上: 生成関数の方法 前: カタラン数を生成関数で求める

ある入試問題の一般化への生成関数の活用

南海　 まず98年の京大の入試問題と その一般化を紹介しよう．このときは史織さんが考えてくれた．

例 1.3.3       ［98年京大前期文理］

袋に青色，赤色，白色の形の同じ玉がそれぞれ 3 個ずつ入っている． 各色の 3 個の玉にはそれぞれ 1 , 2 , 3 の番号がついている． これらの 9 個の玉をよくかきまぜて袋から同時に 3 個の玉を取り出す．取り出した 3 個のうちに同 色のものが他になく，同番号のものも他にない玉の個数を得点とする． たとえば，青1番，赤1番，白3番を取り出したときの得点は 1 で，青2番，赤2番，赤3番を 取り出したときの得点は 0 である。このとき以下の問に答えよ．

1. 得点が $n$ になるような取り出し方の数を $A(n)$ とするとき， $A(0)，A(1)，A(2)，A(3)$ を求めよ．
2. 得点の期待値を求めよ．

例 1.3.4 (問題の一般化)        袋に， $k$ 種の色でぬられた同じ形の玉が $k$ 個ずつ $k^2$ 個入っている． 各色の $k$ 個の玉には 1 から $k$ まで番号がついている．ここから同時に$k$個の玉を取り出す．

$k$ 個のうち同色のものが他になく、同番号のものも他にない玉の個数を得点とする．

点が $n$ になるような取り出し方の総数を $f_k(n)$とする．

1. $f_k(n)$をもとめる一般的な方法を求め， $f_4(0)，f_5(0)$を求めよ．
2. $f_k(n)$を $n$ と $k$ の式で表すことはできるか．
3. 得点の期待値を $k$ の式で表すことはできるか．

史織　 $f_k(n)$について考えると，次のように$f_k(0)$の漸化式が得られました．

1. まず$k^2$個の中から一つ選ぶ． 次に最初に選ばれたものと色か番号が一致するものを除いた$(k-1)^2$個の中から一つとる． 以下順次 $n$ 個目を$(k-n+1)^2$個から一つ選ぶまでとる． この $n$ 個の取り方は，取り出す順序に関係ないから$n!$で割って，
   
   $$\dfrac{k^2\cdot(k-1)^2\cdot \cdots \cdot (k-n+1)^2}{n!}=n! \,({}_kC_n)^2$$
   
   

2. 残る$k-n$個は互いに同色同番があるような選び方だから，$f_{k-n}(0)$通り．
3. よって，
   
   $$f_k(n)=n! \, ({}_kC_n)^2 \cdot f_{k-n}(0)$$
   
   
   である．すべての選び方は${}_{k^2}C_k$通りだから，$f_k(0)$の漸化式
   
   $${}_{k^2}C_k=\sum_{n=0}^k n! \cdot ({}_kC_n)^2 \cdot f_{k-n}(0)$$
   
   
   が成り立つ．最初の条件は，$f_0(0)=1$である．

史織　 ところで，この漸化式は解けるのですか．

南海　 それが問題だ．少しでも前進しなければならない． できているところまで話そう．

$${}_{k^2}C_k =\sum_{n=0}^k n! \cdot ({}_kC_n)^2 \cdot f_{k-n}... ...{n=0}^k\dfrac{(k!)^2}{n!} \cdot \dfrac{f_{k-n}(0)}{((k-n)!)^2}$$

である．つまり，

$$\dfrac{{}_{k^2}C_k}{(k!)^2} =\sum_{n=0}^k\dfrac{1}{n!} \cdot \dfrac{f_{k-n}(0)}{((k-n)!)^2} \quad \cdots (*)$$

ここで， $a_{k-n}= \dfrac{f_{k-n}(0)}{((k-n)!)^2}$と置こう． そして次の二つの無限級数を考える．

$$\begin{eqnarray*} U(t)&=&\sum_{n=0}^{\infty}a_n\,t^n\\ V(t)&=&\sum_{n=0}^{\infty}\dfrac{1}{n!}t^n \end{eqnarray*}$$

すると

$$U(t)\cdot V(t)=\sum_{k=0}^{\infty}\left(\sum_{n=0}^k\dfrac{1}{n!}a_{k-n}\right)t^k$$

である．漸化式$(*)$はこれが

$$\sum_{k=0}^{\infty}\dfrac{{}_{k^2}C_k}{(k!)^2}t^k$$

となることを意味している． ところが$V(t)=e^t$で， さらに $$e^{-t}=\sum_{n=0}^{\infty}\dfrac{1}{n!}(-t)^n$$ であるから，

$$\begin{eqnarray*} U(t)&=&e^{-t}\sum_{k=0}^{\infty}\dfrac{{}_{k^2}C_k}{(k!)^2}t^k... ...1)^{k-j}\dfrac{1}{(k-j)!} \dfrac{{}_{j^2}C_j}{(j!)^2} \right)t^k \end{eqnarray*}$$

$t^k$の係数を比較して，

$$\begin{eqnarray*} f_k(0)=a_k(k!)^2 &=&\sum_{j=0}^k(-1)^{k-j}\frac{k!}{(k-j)!j!} ... ...j=0}^k(-1)^{k-j} \,{}_kC_j \,\cdot {}_kP_{k-j} \cdot {}_{j^2}C_j \end{eqnarray*}$$

史織　 わー，解けてる．ためしてみます．

$$\begin{eqnarray*} f_4(0) &=&(-1)^4\,{}_4C_0\,{}_4P_4\,{}_0C_0+(-1)^3\,{}_4C_1\,{... ..._0\,{}_{25}C_5\\ &=&-120+600-3600+16800-45500+53130\\ &=&21310 \end{eqnarray*}$$

南海　 期待値は求まる．

$$\begin{eqnarray*} n f_k(n)&=&n\cdot {}_kP_ n\cdot {}_kC_n \cdot f_{k-n}(0)\\ &=... ...-1}\cdot {}_{k-1}C_{n-1}\cdot f_{k-n}(0)\\ &=&k^2\ f_{k-1}(n-1) \end{eqnarray*}$$

である．ゆえに

$$\begin{eqnarray*} \sum_{n=0}^k n f_k(n)&=&k^2\,\sum_{n=0}^{k-1}f_{k-1}(n)\\ &=&k^2\ {}_{(k-1)^2}C_{k-1} \end{eqnarray*}$$

したがって求める期待値は

$$\dfrac{k^2\,\,{}_{(k-1)^2} C_{k-1}}{{}_{k^2}C_k}$$

である．

南海　 これが生成関数の方法で， 数列を求めるのに大変強力な方法なのだ． この先は，上に現れた関数の満たす関係を求めなければならず，それはできていない．

京大の問題は生成関数まで使わせてくれたという意味で大変良い問題だった．

上: 生成関数の方法 前: カタラン数を生成関数で求める