Quod Erat Demonstrandum

2015/04/06

平鋪

Filed under: Fun — johnmayhk @ 11:23 下午
Tags:

domino-square_0

把 1*2 骨牌(domino)平鋪在 3*2 的棋盤上,共 3 種方式,見下:

johnmayhk-tiling1

可否把 1*2 骨牌平鋪在 3*3 的棋盤上?不能。

把 1*2 骨牌平鋪在 3*4 的棋盤上,共多少種方式?不難想像包括以下 3*3=9 種方式:

johnmayhk-tiling2

還有以下兩種:

johnmayhk-tiling3

共 11 種情況。

一般地,考慮以 1*2 骨牌來平鋪 3*2n 棋盤,共有 a_n 種方式。

上述兩例,知 a_1=3, a_2=11,那麼,其他的 a_n 是甚麼?

平鋪包括以下兩種情況:

情況一,最左的骨牌全是水平,見:

johnmayhk-tiling4

a_{n-1} 種方式。

情況二,最左只有一塊骨牌是水平,見:

johnmayhk-tiling5

那麼右邊以紅邊包圍的部分,是一個長長的 L 形。如上圖,此 L 形高 3 單位,下底是 2(n-1) 單位,上底是 2n-1 單位。設平鋪這類 L 形(即高 3 單位,一底是 2k 單位,另一底為 2k+1 單位者)的方式共 c_k 種。可見情況二共有 2c_{n-2}

結合情況一和二,得

a_n=a_{n-1}+2c_{n-1} ……………….. (1)

現在考慮 c_n

johnmayhk-tiling6

易知這 L 形的平鋪方式可分以下兩種情況:

johnmayhk-tiling7

a_n 種;和

johnmayhk-tiling8

c_{n-1} 種;所以

c_n=a_n+c_{n-1} ……………….. (2)

由 (1),

a_n-a_{n-1}=2c_{n-1}

由 (2),

a_n-a_{n-1}=2(c_n-a_n)

3a_n-a_{n-1}=2c_n

3a_n-a_{n-1}=a_{n+1}-a_n (由 (1))

a_{n+1}=4a_n-a_{n-1}

a_n=4a_{n-1}-a_{n-2}

(當中 n\ge 2a_0=1。驗算一下,a_1=3a_2=4a_1-a_0=4(3)-1=11

有了 a_n=4a_{n-1}-a_{n-2} 這個遞迴關係(recurrence relation),可以用生成函數找尋 a_n

設 {a_n} 的生成函數為

p=\displaystyle \sum^{\infty}_{r=0}a_rx^r

現在找具體些的 p

p

=\displaystyle \sum^{\infty}_{r=0}a_rx^r

= a_0+a_1x+\displaystyle \sum^{\infty}_{r=2}a_rx^r

= 1+3x+\displaystyle \sum^{\infty}_{r=2}(4a_{r-1}-a_{r-2})x^r

= 1+3x+\displaystyle \sum^{\infty}_{r=2}4a_{r-1}x^r-\displaystyle \sum^{\infty}_{r=2}a_{r-2}x^r

= 1+3x+\displaystyle \sum^{\infty}_{r=1}4a_{r}x^{r+1}-\displaystyle \sum^{\infty}_{r=0}a_rx^{r+2}

= 1+3x+4x\displaystyle \sum^{\infty}_{r=1}a_{r}x^r-x^2\displaystyle \sum^{\infty}_{r=0}a_rx^r

= 1+3x+4x(\displaystyle \sum^{\infty}_{r=0}a_{r}x^r-a_0)-x^2\displaystyle \sum^{\infty}_{r=0}a_rx^r

= 1-x+4x\displaystyle \sum^{\infty}_{r=0}a_{r}x^r-x^2\displaystyle \sum^{\infty}_{r=0}a_rx^r

= 1-x+4xp-x^2p

於是,p 的較具體式子是

p=\frac{1-x}{1-4x+x^2}

現在考慮

(1-4x+x^2)^{-1}

=(1-x(4-x))^{-1}

=1+x(4-x)+x^2(4-x)^2+x^3(4-x)^3+x^4(4-x)^4+x^5(4-x)^5+\dots

設展開上式後,得

=b_0+b_1x+b_2x^2+b_3x^3+b_4x^4+b_5x^5+\dots

可見,

b_0=1

b_1=4

b_2=(-1)+4^2=-1+4^2

b_3=C^2_1(-4)+4^3=-4C^2_1+4^3

b_4=(-1)^2-C^3_1(4^2)+4^4=1-4^2C^3_1+4^4

b_5=C^3_2(4)+C^4_1(-1)4^3+4^5=4C^3_2-4^3C^4_1+4^5

b_6=(-1)^3+C^4_2(-1)^24^2+C^5_1(-1)4^4+4^6=-1+4^2C^4_2-4^4C^5_1+4^6

\dots

依上述模式,不難得出

b_0=1,b_1=4,b_n=4^n-4^{n-2}C^{n-1}_1+4^{n-4}C^{n-2}_2-\dots+(-1)^k4^{n-2k}C^{n-k}_k for n\ge 2

其中,n-k\ge k\Rightarrow k\le \frac{n}{2}\Rightarrow k=[\frac{n}{2}],即 k 是不超過 \frac{n}{2} 的最大整數。

好了,p 的展開式如下:

p

=\frac{1-x}{1-4x+x^2}

=(1-x)(b_0+b_1x+b_2x^2+b_3x^3+\dots)

=1+(b_1-b_0)x+(b_2-b_1)x^2+(b_3-b_2)x^3+\dots

a_n=b_n-b_{n-1}

亦即可計出 a_n

其實,只要上一上網,在

http://www.wolframalpha.com/

輸入

expand (1-x)/(1-4x+x^2)

不用一分數秒,得:

johnmayhk-3by2n

從係數可見

a_1=3,a_2=11,a_3=41,a_4=153,a_5=571,\dots

進一步推廣,可以考慮棋盤的高為 4,5,6,… 個單位,有興趣者可參考下文:

http://www.fq.math.ca/Scanned/18-1/read.pdf

發表迴響 »

仍無迴響。

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