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

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

難易度 3期末試験の応用レベル大学数学離散数学・組合せ論

集合 ${1, 2, \dots, 10}$ の分割（空でない互いに素なブロックへの分け方。ブロックの順序は区別しない）を考える。分割が非交差であるとは、 $a < b < c < d$ を満たす $a, b, c, d \in {1, \dots, 10}$ で、 $a, c$ が同じブロックに属し、 $b, d$ がそれとは異なる同じブロックに属するようなものが存在しないことをいう。

${1, 2, \dots, 10}$ の非交差分割のうち、どのブロックも 2 個以上の要素を含む（要素 1 個だけのブロックを持たない）ものの個数を求めよ。

この問題で使うもの

カタラン数（説明と入口の問題）
組合せ（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

非交差分割全体の個数はカタラン数 $C_{n}$ で与えられる。全体と「単集合を持たないもの」の関係を作ることを考えよう。

ヒント 2

単集合は交差に関与しないので、非交差分割は「単集合でないブロックに属する要素の集合 $T$ 」と「 $T$ 上の単集合なし非交差分割」の組に対応する。これから $C_{n} = \sum_{k} (k n) R_{k}$ が得られる。

ヒント 3

二項反転により $R_{n} = \sum_{k = 0}^{n} (- 1)^{n - k} (k n) C_{k}$ となる。 $n = 10$ では、偶数番目の項の和は $111897$ になる。

答えと解説

答えを見る

603

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

解説を読む

${1, \dots, n}$ の非交差分割全体の個数はカタラン数 $C_{n} = \frac{1}{n + 1} (n 2 n)$ である（よく知られた事実。要素 1 を含むブロックの最大要素で場合分けすると、 $C_{n + 1} = \sum_{i = 0}^{n} C_{i} C_{n - i}$ というカタラン数の漸化式が得られる）。

${1, \dots, n}$ の非交差分割で要素 1 個のブロック（単集合）を持たないものの個数を $R_{n}$ とおく（ $R_{0} = 1$ ）。

単集合の取り除き・付け加え. 非交差の条件に現れる $a, c$ や $b, d$ はそれぞれ 2 個以上の要素をもつブロックに属するので、単集合は交差に関与しない。よって
- 非交差分割から単集合をすべて取り除いても、残りは非交差のままである。
- 単集合を持たない非交差分割に、任意の単集合を付け加えても非交差のままである。

また、非交差性は要素の大小関係だけで決まるので、 $k$ 元集合 $T \subset {1, \dots, n}$ 上の単集合を持たない非交差分割は、 $T$ を順序を保って ${1, \dots, k}$ に対応させることで、 $R_{k}$ 個あると分かる。

${1, \dots, n}$ の非交差分割は、「単集合でないブロックに属する要素の集合 $T$ （ $∣ T ∣ = k$ ）」と「 $T$ 上の単集合を持たない非交差分割」の組と 1 対 1 に対応する。したがって
$C_{n} = k = 0 \sum n (k n) R_{k} .$

二項反転. この関係から二項反転公式により
$R_{n} = k = 0 \sum n (- 1)^{n - k} (k n) C_{k} .$

計算. $C_{0}, \dots, C_{10}$ は $1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796$ であり、 $(k 10)$ は $1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1$ である。 $n = 10$ のとき符号は $(- 1)^{10 - k} = (- 1)^{k}$ なので、
- $k$ が偶数の項（正）: $1 + 90 + 2940 + 27720 + 64350 + 16796 = 111897$
（ $(0 10) C_{0} = 1$ , $(2 10) C_{2} = 90$ , $(4 10) C_{4} = 2940$ , $(6 10) C_{6} = 27720$ , $(8 10) C_{8} = 64350$ , $(10 10) C_{10} = 16796$ ）
- $k$ が奇数の項（負）: $10 + 600 + 10584 + 51480 + 48620 = 111294$
（ $(1 10) C_{1} = 10$ , $(3 10) C_{3} = 600$ , $(5 10) C_{5} = 10584$ , $(7 10) C_{7} = 51480$ , $(9 10) C_{9} = 48620$ ）

よって
$R_{10} = 111897 - 111294 = 603.$

（検算として、小さい場合は $R_{2} = 1 - 2 + 2 = 1$ , $R_{4} = 1 - 4 + 12 - 20 + 14 = 3$ となる。 $R_{4} = 3$ は ${1234}$ , ${12} {34}$ , ${14} {23}$ の 3 個と一致する。）

答えは $603$ である。

別解

非交差分割のうち要素 1 個だけのブロックを持たないものの個数は、リオルダン数 $R_{n}$ である。 $R_{n}$ は $R_{0} = 1, R_{1} = 0$ と漸化式 $(n + 1) R_{n} = (n - 1) (2 R_{n - 1} + 3 R_{n - 2})$ で決まる。

小さい $n$ での確認として、 $n = 4$ の非交差分割で単独ブロックを持たないものは ${1234}$ 、 ${12∣34}$ 、 ${14∣23}$ の 3 個である。 ${13∣24}$ は交差するので除かれる。これは $R_{4} = 3$ と一致する。

漸化式から順に求める。
$R_{2} = 1, R_{3} = 1, R_{4} = 3, R_{5} = 6, R_{6} = 15, R_{7} = 36, R_{8} = 91, R_{9} = 232$ 。

$n = 10$ では
$11 R_{10} = 9 (2 \cdot 232 + 3 \cdot 91) = 9 \cdot 737 = 6633$
より $R_{10} = 603$ 。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題