Quod Erat Demonstrandum

2013/07/04

無聊數算

Filed under: NSS — johnmayhk @ 12:08 下午
Tags:

趁學校進行第 n 次模擬 stock taking(其間,一小撮同事忙死,其他同事等侯時悶死)隨便寫個無聊 post。

把 3 點放入 7 個空格,每格最多放一點,比如:

有多少種放置方法?

可以想像把空格由左至右編號:1,2,3,4,5,6,7

第一個例,選上 1,2,5 號格,故

第一個例對應 {1,2,5},類似地
第二個例對應 {2,4,7}
第三個例對應 {5,6,7}

等。總共有多少放置方法,即是在 {1,2,3,4,5,6,7} 中選 3 個不同數字,共有多少組合。

高中同學知,共有

C_3^7

種。

現在讓我以另一種方式數算。

先放「中間點」,例如:

那麼其餘兩點分別放於中間點之左右。見上圖,中間點之左有 1 格,右有 5 格,故總共有 1\times 5 種放點方法。

下圖,

中間點的左右分別有 2 和 4 格,故總共有 2\times 4 種放點方法。

再看下圖:

易知它對應著 3\times 3 種放點方法。

因為中間點可以在第 2 至第 6 格出現,故放點總共有

1\times 5+2\times 4+3\times 3+4\times 2+5\times 1

種方法。綜合較早前結果,得

1\times 5+2\times 4+3\times 3+4\times 2+5\times 1=C_3^7

甚至更一般地:

1\times n+2\times (n-1)+3\times (n-2)+\dots+(n-1)\times 2+n\times 1=C_3^{n+2}

好了,現在運用上式,求

1^2+2^2+3^2+\dots+n^2

首先,我們輕易想像平方數的「對應圖象」,比如 5^2,可以下圖表之:

現在把上圖的 5^2 個圓,以斜線連之如下:

那麼我們便可知:

5^2=1+2+3+4+5+4+3+2+1

其他的平方數,比如 4^2 皆可寫成上述形式,即

4^2=1+2+3+4+3+2+1

所以,以 1^2+2^2+3^2+4^2+5^2 為例,我們有

由上面討論,得

1^2+2^2+3^2+4^2+5^2

=C_3^7+C_3^6

=35+20=55

一般地

1^2+2^2+3^2+\dots+n^2

=C_3^{n+2}+C_3^{n+1}

=\frac{(n+2)(n+1)n}{3!}+\frac{(n+1)n(n-1)}{3!}

=\frac{(n+1)n(n+2+n-1)}{6}

1^2+2^2+3^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6}

發表迴響 »

仍無迴響。

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 位部落客按了讚: