數學女孩：10.5 音樂教室_結城浩

第二天。

放學後，在音樂教室裡，我、盈盈還有米爾嘉三人在一起說話。

你們去討論你們的歐拉，我呢就來彈我的巴赫。

盈盈坐在鋼琴旁邊彈著變奏曲邊說。她是高中二年級的學生，雖然是和我一個年級的，但是不與我和米爾嘉同班。她擔任鋼琴愛好者協會「最強音」的會長，是一個非常喜歡琴鍵的小女孩。

「嗯，巴赫很好啊。」米爾嘉邊笑邊把兩手放在身後，合著鋼琴的拍子，一步一步在音樂教室裡來回走動，一副很陶醉的樣子。她的心情很好。

「對了，泰朵拉今天會來嗎？不是只要有你在的地方，不管在哪裡她都會過來的嗎？」盈盈一邊繼續彈奏一邊朝我問道。

泰朵拉。

「那孩子並不是一直追隨著我哦。」我說。

就在那時，泰朵拉懷裡抱著筆記本走進了音樂教室。

「啊，原來您在這裡啊。我看您不在圖書室，還想您怎麼了呢。」

「她還追得真緊啊。」盈盈小聲嘀咕道。

「是不是給你們添麻煩了？」泰朵拉打量著我們。

「沒關係，泰朵拉。我也沒什麼要緊的事情做。」我說。

「你聽到我那令人感動的演奏了嗎？」盈盈問。

「嗯嗯，我聽了。——啊，對了。」我說，「泰朵拉來得正好，大家一起來討論一下昨晚的成果吧。米爾嘉，我可以寫寫分拆數的式子嗎？」

「你的意思是說你求了通項 Pn 的有限項代數式嗎？」米爾嘉頓時站起身，很嚴肅地問我。

「沒有，不是，我並沒有求出通項公式 Pn 的有限項代數式，而是求得了生成函數 P(x) 的無限積的形式。」我說。

「那就好。」米爾嘉的臉上又露出了笑容。

「那麼就用前面的黑板吧。」我走到音樂教室前面，滑動了一下黑板，準備開始寫字。米爾嘉和泰朵拉也湊了過來。

盈盈說：「啊呀，你們開始做數學了啊。」邊說邊停下了彈鋼琴的手。

10.5.1　我的發言（分拆數的生成函數）

「為瞭解出問題 10-2，我想到了求分拆數 Pn 的通項公式。為此首先要求生成函數 P(x)。生成函數 P(x) 可以寫成以下形式。」我說。

「我只是照定義式的樣子寫出了這個式子。我自己假設了問題 10-3『尋找乘積形式的生成函數 P(x)』。但是在解問題 10-3 之前，為了便於說明，我們先來考慮一下接下來的問題 10-4，就是對硬幣的枚數和種類加以限制的『帶有限制的分拆數』問題。」我說道。

問題 10-4　「帶有限制的分拆數」

1 元硬幣、2 元硬幣和 3 元硬幣各有 1 枚。支付 3 元的方法有幾種？

「這個問題 10-4 並不難。因為限制了硬幣的種類，只有 1、2、3 元，而且各種硬幣都只有 1 枚，所以支付 3 元的方法只有兩種：一種是使用 1 元和 2 元硬幣，還有一種是使用 3 元硬幣。這就是答案。」

解答 10-4

2 種。

「對了，利用問題 10-4，我們來說明一下生成函數。我來列舉一下使用各種硬幣能夠支付的金額。」

使用可以支付的金額是 0 元或者是 1 元。

使用可以支付的金額是 0 元或者是 2 元。

使用可以支付的金額是 0 元或者是 3 元。

「在這裡，我們考慮一下以下式子。它使用了形式上的變量 x，指數部分表示『可以支付的金額』。為了便於理解，1 可以寫作 x0。」

「原來如此。真是有意思啊。」米爾嘉說。

「是啊。」我微笑著說。

「米爾嘉，你說什麼『原來如此』呢？學長，你說什麼『是啊』呢？我不明白。學姐，學長，拜託你們按照邏輯順序把話說清楚好嗎？」泰朵拉開始抱怨起來。這時，盈盈彈奏起滑稽的片段。

「你繼續說說看。」米爾嘉說。

「泰朵拉，剛才的式子應該這樣理解哦。」我說。

「展開後或許你就能理解了。各個硬幣所能支付的金額變成了指數，而且可以支付的所有可能性都變成了項出現。」我又說。

