離散数学・組合せ論の問題

$\text{A},\text{B},\text{C},\text{D}$ がもらう個数をそれぞれ $a,b,c,d$ とすると、求める数は
$$a+b+c+d=8,0\le a\le 2,b,c,d\ge 0$$
を満たす整数の組 $(a,b,c,d)$ の個数である。

母関数をつくる。 $a$ のとり得る値 $0,1,2$ に対応して $1+x+x^2$、$b,c,d$ のとり得る値 $0,1,2,\dots$ に対応してそれぞれ $1+x+x^2+\cdots =\frac{1}{1-x}$ を考える。これらの積を展開したとき、$x^a{x}^b{x}^c{x}^d=x^{a+b+c+d}$ の項がちょうど $1$ つの組 $(a,b,c,d)$ に対応するので、求める数は
$$[x^8](1+x+x^2)\cdot \frac{1}{(1-x{)}^3}$$
である。

式を整理する。 等比数列の和より $1+x+x^2=\frac{1-x^3}{1-x}$ なので
$$(1+x+x^2)\cdot \frac{1}{(1-x{)}^3}=\frac{1-x^3}{(1-x{)}^4}=\frac{1}{(1-x{)}^4}-x^3\cdot \frac{1}{(1-x{)}^4}.$$

係数を取り出す。 公式 $[x^n]\frac{1}{(1-x{)}^k}=\left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)$ を $k=4$ で使う。
- 第 1 項：$[x^8]\frac{1}{(1-x{)}^4}=\left(\genfrac{}{}{0ex}{}{11}{3}\right)=165$
- 第 2 項：$x^3$ が掛かっているので $[x^8]x^3\frac{1}{(1-x{)}^4}=[x^5]\frac{1}{(1-x{)}^4}=\left(\genfrac{}{}{0ex}{}{8}{3}\right)=56$

よって求める数は
$$165-56=109.$$

（確認：$a=0,1,2$ のとき残りを $b,c,d$ に配る方法は ${}_3{\mathrm{H}}_8=45$, ${}_3{\mathrm{H}}_7=36$, ${}_3{\mathrm{H}}_6=28$ 通りで、合計 $109$ 通り。）

A がもらう個数 a は 0, 1, 2 のいずれか。残りの 8−a 個を B, C, D の 3 人に配る方法は、重複組合せで $\left(\genfrac{}{}{0ex}{}{(8-a)+2}{2}\right)$ 通り。

• a=0: 8個を3人に配る。$\left(\genfrac{}{}{0ex}{}{10}{2}\right)=45$
• a=1: 7個を3人に配る。$\left(\genfrac{}{}{0ex}{}{9}{2}\right)=36$
• a=2: 6個を3人に配る。$\left(\genfrac{}{}{0ex}{}{8}{2}\right)=28$

合計 $45+36+28=109$。

検算: 全体は $\left(\genfrac{}{}{0ex}{}{11}{3}\right)=165$ 通り。A が 3 個以上の場合は、A に先に 3 個渡して残り 5 個を 4 人に配ると考え、$\left(\genfrac{}{}{0ex}{}{8}{3}\right)=56$ 通り。したがって $165-56=109$ で一致する。