15
解説高校数学
2023東大理系数学第2問を母関数を使って解く
2474
0
$$$$
$\newcommand{\bino}[1]{{}_6\mathrm{C}_{#1}}$
次の問題を考えてみます．
2023東大理系[2] 改
黒玉3個，赤玉4個，白玉5個を一列に並べるとき，
黒玉どうし，赤玉どうしが隣り合わないように並べる方法の総数はいくらか．
(実際に出題されたのは赤玉が隣り合わないとき黒玉も隣り合わない条件付き確率ですが，やることは同じなので許してください)
母関数を用いた解答
黒玉$a$個，赤玉$b$個を同じ色が隣り合わないように並べる方法の総数を$N(a,b)$とする．
白玉5個によって順列は黒or赤のみからなる6個の順列に分割される．よって，
$$a_1+a_2+\cdots+a_6=3,\ b_1+b_2+\cdots+b_6=4$$
なる非負整数の組$(a_i,b_i) (i=1,2,3,4,5,6)$に対して，
$$N(a_1,b_1)N(a_2,b_2)\ldots N(a_6,b_6)$$
の総和を求めればよい．
ここで，形式的冪級数
$$f\left(x,y\right)=\sum_{a=0}^{\infty}\sum_{b=0}^{\infty}{N\left(a,b\right)x^ay^b}$$
を用いれば，求める答えは，
$\{f(x,y)\}^6$の$x^3 y^4$の係数 となる．
黒玉，赤玉を同じ色が隣り合わないように並べるとき，黒・赤は交互に並んでいる必要があるので，
$$ N(a,b)= \begin{eqnarray} \left\{ \begin{array}{l} 2,&a=b≥1 \\ 1,&a=b=0 ⋁ |a-b|=1\\ 0,&otherwise. \end{array} \right. \end{eqnarray} $$
である．したがって，
$$f(x,y)=1+x+y+2xy+x^2 y+xy^2+2x^2 y^2+x^3 y^2+x^2 y^3+2x^3 y^3+\cdots$$
$$=(1+x+y+xy)(1+xy+x^2 y^2+x^3 y^3+\cdots)=\frac{(1+x)(1+y)}{1-xy}$$
よって，
$$\{f(x,y)\}^6=\frac{(1+x)^6 (1+y)^6}{(1-xy)^6}$$
を級数展開したときの，$x^3 y^4$の係数を求めれば良い．
まず，$\frac1{(1-X)^6}$の各係数を求める．いくつか方法があるが，ここでは微分を用いる．(一般化二項定理を使っても良い)
$$\frac1{1-X}=\sum_{k=-5}^{\infty}X^{k+5}$$
両辺を5回微分して，
$$\frac{5!}{\left(1-X\right)^6}=\sum_{k=0}^{\infty}{\left(k+5\right)\left(k+4\right)\ldots\left(k+1\right)X^k}$$
$$ \therefore \frac{1}{\left(1-X\right)^6}=\sum_{k=0}^{\infty}\frac{\left(k+5\right)\left(k+4\right)\ldots\left(k+1\right)}{5!}X^k =1+6X+21X^2+56X^3+\cdots $$
したがって，
$$\{f(x,y)\}^6=(1+x)^6(1+y)^6(1+6xy+21x^2y^2+56x^3y^3+\cdots)$$
よって，$\{f(x,y)\}^6$の$x^3y^4$の係数，すなわち求める値は，
$$ 1\cdot\bino{3}\cdot\bino{4}+6\cdot\bino{2}\cdot\bino{3}+21\cdot\bino{1}\cdot\bino{2}+56\cdot\bino{0}\cdot\bino{1}=4326 $$
白玉5個によって順列は黒or赤のみからなる6個の順列に分割される．よって，
$$a_1+a_2+\cdots+a_6=3,\ b_1+b_2+\cdots+b_6=4$$
なる非負整数の組$(a_i,b_i) (i=1,2,3,4,5,6)$に対して，
$$N(a_1,b_1)N(a_2,b_2)\ldots N(a_6,b_6)$$
の総和を求めればよい．
ここで，形式的冪級数
$$f\left(x,y\right)=\sum_{a=0}^{\infty}\sum_{b=0}^{\infty}{N\left(a,b\right)x^ay^b}$$
を用いれば，求める答えは，
黒玉，赤玉を同じ色が隣り合わないように並べるとき，黒・赤は交互に並んでいる必要があるので，
$$ N(a,b)= \begin{eqnarray} \left\{ \begin{array}{l} 2,&a=b≥1 \\ 1,&a=b=0 ⋁ |a-b|=1\\ 0,&otherwise. \end{array} \right. \end{eqnarray} $$
である．したがって，
$$f(x,y)=1+x+y+2xy+x^2 y+xy^2+2x^2 y^2+x^3 y^2+x^2 y^3+2x^3 y^3+\cdots$$
$$=(1+x+y+xy)(1+xy+x^2 y^2+x^3 y^3+\cdots)=\frac{(1+x)(1+y)}{1-xy}$$
よって，
$$\{f(x,y)\}^6=\frac{(1+x)^6 (1+y)^6}{(1-xy)^6}$$
を級数展開したときの，$x^3 y^4$の係数を求めれば良い．
まず，$\frac1{(1-X)^6}$の各係数を求める．いくつか方法があるが，ここでは微分を用いる．(一般化二項定理を使っても良い)
$$\frac1{1-X}=\sum_{k=-5}^{\infty}X^{k+5}$$
両辺を5回微分して，
$$\frac{5!}{\left(1-X\right)^6}=\sum_{k=0}^{\infty}{\left(k+5\right)\left(k+4\right)\ldots\left(k+1\right)X^k}$$
$$ \therefore \frac{1}{\left(1-X\right)^6}=\sum_{k=0}^{\infty}\frac{\left(k+5\right)\left(k+4\right)\ldots\left(k+1\right)}{5!}X^k =1+6X+21X^2+56X^3+\cdots $$
したがって，
$$\{f(x,y)\}^6=(1+x)^6(1+y)^6(1+6xy+21x^2y^2+56x^3y^3+\cdots)$$
よって，$\{f(x,y)\}^6$の$x^3y^4$の係数，すなわち求める値は，
$$ 1\cdot\bino{3}\cdot\bino{4}+6\cdot\bino{2}\cdot\bino{3}+21\cdot\bino{1}\cdot\bino{2}+56\cdot\bino{0}\cdot\bino{1}=4326 $$
母関数を使うメリットは，頭を使わずに計算だけで答えが出せるという点です．
「代数・解析の計算は慣れてるけど場合の数特有の発想は苦手」という方におすすめです．
投稿日：4月22日
投稿者
投稿者
この記事を高評価した人
この記事を高評価した人
高評価したユーザはいません
この記事に送られたバッジ
この記事に送られたバッジ
バッジはありません。
コメント
コメント
他の人のコメント
コメントはありません。
読み込み中...
読み込み中