「比如說，x1+2+0 這一項的指數 1 + 2 + 0 可以這樣理解。」

1　　使用可以支付的金額 1 元2　　使用可以支付的金額 2 元0　　使用可以支付的金額 0 元

「學長，等一下。可我還是不太明白 x1+2+0 的意思。如果使用 1 枚、1 枚、0 枚，那麼指數就不應該是 1 + 2 + 0，而應該是 1 + 1 + 0，不是嗎？」泰朵拉一副很認真的表情，不停地追問。

「啊，不對。這裡考慮的不是『k 元硬幣的枚數』，而是『k 元硬幣可以支付的金額』。」我說。

「如果是我的話，我會把它稱為『k 元硬幣貢獻的部分』。」米爾嘉說。

「學長，我有點明白了。確實，看了展開式後，從 x 的指數能夠看出使用、、進行支付的所有可能性，但是還是有些不可思議。為什麼非得考慮不可呢？」泰朵拉問道。

「這個嘛，是因為『公式的展開方法』和『支付方式的所有可能性的獲取方法』的原理是相同的。將展開時，各項是這樣形成的。」我答道。

從 x0 + x1 中選擇項，
從 x0 + x2 中選擇項，
從 x0 + x3 中選擇項，然後求積。

「這種選擇方法和下面這種考慮支付方法時的做法一樣。」

選擇用來支付的金額，
選擇用來支付的金額，
選擇用來支付的金額，然後求和。

「哈哈，原來如此。我明白了。為了求出所有組合，所以就把式子展開了。……呵呵。」泰朵拉似乎可以接受我的說法。

於是我繼續解釋。

「整理展開後的式子，我們可以得到以下式子。合併含有 xk 的項，也就是合併同類項，按照指數從小到大的順序進行排列。」

「泰朵拉，x3 前的係數變成了 2 吧。你認為這個意味著什麼呢？」我問道。

「嗯，你是問為什麼係數是 2 嗎？——因為 x3 的項只有兩項啊。具體說來，就是 x0+0+3 和 x1+2+0。——原來如此，我明白了。x3 前的係數變成 2，就表示支付的金額是 3 元時支付方法有 2 種。」她說。

「正是如此。我們再來考慮一遍泰朵拉剛才說的話。在我們面前是使用了形式上的變量 x 的冪的和。然後，xn 的係數是『支付金額是 n 時支付方法的個數』。那麼，『支付金額是 n 時支付方法的個數』究竟是什麼呢？」我問道。

「『支付金額是 n 時支付方法的個數』是……啊，是分拆數！」泰朵拉恍然大悟。

「是啊。因為問題 10-4 中，硬幣的枚數和種類都受到限制，所以和村木老師的問題 10-1 及問題 10-2 中所出現的分拆數不同。但是，情況也非常相似。存在使用了形式上的變量 x 的冪的和，而它的係數又是『支付金額是 n 時支付方法的個數』，這種情況只可能是生成函數了。也就是說，是『帶有限制的分拆數』的生成函數。」我說。

問題 10-4 的「帶有限制的分拆數」的生成函數

「原來如此……說到生成函數，就要出現無窮級數，我還以為會很麻煩呢。原來像這類因式那麼少的有限項積也會成為生成函數啊。迷你生成函數……」泰朵拉擺了一個捏飯團的手勢。

「那麼……」我繼續說道。

◎　　◎　　◎

到此為止我們所說的是「帶有限制的分拆數」。從這裡開始，我們解除對硬幣的枚數和種類的限制。但是，討論的推進方法還是相同的。只不過這裡不再是這種「有限項和的有限項積」，而是「無限項和的無限項積」，如下所示。

無限項和的出現與不限制硬幣枚數這一條件相對應。

無限項積的出現與不限制硬幣種類這一條件相對應。

展開這個無限項和的無限項積後，支付方法的所有可能性就可以一口氣算出來。求出乘積，合併同類項之後，我們就可以開始觀察 xn 的項。這樣一來，xn 的係數就是 n 的分拆數。為什麼這麼說呢？這是因為 xn 的係數就和「n 元的支付方法的個數」相同。

「係數是分拆數的形式上的冪級數」，也就是上面所寫的無限項和的無限項積，就是「分拆數的生成函數」。這樣一來，P(x) 就可以寫成以下形式。

好了，在這裡我們轉變一下視角。將形式上的變量 x 想像成 0 ≤ x < 1 的實數，然後用等比數列的公式來計算。這樣一來，k 元硬幣貢獻的部分就可以表示成以下的分數形式。

