2023東大理系数学第2問を母関数を使って解く

4403

次の問題を考えてみます．

2023東大理系[2] 改

黒玉3個，赤玉4個，白玉5個を一列に並べるとき，
黒玉どうし，赤玉どうしが隣り合わないように並べる方法の総数はいくらか．

(実際に出題されたのは赤玉が隣り合わないとき黒玉も隣り合わない条件付き確率ですが，やることは同じなので許してください)

黒玉

a

個，赤玉

b

個を同じ色が隣り合わないように並べる方法の総数を

N (a, b)

とする．
白玉5個によって順列は黒or赤のみからなる6個の順列に分割される．よって，

a_{1} + a_{2} + \dots + a_{6} = 3, b_{1} + b_{2} + \dots + b_{6} = 4

なる非負整数の組

(a_{i}, b_{i}) (i = 1, 2, 3, 4, 5, 6)

に対して，

N (a_{1}, b_{1}) N (a_{2}, b_{2}) \dots N (a_{6}, b_{6})

の総和を求めればよい．

ここで，形式的冪級数

f (x, y) = \sum_{a = 0}^{\infty} \sum_{b = 0}^{\infty} N (a, b) x^{a} y^{b}

を用いれば，求める答えは，

{f (x, y)}^{6}

の

x^{3} y^{4}

の係数となる．

黒玉，赤玉を同じ色が隣り合わないように並べるとき，黒・赤は交互に並んでいる必要があるので，

N (a, b) = \begin{array}{r} {\begin{cases} 2, & a = b \geq 1 \\ 1, & a = b = 0 ⋁ | a - b | = 1 \\ 0, & o t h e r w i s e . \end{cases} \end{array}

である．したがって，

f (x, y) = 1 + x + y + 2 x y + x^{2} y + x y^{2} + 2 x^{2} y^{2} + x^{3} y^{2} + x^{2} y^{3} + 2 x^{3} y^{3} + \dots

= (1 + x + y + x y) (1 + x y + x^{2} y^{2} + x^{3} y^{3} + \dots) = \frac{(1 + x) (1 + y)}{1 - x y}

よって，

{f (x, y)}^{6} = \frac{(1 + x)^{6} (1 + y)^{6}}{(1 - x y)^{6}}

を級数展開したときの，

x^{3} y^{4}

の係数を求めれば良い．

まず，

\frac{1}{(1 - X)^{6}}

の各係数を求める．いくつか方法があるが，ここでは微分を用いる．(一般化二項定理を使っても良い)

\frac{1}{1 - X} = \sum_{k = - 5}^{\infty} X^{k + 5}

両辺を5回微分して，

\frac{5!}{{(1 - X)}^{6}} = \sum_{k = 0}^{\infty} (k + 5) (k + 4) \dots (k + 1) X^{k}

∴ \frac{1}{{(1 - X)}^{6}} = \sum_{k = 0}^{\infty} \frac{(k + 5) (k + 4) \dots (k + 1)}{5!} X^{k} = 1 + 6 X + 21 X^{2} + 56 X^{3} + \dots

したがって，

{f (x, y)}^{6} = (1 + x)^{6} (1 + y)^{6} (1 + 6 x y + 21 x^{2} y^{2} + 56 x^{3} y^{3} + \dots)

よって，

{f (x, y)}^{6}

の

x^{3} y^{4}

の係数，すなわち求める値は，

1 \cdot_{6} C_{3} \cdot_{6} C_{4} + 6 \cdot_{6} C_{2} \cdot_{6} C_{3} + 21 \cdot_{6} C_{1} \cdot_{6} C_{2} + 56 \cdot_{6} C_{0} \cdot_{6} C_{1} = 4326

母関数を使うメリットは，頭を使わずに計算だけで答えが出せるという点です．
「代数・解析の計算は慣れてるけど場合の数特有の発想は苦手」という方におすすめです．

投稿日：2023年4月22日

この記事を高評価した人

高評価したユーザはいません

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

148

32537

大学3年生です

コメントはありません。

読み込み中