一題填數字的問題(排列組合)

[大卡車 10]

將1-10十個整數填入下列空格

┌-┬-┬-┬-┬-┐

├-┼-┼-┼-┼-┤

└-┴-┴-┴-┴-┘

並規定每一行下面的數字不能比上面大

　　　每一列左邊的數字不能比右邊大

求有幾種填數字的方法？

PS:我是用土法煉鋼解出來 但我想知道是否可以用遞迴式表示到第N列

還有問到老師說可以用走4X4格子的加法原理方式但不能過對角線 但我不知道原因 可否請大家幫忙解答 謝謝!!!

[曾阿牛 10]

先回答老師對您的解說

數學上　常常在兩個問題(或兩個觀念)之間　找尋一一對應的關係　

使得　想要解決其中一個問題時　等於是解決另一個與之對應的問題　

排列組合在這方面的表現更是明顯

以這題來說　題目有兩個規定　我們先看第一個：每一列左邊的數字不能比右邊大

在只考慮這一條規定之下　我們可以發現填格子的方法恰與一個由1和2所構成的數列(長度為10)產生一一對應

對應的方法是　將 1 ～ 10 在格子的列數 依序記錄下來 (底下那列記為1　上方列記為2)

譬如說　５６７８10

　　　　１２３４９　這樣的的填法　對應到 1111222212

因為 1~4 在第一列 5~8在第二列　所以數列的前四項是1　第5到第8項是2

9在第一列　所以數列的第9項是1　10在第二列　所以數列的第10項是2

反過來　如果任意給一個數列(注意：必須五個1和五個2)　我們也可以找到一個對應的填格子的方法

譬如說　1211211222　則對應到　２５８９10

　　　　　　　　　　　 　　　　 １３４６７

所以　光考量每一列左邊的數字不能比右邊大時　

我們可以將填格子的問題　看成是　由五個1和五個2組成的數列的問題

接下來　要考慮題目的另一規定：每一行下面的數字不能比上面大

如果數列的開頭是 11222　則對應到　３４５

　　　　　　　　　　　　　　　　　１２　　則 ５ 的下方必然只能填 6, 7, 8, 9, 10 但都比5大

違背了題目的規定　　所以　一個數列對應到的填格子方法要滿足題目規定的話

必須具備以下的性質：

從左數到右　不論數到什麼地方　1的總數必須大於等於2的總數

像是剛才的 11222　數到第五項的時候 1的總數是2 但2的總數是3　這是造成違規的主因

總結：填格子問題可以看成是由五個1和五個2組成的數列的問題　而且該數列必須滿足

從左數到右　不論數到什麼地方　1的總數必須大於等於2的總數

而上述的數列問題　可以用走4X4格子　配合上角落註記法 來計數

數列如果出現1　相當於往右邊走一格(從4X4格子的左下角出發)　出現2　則往上走一格

五個1反應了往右共走五格　五個2反應了往上共走五格

但　考慮到　1的總數必須大於等於2的總數　所以　走格子的時候不可以走到左上方的部分

也就是老師說的　不能(超)過對角線

今天時間不夠　有些地方沒有解說的很詳細　如果有疑問　可先提出　阿牛下次再補充說明

此內容已被編輯, June 5, 2012 ,由 曾阿牛

[大卡車 10]

已經瞭解了!!感謝

[yangmenghsuan 0]

有人可以用稍微比較白話的方式講解給我聽嗎？(´･ω･`)?

[DoDoMan 0]

左下角是1,  右上角是10

[DoDoMan 0]

在 2012/6/5 at PM1點40分, 曾阿牛說:

從左數到右　不論數到什麼地方　1的總數必須大於等於2的總數

研究了一下，這個規則是對的。

此內容已被編輯, July 2, 2021 ,由 DoDoMan