この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

離散数学・組合せ論の問題

難易度 4大学院入試の標準レベル大学数学離散数学・組合せ論

$n$ を正の整数とする。座標平面上で、原点 $(0, 0)$ から点 $(2 n, 0)$ まで、1 歩ごとに $(1, 1)$ または $(1, - 1)$ だけ進む経路のうち、途中で $y$ 座標が一度も負にならないものを考える（このような経路をディック経路という）。ディック経路 $P$ に対し、 $P$ が通る点 $(i, 0)$ で $1 \leq i \leq 2 n$ を満たすものの個数を $r (P)$ とする（ $x$ 軸に戻る回数。終点 $(2 n, 0)$ も数える）。

$S_{n} = P \sum r (P)^{2}$

とおく。ただし、和は長さ $2 n$ のディック経路 $P$ すべてにわたってとる。 $S_{n}$ を $n$ の式で表せ。

この問題で使うもの

カタラン数（説明と入口の問題）
畳み込み型の漸化式と母関数の積（説明と入口の問題）
母関数と係数の取り出し（説明と入口の問題）
べき級数と収束半径（説明と入口の問題）

この問題を解けるようになるまで（62 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

ディック経路の母関数 $C (x)$ を最初に $x$ 軸に戻る点での分解から求め、 $x$ 軸に戻る回数ごとに経路を分類した母関数を作りましょう。

ヒント 2

$x$ 軸に戻る回数がちょうど $k$ の経路の母関数は $(x C)^{k}$ です。 $C = 1 + x C^{2}$ から $1 - x C = 1/ C$ が成り立つことを使うと、 $\sum_{k} k^{2} y^{k} = \frac{y ( 1 + y )}{( 1 - y ) ^{3}}$ が簡単になります。

ヒント 3

$\sum_{n} S_{n} x^{n} = x C^{4} + x^{2} C^{5}$ となります。あとは $C = 1 + w$ , $w = x (1 + w)^{2}$ に対するラグランジュの反転公式で $[x^{m}] C^{r} = \frac{r}{2 m + r} (m 2 m + r)$ を求め、2 つの項を $(n 2 n)$ でそろえて足しましょう。

答えと解説

答えを見る

\frac{n ( 13 n - 1 )}{( n + 1 ) ( n + 2 ) ( n + 3 )} (n 2 n)

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

上向きの歩を $U$ 、下向きの歩を $D$ と書く。長さ $2 m$ のディック経路の個数を $c_{m}$ とし（ $c_{0} = 1$ ）、母関数を $C (x) = \sum_{m \geq 0} c_{m} x^{m}$ とする。

1. $C (x)$ の満たす式 長さ $2 m$ ( $m \geq 1$ ) の経路は、最初に $x$ 軸に戻る点で切ると、ただ一通りに $U P_{1} D P_{2}$ （ $P_{1}, P_{2}$ はディック経路）と分解できる。よって $c_{m} = \sum_{k = 0}^{m - 1} c_{k} c_{m - 1 - k}$ であり、
$C = 1 + x C^{2} (1)$
が成り立つ。 $(1)$ を変形すると $C (1 - x C) = 1$ 、すなわち
$1 - x C = \frac{1}{C} . (2)$

2. 戻る回数で分類した母関数 途中で $x$ 軸に触れない（終点でだけ戻る）空でない経路を「既約」とよぶ。既約な経路は $U Q D$ （ $Q$ はディック経路）と一意に書けるので、その母関数は $x C$ である。 $r (P) = k$ の経路は既約な経路 $k$ 個の連結と一意に対応するから、 $r (P) = k$ の経路の母関数は $(x C)^{k}$ である。したがって
$F (x) = n \geq 1 \sum S_{n} x^{n} = k \geq 1 \sum k^{2} (x C)^{k} .$
$\sum_{k \geq 1} k^{2} y^{k} = \frac{y ( 1 + y )}{( 1 - y ) ^{3}}$ に $y = x C$ を代入し、 $(2)$ より $\frac{1}{( 1 - x C ) ^{3}} = C^{3}$ を使うと
$F (x) = x C (1 + x C) C^{3} = x C^{4} + x^{2} C^{5} .$