P(x) 中的無限項和都可以用這個公式來表示成分數形式。

「無限項和的無限項積」變為了「分數的無限項積」。這就是變成了乘積形式的生成函數 P(x)。我們把 ×（乘號）統一寫成 ·（點號）。

解答 10-3　（分拆數 Pn 的生成函數 P(x)「積的形式」）

我們來整理一下到此為止的內容吧。為了求出村木老師問題 10-2 中的 P15，我想到要先求出通項公式 Pn。為此，我又想到了求 Pn 的生成函數 P(x)，並自己假設了問題 10-3。最後，如上面的解答 10-3 所示，我求得了乘積形式的生成函數 P(x)。

接下來，我準備考慮下面的問題 X。

問題 X

將下面的函數 P(x) 進行冪級數展開的時候，xn 的係數為多少？

xn 的係數為 Pn。求出通項公式 Pn 後，再來探討一下問題 10-2 中的不等式 P15 是否小於 1000。

「求分拆數的通項公式」的「旅行地圖」

到這裡我不再繼續說了。

◎　　◎　　◎

「你是想正面求解嗎？」米爾嘉立即開口問道。

「是的。」

「嗯。不過如果只是證明問題 10-2 的不等式的話，是沒有必要非求出 Pn 不可的，不是嗎？」米爾嘉說。

「這個……道理上來講是這樣的。」我開始不安起來。

「不過我既沒有求出通項 Pn，也沒有求出 P15，就把問題 10-2 解答出來了。」米爾嘉說。

「啊？」

10.5.2　米爾嘉的發言（分拆數的上限）

「只要證明問題 10-2 的不等式 P15 < 1000 的話，不一定非要求出 P15 的值。」米爾嘉一邊這樣說，一邊跟我調換了一下位置，站在了黑板前。

「分拆數 Pn 會急劇增加，變成泰朵拉所說的『了不得的數字』。所以在這裡，我想先分析一下分拆數 Pn 的上限在哪裡。」

「上限指的是什麼呢？」泰朵拉馬上問道。

「上限指的是，對於任意大於等於 0 的整數 n，滿足 Pn ≤ M(n) 的函數 M(n)。雖然 Pn 會隨著 n 的變大而變大，但是不會大於 M(n)，這個 M(n) 就是上限。另外，上限有無數個，而不是僅限於一個。」

「就是說上面有一個界限麼？」泰朵拉把手放在頭頂上說。

「對。上限這個詞有時候表示常數，在這裡卻不是這樣。M(n) 說到底就是關於 n 的函數。那麼，觀察 P0, P1, P2, P3, P4 會發現，它們都與斐波那契數列 F1, F2, F3, F4, F5 相等。」

米爾嘉用手指點過 1, 2, 3, 4，在 5 那裡停下了。

「遺憾的是 P5 不等於 F6，儘管這樣，但因為我們知道 P5 = 7，F6 = 8，所以依然可以得到

於是我推測，雖然 Pn = Fn+1 這個等式不成立，但

這個不等式也許是可以成立的。接下來，可以證明它確實是成立的。也就是說，這裡使斐波那契數列 Fn+1 作為 Pn 的上限 M(n) 了。證明的時候使用數學歸納法即可。」米爾嘉說。

◎　　◎　　◎

根據斐波那契數列求分拆數 Pn 的上限

假設分拆數，斐波那契數列。這時，對於所有的整數 n ≥ 0，以下不等式成立。

下面用數學歸納法來證明。

首先，當 n 為 0 和 1 時，Pn ≤ Fn+1 成立。

然後，對於任意整數 k ≥ 0，只要證明

這個式子成立就可以了。

為什麼這麼說呢？這是因為如果這個式子成立的話，那麼

由 P0 ≤ F1 和 P1 ≤ F2 可以得到 P2 ≤ F3。

由 P1 ≤ F2 和 P2 ≤ F3 可以得到 P3 ≤ F4。

由 P2 ≤ F3 和 P3 ≤ F4 可以得到 P4 ≤ F5。

由 P3 ≤ F4 和 P4 ≤ F5 可以得到 P5 ≤ F6 ……

也就是說，對於任意整數 n ≥ 0，都有 Pn ≤ Fn+1 成立。這是數學歸納法的解法。這些說明是特意為泰朵拉做的補充說明，因為我看到她現在頭上有一個大大的問號。