組合せ
${}_n \mathrm{C} _r$ などを求める。
列挙(パスカルの三角形)
説明
${}_n \mathrm{C} _r = {}_{n-1} \mathrm{C} _{r-1} + {}_{n-1} \mathrm{C} _r$ を利用する。
計算量
前計算 $O(nr)$, クエリ $O(1)$
実装例
列挙(階乗+逆元)
説明
${}_n \mathrm{C} _r = \frac {n!} {(n-r)! r!} = n! ((n-r)!)^{-1} (r!)^{-1}$ を利用する。$n$ までの階乗と階乗の逆元を列挙したあとに, その値を用いて計算する
計算量
前計算 $O(n + \log mod)$, クエリ $O(1)$
実装例
値
説明
${}_n \mathrm{C} _r = \frac {n(n-1)\dots (n-r+1)} {r(r-1)\dots 1}$ を利用する。
計算量
クエリ $O(r)$
実装例
写像 12 相
$n$ 個のボールを $k$ 個の箱に入れる場合の数を, 状況によって以下の $12$ 種類の問題設定に分けることが出来る。
| ボール | 箱 | ボールの入れ方に制限がない | $1$ つの箱に入れられるボールが高々 $1$ 個 | $1$ つの箱に最低 $1$ 個のボールを入れる |
|---|---|---|---|---|
| 区別あり | 区別あり | $k^n$ | ${}_k \mathrm{P} _n$ | $\displaystyle \sum_{i=1}^k(-1)^{k-i}{}_k\mathrm{C}_{i}i^n$ |
| 区別なし | 区別あり | ${}_{k}\mathrm{H}_{n}$ | ${}_k\mathrm{C}_n$ | ${}_{n-1}\mathrm{C}_{k-1}$ |
| 区別あり | 区別なし | $B(n,k)$ | $1$ | $S(n,k)$ |
| 区別なし | 区別なし | ${}_{n+k}\mathrm{P}_{k}$ | $1$ | ${}_{n}\mathrm{P}_{k}$ |
カタラン数
$C_n$ は $n$ 番目のカタラン数である。カタラン数は様々な意味付けがなされていて, 以下にその例をあげる。
- valid な括弧列の個数: $x$ 組の () を正しく並べる個数は $C_x$
- $x+1$ 個の葉を持つ二分木の個数は $C_x$
- 平面グラフの交差: $2x$ 人が手を交差させないで握手する場合の数は $C_x$
カタラン数 $C_n$ の一般項は $C_n = {}_{2n} \mathrm{C} _{n} - {}_{2n} \mathrm{C} _{n-1}$ である。
モンモール数
モンモール数 $a_n$ は長さ $n$ の完全順列の個数である。$n$ 番目に置く数の選び方は $1$ から $n-1$ の $(n-1)$ 通りで, ここで選んだ数を $i$ とする。$i$ 番目に置いた数が $n$ であれば残り $(n-2)$ 個の並べ方の個数は $a_{n-2}$ に等しい。$i$ 番目に置いた数が $n$ でないとき残り $(n-1)$ 個の並べ方の個数は $a_{n-1}$ に等しい。よって漸化式が $a_1 = 0, a_2 = 1, a_n = (n-1)(a_{n-1} + a_{n-2})$ となる。