用數學歸納法證明組合數C(n,6)=C(n,n-6)

Question

請用數學歸納法證明組合數C(n,6)=C(n,n-6)，對於所有6以上的正整數n皆成立。

海韻&風濤：
我有點小問題呢！
言下之意是說
n!/[m!(n-m)!]=C(n,m)，m是被乘數，所以取m；
n!/[(n-m)!m!]=C(n,n-m)，(n-m)是被乘數，所以取(n-m)；
但乘法既然有交換律，
n!/[m!(n-m)!]為什麼不能是C(n,n-m)呢？[m是被乘數，但是取(n-m)]
如果已確定可以是的話，又何必用數學歸納法證明呢？

有人規定只能取被乘數，不能取乘數嗎？
如果沒有的話，請問您證明的是C(n,6)=C(n,n-6)，還是C(n,6)=C(n,6)？

Answer 1

這個問題不知為何要指定用歸納法來解,如同你們所解的用乘法交換律直接可以證明,如果非要用歸納法必須假設不知道除數中是否存在交換率,如此

n=6時
C(6,6)=6!/(6!0!)=72/(72*1)=1
C(6,0)=6!/(0!6!)=72/(1*72)=1 成立
設n=k時成立
n=k+1時
C(k+1,6)=(k+1)!/(6!(k-5)!)=(k+1)*k*(k-1)*...*7/((k-5)*(k-4)*(k-3)*...*1)
=(k+1)*k*(k-1)*...*(k-4)/(6*5*4*3*2*1)
C(k+1,k-5)=(k+1)!/((k-5)!6!)=(k+1)*k*(k-1)*...*(k-4)/(6*5*4*3*2*1)
成立

故C(n,6)=C(n,n-6)對於所有6以上的正整數n皆成立

2007-12-04 15:25:22 補充：
既然你已經知道C(n,6)與C(n,n-6)實際上組合的方法不同但剛好有相同的表示式,不知你為何還有這樣的問題

還是解一下給你看好了

C(n,k)是從n個東西無順序取出k個的方法數
取出第1個有n個選擇
取出第2個有n-1個選擇
:
:
取出第k個有n-k+1個選擇
但是因為是無順序的
所以k個次序掉換有k!種方法
所以C(n,6)=n(n-1)(n-2)...(n-5)/6!
C(n,n-6)=n(n-1)...7/(n-6)!(這裡的公式僅適用於n>6,如果n=6時因為代表什麼都不拿,所以C(6,0)=1,n<5時不存在這種組合)

2007-12-04 15:26:22 補充：
當n=6時
C(6,6)=6*5*4*3*2*1/6!=1=C(6,0)成立
設n=k時成立
n=k+1時
C(k+1,6)=(k+1)k(k-1)...(k-4)/6!=(k+1)C(k,6)/(k-5)
C(k+1,k-5)=(k+1)k(k-1)...7/(k-5)!=(k+1)C(k,k-6)/(k-5)=(k+1)C(k,6)/(k-5)=C(k+1,6)成立
故C(n,6)=C(n,n-6)對於所有6以上的正整數n皆成立
得證

2007-12-04 15:33:54 補充：
其實從公式

C(n,k)=n(n-1)(n-2)...(n-k+1)/k!

就可以看出為什麼我們習慣寫C(n,k)=n!/[k!(n-k)!]而不是C(n,k)=n!/[(n-k)!k!]
因為我們是同時在除數和被除數右邊乘上(n-k)!
所以就算沒規定,我們還是寫C(n,k)=n!/[k!(n-k)!]

2007-12-10 13:32:53 補充：
克勞棣:
你有發現你回到自己的爭點上了嗎
如果
C(n,6)=P(n,6)÷6!=[n!/(n-6)!]÷6!
C(n,n-6)=P(n,n-6)÷(n-6)!=[n!/6!]÷(n-6)!
那我們直接可以說C(n,6)=C(n,n-6)不是嗎
何須使用數學歸納法去證明
而且P(n,6)=n!/(n-6)!也是經過整理過而非原來的長相

2007-12-13 18:41:48 補充：
既然可以整理
那我當然可以將你所謂被除數和除數都不相同的兩式整理到相同的形式吧
除非你說(A/B)/C=A/(B*C)這個式子沒被證明成立所以不能用
但是當你出一個題目時
你怎麼可以在沒有說明的情況下去假設哪些公式可用及不可用
也就是
既然我可以用C(n,6)=P(n,6)÷6!=[n!/(n-6)!]÷6!
當然我也可以用C(n,6)=n!/[6!(n-6)!]

