第2章 二項式與鴿籠原理
2.1 係數數選法，鴿籠找保證
對非負整數 n，展開 (x+y)ⁿ 時從每個因子選一項。得到 xⁿ⁻ᵏyᵏ，正好要在 n 個因子中選 k 個取 y，所以係數是 C(n,k)。當 1≤k≤n−1，依最後一個因子取 x 或 y 分類，得到 C(n,k)=C(n−1,k)+C(n−1,k−1)。兩端係數為 1，n=0 時只有常數項 1。代 x=y=1 得每列係數和為 2ⁿ。
設 m、k 為正整數，每個物件恰放入 m 個箱之一。若各箱至多 k−1 個，總數至多 m(k−1)；所以 N>m(k−1) 就保證某箱至少 k 個。對 N≥1，取 k=⌈N/m⌉ 可知某箱至少有這麼多。若各箱可自由放入 k−1 個，平均放 m(k−1) 個時每箱恰有 k−1 個，說明再少一個就無法保證。若另有分箱限制，需依實際限制找未達標的配置。
2.2 四個例題
例題1 第十三個才保證
13 張卡各入四個箱。若每箱至多 3 張，合計至多 12 張，矛盾。所以某箱至少 4 張。12 張可採每箱 3 張，故 13 是最小保證門檻。
例題2 展開時只找想要的一項
(x+2y)⁵ 的 x³y² 項，從五因子選兩個給 2y。係數 C(5,2)·2²=10·4=40；另三個 x 不改係數。
例題3 一列係數可用一個代入加總
(1+t)⁶ 的係數依次是 1、6、15、20、15、6、1。代 t=1 即得到總和 2⁶=64，不必逐項加算。
例題4 把餘數當箱子
任取七個整數，按除以 6 的餘數 0 到 5 分箱。七個物件進六箱，有兩個同餘；兩數之差被 6 整除。若只有六個，0 到 5 各一個就不能保證。
2.3 練習
- B10-C02-Q01 求 (1+t)⁴ 的 t² 係數。
- B10-C02-Q02 求 (x−2)⁴ 的 x² 係數。
- B10-C02-Q03 用前一列的兩個係數算 C(7,3)。
- B10-C02-Q04 (1+t)⁵ 的所有奇次係數之和？
- B10-C02-Q05 22 本書各放入五格。無論如何分配，最滿的一格至少有幾本？請給出達到這個最小值的分法。
- B10-C02-Q06 三種顏色的球，至少抽幾顆才保證有三顆同色？假設各色供應充分。
- B10-C02-Q07 從 13 人的出生月份，能保證什麼？
- B10-C02-Q08 若 16 個物件入四箱，必有一箱至少五個嗎？
- B10-C02-Q09 證明 n≥1 時，(x+y)ⁿ 兩端係數都是 1。
- B10-C02-Q10 五種標籤各最多重複使用兩次。若已標 11 件會怎樣？
2.4 完整解答
Q01
四個因子中選兩個取 t，其餘取 1，係數 C(4,2)=6。
Q02
選兩個因子取 −2，另兩個取 x。乘上 (−2)²，係數 C(4,2)·4=24。
Q03
分指定元素是否入選，得 C(6,2)+C(6,3)=15+20=35。兩類沒有重疊。
Q04
把 t=1 與 t=−1 的值相減，偶次抵消、奇次變兩倍。故奇次和為 (32−0)/2=16。
Q05
每格至多 4 本時只有 20 本，所以至少一格 5 本。分成 5、5、4、4、4 可達，不能保證有 6 本。
Q06
未達標時，每色可至多兩顆，合計 6 顆；6 顆可每色兩顆。故至少 7 顆才保證。
Q07
按 12 個月份分箱。若每月最多一人，總共最多 12 人，所以至少兩人同月，不必同日。
Q08
不必。每箱 4 個就合計 16，且沒有五個同箱。要保證至少 5 個，最小是 17 個。
Q09
xⁿ 只能從每個因子取 x，yⁿ 只能從每個因子取 y；兩個選擇各只有一種。若 n=0，只有常數項 1，不是兩項。
Q10
每種若最多用兩次，最多能標 5·2=10 件。標了 11 件代表原限制無法同時滿足，至少一種標籤用到三次。