Quod Erat Demonstrandum

2015/02/03

玩 nCr

Filed under: Fun,NSS — johnmayhk @ 3:30 下午
Tags: ,

網遊時偶見有個結果:

C^{m+n}_2=C^m_2+C^n_2+mn

若要學生證之,他們或以

C^n_r=\frac{n!}{r!(n-r)!}

作代數運算。

但以數算(counting)概念處理,甚易。

count-clipart-royalty-free-counting-clipart-illustration-1048674

只要(比方說)考慮 m 男,n 女;選 2 人出來的組合,共 C^{m+n}_2;但 2 人可以是 2 男;2 女或 1 男 1 女;對應選法分別是 C^m_2C^n_2C^m_1C^n_1=mn;於是

C^{m+n}_2=C^m_2+C^n_2+mn

繼續演化…

C^{n+n}_2=C^n_2+C^n_2+n\times n \Rightarrow C^{2n}_2=2C^n_2+n^2

C^{2n+n}_2=C^{2n}_2+C^n_2+2n\times n \Rightarrow C^{3n}_2=(2C^n_2+n^2)+C^n_2+2n^2=3C^n_2+3n^2

C^{3n+n}_2=C^{3n}_2+C^n_2+3n\times n \Rightarrow C^{4n}_2=(3C^n_2+3n^2)+C^n_2+3n^2 =4C^n_2+6n^2

一般地,

C^{kn}_2=kC^n_2+(1+2+\dots +(k-1))n^2=kC^n_2+\frac{k(k-1)}{2}n^2 ……….. (*)

代入 k=n,得

C^{n^2}_2=nC^n_2+\frac{n^3(n-1)}{2}

另一個方向演化…

代入 k=m,(*) 變成

C^{mn}_2=mC^n_2+\frac{m(m-1)}{2}n^2=mC^n_2+n^2C^m_2

把 m,n 角色互換,得

C^{nm}_2=nC^m_2+m^2C^n_2

結合上面兩式,得

mC^n_2+n^2C^m_2=nC^m_2+m^2C^n_2

這就製作出可以給學生做練習的證明題。

又另一個方向演化…

以數算概念,易知

C^{m+n+r}_2=C^{m+n}_2+C^r_2+(m+n)r=C^m_2+C^n_2+C^r_2+mn+nr+rm

C^{m+n+r+s}_2

=C^{m+n+r}_2+C^s_2+(m+n+r)s

=C^m_2+C^n_2+C^r_2+C^s_2+mn+mr+ms+nr+ns+rs

又另一個方向演化…

以數算概念,易知

C^{m+n}_3=C^m_3+C^n_3+C^m_2C^n_1+C^n_2C^m_1=C^m_3+C^n_3+nC^m_2+mC^n_2

循之前有關 C^{kn}_2 的做法,不難得

C^{kn}_3 的式子,同學可試試。

諸如此類,以前在純數課程也有遇過製作涉及 C^n_r 的式子,投巧:

– 代數字(substitution)
– 比較系數(comparing coefficients)
– 求導(differentiation)
– 求積(integration)

現只用「比較系數」玩:

考慮

(1+x)^{2n}=(1+x)^n(1+x)^n

比較等號左右的 x^k 的系數,知

C^{2n}_k=C^n_0C^n_k+C^n_1C^n_{k-1}+C^n_2C^n_{k-2}+\dots +C^n_{k-1}C^n_1+C^n_kC^n_0

代入

k=2,得之前的結果,見:

C^{2n}_2=C^n_0C^n_2+C^n_1C^n_1+C^n_2C^n_0=2C^n_2+n^2

代入

k=3,得:

C^{2n}_3=C^n_0C^n_3+C^n_1C^n_2+C^n_2C^n_1+C^n_3C^n_0=2C^n_3+nC^n_2

又另一個方向演化…

考慮

(1+x)^{3n}=(1+x)^n(1+x)^n(1+x)^n

比較等號左右的 x^k 的系數,知

C^{3n}_k=C^n_0C^n_0C^n_k+C^n_0C^n_1C^n_{k-1}+C^n_0C^n_2C^n_{k-2}+\dots +C^n_kC^n_0C^n_0

不難知等號右面共 C^{k+2}_2 項。

代入

k=2,得:

C^{3n}_3=C^n_0C^n_0C^n_3+C^n_0C^n_1C^n_2+C^n_0C^n_2C^n_1+C^n_0C^n_3C^n_0+C^n_1C^n_0C^n_2+C^n_1C^n_1C^n_1+C^n_1C^n_2C^n_0+C^n_2C^n_0C^n_1+C^n_2C^n_1C^n_0+C^n_3C^n_0C^n_0

注,等號右面共 C^{3+2}_2=10 項,數法如下(貼圖而不解釋,讀者自行參透):

1904005_10152650768998231_1891426184618957630_n

化簡,得

C^{3n}_3=3C^n_3+6nC^n_2+n^3

應該還可以繼續玩下去,但都是停於此。

發表迴響 »

仍無迴響。

RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: