20

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

4403
0


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

2023東大理系[2] 改

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

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

母関数を用いた解答

黒玉a個,赤玉b個を同じ色が隣り合わないように並べる方法の総数をN(a,b)とする.
白玉5個によって順列は黒or赤のみからなる6個の順列に分割される.よって,
a1+a2++a6=3, b1+b2++b6=4
なる非負整数の組(ai,bi)(i=1,2,3,4,5,6)に対して,
N(a1,b1)N(a2,b2)N(a6,b6)
の総和を求めればよい.

ここで,形式的冪級数
f(x,y)=a=0b=0N(a,b)xayb
を用いれば,求める答えは,
{f(x,y)}6x3y4の係数
となる.

黒玉,赤玉を同じ色が隣り合わないように並べるとき,黒・赤は交互に並んでいる必要があるので,
N(a,b)={2,a=b11,a=b=0|ab|=10,otherwise.
である.したがって,
f(x,y)=1+x+y+2xy+x2y+xy2+2x2y2+x3y2+x2y3+2x3y3+
=(1+x+y+xy)(1+xy+x2y2+x3y3+)=(1+x)(1+y)1xy
よって,
{f(x,y)}6=(1+x)6(1+y)6(1xy)6
を級数展開したときの,x3y4の係数を求めれば良い.

まず,1(1X)6の各係数を求める.いくつか方法があるが,ここでは微分を用いる.(一般化二項定理を使っても良い)
11X=k=5Xk+5
両辺を5回微分して,
5!(1X)6=k=0(k+5)(k+4)(k+1)Xk
1(1X)6=k=0(k+5)(k+4)(k+1)5!Xk=1+6X+21X2+56X3+
したがって,
{f(x,y)}6=(1+x)6(1+y)6(1+6xy+21x2y2+56x3y3+)
よって,{f(x,y)}6x3y4の係数,すなわち求める値は,
16C36C4+66C26C3+216C16C2+566C06C1=4326

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

投稿日:2023422
OptHub AI Competition

この記事を高評価した人

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

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

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

投稿者

dragoemon
dragoemon
148
32537
大学3年生です

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中