読書記録『数学ガールの秘密ノート場合の数』☆☆☆☆

確率の話とかは出ずに純粋に場合の数の話
中華料理店などにあるような回転するテーブルが英語で"Lazy Susan"と呼ばれるというトリビアが取り上げられていた(すぐ忘れそう

場合の数はよく考えないと、すぐに間違えるので難しい
取り上げてる内容は以下のような感じ

円順列
数珠順列
パスカルの三角形
ヴェン図
包除原理(3つの集合まで)
カタラン数
第2種スターリング数

カタラン数

カタラン数は以下のようなものなどの場合の数になる

格子上の経路を通り対角線の反対側まで行く対角線を超えない経路の数
対応の取れたn個のカッコを並べる場合の数
n個の分岐を持つ二分木の数

漸化式で表すと以下のようになる(2つの部分に分けてそれぞれの場合の数を独立に計算してかけ合わせたものの総和)
$$C_0 =1, \quad C_{n+1}=\frac{2(2n+1)}{n+2} \, C_n = \sum_{i=0}^{n}C_i\,C_{n-i}$$
一般項は以下のようになる(本の中の計算だと、対角線を考えずに経路を移動する場合の数を考えて、対角線を超えて目的地と鏡合わせの位置に行く場合の数を引いてくる)
$$C_n = {2n \choose n} - {2n \choose n-1 }= \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{(n+1)! \, n!}$$
カタラン数 - Wikipedia
カタラン数の意味と漸化式 | 高校数学の美しい物語

第2種スターリング数

第2種スターリング数はn個の要素をk個のグループに分けるときの場合の数
漸化式は以下のようになる(新しい要素が単独でグループになるときの場合の数 + 新しい要素が既存のグループのどこかに追加されるときの場合の数)
$$S(n, k)=S(n-1, k-1) + kS(n-1, k)$$
一般項は以下のようになる
$$S(n,k)=\dfrac{1}{k!}\displaystyle\sum_{i=1}^k(-1)^{k-i}{}_kC_{i}i^n$$
一般項の導出は以下の記事の説明が分かりやすかった
全射の個数の証明とベル数 | 高校数学の美しい物語

スターリング数 - Wikipedia
スターリング数の漸化式と3つの意味 | 高校数学の美しい物語