極限の問題の母関数を使った解法

1842

　この記事では, 以下の問題の解説をしようと思います.

1

〜

n

の数を無作為に並べた時, 大小大小...の順(例えば"51423"等)に並ぶ確率を

p_{n}

とする.
　

lim_{n \to \infty} \frac{p_{n + 1}}{p_{n}}

を求めよ.

漸化式を立てる

　まずは, 漸化式を立てます. このような並べ方の場合の数を $a_{n} (= n! \cdot p_{n})$ とおきます.

　ここで, $n \geq 2$ のとき, 小大小大...の順に並べる方法も同じく $a_{n}$ であることに注意します.(これは各位の数を $n + 1$ から引けばすぐにわかります.)

　 $(n + 1)$ 個の数の並びであって, 「大小大小...」または「小大小大...」となっているものについて考えます. この並びの $(k + 1)$ 番目が $1$ であるとしましょう. すると, $1$ から左向きに見ていくと, 大小大小...の順で $k$ 文字が並んでいて, 同様に右向きに見ていけば, 大小大小...の順で $(n - k)$ 文字が並んでいます.

　これを踏まえれば, $k = 0, 1, \dots, n$ に対して, $(k + 1)$ 番目に $1$ を置き, それより左に入る数を $(\binom{n}{k})$ 通りの中から選んで $a_{k}$ 通りで並べ, 同様に右に入る数を $a_{n - k}$ 通りで並べれば, $2 a_{n + 1}$ 通りの並べ方が再現できることが分かります. (但し, 便宜的に $a_{0} = 1, a_{1} = 1$ とします.)

　従って,

$2 a_{n + 1} = \sum_{k = 0}^{n} (\binom{n}{k}) a_{k} a_{n - k}$

が, $n \geq 1$ で成り立つことが分かりました. これに $a_{n} = n! \cdot p_{n}$ を代入して,
$2 (n + 1) p_{n + 1} = \sum_{k = 0}^{n} p_{k} p_{n - k} (n \geq 1)$
を得ます.

母関数を利用する

　 $f (x) = \sum_{n = 0}^{\infty} p_{n} x^{n}$ とおきます.

　まず,
$\sum_{n = 0}^{\infty} 2 (n + 1) p_{n + 1} x^{n} = 2 f^{'} (x)$
さらに,
$\sum_{n = 0}^{\infty} (\sum_{k = 0}^{n} p_{k} p_{n - k}) x^{n} = f (x)^{2}$
となります.

　これら2式の全ての係数が等しいので...としたいところなのですが, 例の等式は $n \geq 1$ でしか成立せず, 具体的には $n = 0$ のときは右辺に $+ 1$ が必要になります.(つまり, 定数項のみ $+ 1$ が必要になります.) 従って, 係数を比べて,
$2 f^{'} (x) = f (x)^{2} + 1$
が成り立ちます.

微分方程式を解く

　これは基本的な微分方程式になりますね. $2 y^{'} = y^{2} + 1$ の解ですから, 変数分離して $y = \tan (\frac{x}{2} + C)$ のようになります. さらに $f (0) = p_{0} = a_{0} = 1$ ですから $C$ も求まって,
$f (x) = \tan (\frac{x}{2} + \frac{π}{4})$
となります.

極限を求める

　 $f (x)$ の原点から最も近い特異点は $x = \frac{π}{2}$ ですから, このTaylor展開の収束半径は $\frac{π}{2}$ となります. 従って,
$lim_{n \to \infty} \frac{p_{n + 1}}{p_{n}} = \frac{2}{π}$
です.