3. $C^{r}$ の係数（ラグランジュの反転公式） $C = 1 + w$ とおくと、 $(1)$ より $w = x (1 + w)^{2}$ である。 $φ (w) = (1 + w)^{2}$ 、 $H (w) = (1 + w)^{r}$ としてラグランジュの反転公式を使うと、 $m \geq 1$ のとき
$[x^{m}] C^{r} = \frac{1}{m} [w^{m - 1}] H^{'} (w) φ (w)^{m} = \frac{r}{m} [w^{m - 1}] (1 + w)^{2 m + r - 1} = \frac{r}{m} (m - 1 2 m + r - 1) = \frac{r}{2 m + r} (m 2 m + r) .$
この式は $m = 0$ でも値 $1$ を与えるので正しい。

4. 計算 $S_{n} = [x^{n - 1}] C^{4} + [x^{n - 2}] C^{5}$ であり（ $n = 1$ のとき第 2 項は $0$ ）、
$[x^{n - 1}] C^{4} = \frac{4}{2 n + 2} (n - 1 2 n + 2), [x^{n - 2}] C^{5} = \frac{5}{2 n + 1} (n - 2 2 n + 1) .$
これらを $(n 2 n)$ を用いて書き直す。
$(n - 1 2 n + 2) = \frac{( 2 n + 2 ) ( 2 n + 1 ) n}{( n + 1 ) ( n + 2 ) ( n + 3 )} (n 2 n) = \frac{2 ( 2 n + 1 ) n}{( n + 2 ) ( n + 3 )} (n 2 n)$
より、第 1 項は $\frac{4 n ( 2 n + 1 )}{( n + 1 ) ( n + 2 ) ( n + 3 )} (n 2 n)$ となる。
$(n - 2 2 n + 1) = \frac{( 2 n + 1 ) n ( n - 1 )}{( n + 1 ) ( n + 2 ) ( n + 3 )} (n 2 n)$
より、第 2 項は $\frac{5 n ( n - 1 )}{( n + 1 ) ( n + 2 ) ( n + 3 )} (n 2 n)$ となる（ $n = 1$ でも $0$ となり正しい）。

2 つを足すと $4 (2 n + 1) + 5 (n - 1) = 13 n - 1$ なので
$S_{n} = \frac{n ( 13 n - 1 )}{( n + 1 ) ( n + 2 ) ( n + 3 )} (n 2 n) .$

5. 検算 個別に数えた値と比べる。
- $n = 1$ ：経路は $U D$ のみで $S_{1} = 1^{2} = 1$ 。公式も $\frac{12}{24} \cdot 2 = 1$ 。
- $n = 2$ ： $U D U D$ （ $r = 2$ ）、 $U U D D$ （ $r = 1$ ）より $S_{2} = 4 + 1 = 5$ 。公式も $\frac{50}{60} \cdot 6 = 5$ 。
- $n = 3$ ： $r$ の値は $3, 2, 2, 1, 1$ なので $S_{3} = 9 + 4 + 4 + 1 + 1 = 19$ 。公式も $\frac{114}{120} \cdot 20 = 19$ 。

以上より、答えは $\frac{n ( 13 n - 1 )}{( n + 1 ) ( n + 2 ) ( n + 3 )} (n 2 n)$ である。

別解

$r (P) = k$ のディック経路の母関数は、ディック経路の母関数を $C (x)$ として $(x C)^{k}$ である。 $C = 1/ (1 - x C)$ より $1 - x C = 1/ C$ となる。 $u = x C$ とおくと、
$\sum_{k} k^{2} u^{k} = \frac{u ( 1 + u )}{( 1 - u ) ^{3}} = u (1 + u) C^{3} = x C^{4} + x^{2} C^{5}$ 。

ラグランジュの反転公式（既知の結果）により $[x^{n}] C^{m} = \frac{m}{2 n + m} (n 2 n + m)$ である。よって
$S_{n} = \frac{4}{2 n + 2} (n - 1 2 n + 2) + \frac{5}{2 n + 1} (n - 2 2 n + 1)$ 。

階乗で書き直すと、
第1項 $= \frac{4 ( 2 n + 1 )!}{( n - 1 )! ( n + 3 )!}$ 、第2項 $= \frac{5 ( 2 n )!}{( n - 2 )! ( n + 3 )!}$ 。
共通因子 $\frac{( 2 n )!}{( n - 1 )! ( n + 3 )!}$ でくくると $4 (2 n + 1) + 5 (n - 1) = 13 n - 1$ なので、
$S_{n} = \frac{( 13 n - 1 ) ( 2 n )!}{( n - 1 )! ( n + 3 )!}$ 。

検算（直接数え上げ）:
- $n = 1$ : $S_{1} = 1$ 。公式は $12 \cdot 2/ (1 \cdot 24) = 1$ で一致。
- $n = 2$ : 経路は UDUD（ $r = 2$ ）と UUDD（ $r = 1$ ）なので $S_{2} = 4 + 1 = 5$ 。公式も $5$ 。
- $n = 3$ : $r$ の値は $3, 2, 2, 1, 1$ なので $S_{3} = 9 + 4 + 4 + 1 + 1 = 19$ 。公式も $19$ 。
- $n = 4$ : $r = 1, 2, 3, 4$ の経路数は $5, 5, 3, 1$ なので $S_{4} = 5 + 20 + 27 + 16 = 68$ 。公式も $68$ 。

離散数学・組合せ論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題