2007-12-13 18:42:21 補充：
又或是
既然
[n!/(n-6)!]÷6!
[n!/6!]÷(n-6)!
因為被除數和除數都不一樣所以需要證明
那我也可以說
n!/[m!(n-m)!]
n!/[(n-m)!m!]
的除數形式不同所以需要證明
因為沒人規定A*B=B*A

Answer 2

Problem: Show C(n, r) = C(n, n-r), for n >= r
using induction on the integer n.
Hint:
Use the equation C(n,r) = C(n-1, r) + C(n-1, r-1) ---- (*)
This equation is easy to see:
C(n-1, r) is for not including some element A, while
C(n-1, r-1) is for including A, in the combination.
PROOF: (Omit the base case when n = r, which is easy)
We show C(k+1, r) = C(k+1, k+1-r), assuming
that C(k, r) = C(k, k-r):
C(k+1, r) = C(k, r) + C(k, r-1) (by *)
= C(k, k-r) + C(k, k-(r-1)) (by induc. hypo.)
= C(k+1, k-r+1) (by *)

Answer 3

贊同克勞棣:
解題的兩位被題目給騙了!

Answer 4

兩位，沒有人規定
C(n,6)=n!/[6!(n-6)!]，而C(n,n-6)=n!/[(n-6)!6!]，且分母的兩個數不得互換位置，
相反的，也沒有人規定
C(n,n-6)=n!/[6!(n-6)!]，而C(n,6)=k!/[(n-6)!6!]，且分母的兩個數不得互換位置，
乘法交換律沒道理不能成立，

所以，當你認定C(n,6)=n!/[6!(n-6)!]時，你已經預設C(n,6)=C(n,n-6)成立了，
因為兩者長得一模一樣，都是n!/[6!(n-6)!]。

2007-11-29 21:18:35 補充：
但，

C(n,6)與C(n,n-6)只是「值」相同，它們本質是不一樣的，

C(n,6)是從n個相異物中取出6個的方法數，
C(n,n-6)是從n個相異物中取出(n-6)個的方法數，
不一樣的東西怎會有永遠相同的算式呢？

而事實上，C(n,6)與C(n,n-6)的算式的確是不一樣的，
n!/[6!(n-6)!]並非C(n,6)原來的長相，
這，只是一個化簡過的結果罷了。

2007-12-08 02:35:14 補充：
zook：
沒注意到您終於回應了。
C(n,6)=n(n-1)(n-2)...(n-5)/6!
C(n,n-6)=n(n-1)...7/(n-6)!
寫這樣不是很累嗎？而且數學表達式應該盡量避免刪節號。
C(n,6)=P(n,6)÷6!=[n!/(n-6)!]÷6!
C(n,n-6)=P(n,n-6)÷(n-6)!=[n!/6!]÷(n-6)!
我覺得寫這樣證明上比較方便，不知道您認為呢？

2007-12-11 21:02:45 補充：
[n!/(n-6)!]÷6!
[n!/6!]÷(n-6)!
這兩式，被除數和除數都不一樣，是不是？
被除數和除數都不一樣，必然得到相同的結果嗎？不！
所以需要證明。

我並無強調一定要最原來的長相，而是它們應該不一樣 。

2007-12-13 20:41:48 補充：
所以說，問題又繞回來了
C(n,6)=P(n,6)÷6!這是組合數公式的來源，
你不能寫C(n,6)=P(n,n-6)÷(n-6)!，這是不能交換的，除非你先證明P(n,6)÷6!=P(n,n-6)÷(n-6)!。

2007-12-13 20:50:32 補充：
有人規定C(n,6)=P(n,6)÷6!=[n!/(n-6)!]÷6!且C(n,n-6)=P(n,n-6)÷(n-6)!=[n!/6!]÷(n-6)!
，卻沒人規定C(n,6)必須是n!/[6!(n-6)!]，或C(n,6)必須是n!/[(n-6)!6!]，
我沒說什麼公式可用，什麼公式不可用，
問題是C(n,6)與C(n,n-6)到底有什麼不一樣，它們應該有不能互換的計算形式吧！

難道
n人的直線排列方法數為(n+1)!/(n+1)，而(n+1)人的環狀排列方法數為n!？