catalan_number

<h2>括弧と括弧閉じが正しく並ぶ場合の数</h2>
<p>
二つの文字、括弧と括弧閉じ「()」を \(n\) ペア並べるものとする。
すべての並び方の場合の数のうち、括弧と括弧閉じが正しく並ぶ場合の数とその割合を求めよ。
</p>
<h3>括弧と括弧閉じを並べる場合の数</h3>
<div class="card">
  <div class="card-body">
    <h4 class="card-title">同じものを含む順列</h4>
    <h5 class="card-subtitle mb-2 text-muted">組み合わせの積に等しい</h5>
    <p class="card-text">
同じものの個数 \(p_1, p_2, \cdots, p_m\) で表されるものをすべて並べる場合の数は以下のように表される。
\[
\frac{(\sum_{i=1}^{m}p_i)!}{\prod_{i=1}^{m}p_i!}
= \prod_{i=1}^{m}\dbinom{\sum_{j=i}^{m}p_j}{p_i}
\]
さらに、順列と組み合わせの記号に置き換えれば：
\[
\frac{\permu{\sum_{i=1}^{m}p_i}{\sum_{i=1}^{m}p_i}}{\prod_{i=1}^{m}\permu{i}{i}}
= \prod_{i=1}^{m}\combi{\sum_{j=i}^{m}p_j}{p_i}
\]
このままでは理解が難しいので、\(m=3\) として同じものの個数 \(p, q, r\) で表されるものをすべて並べる場合の数は以下の通りである。
\[
\frac{(p+q+r)!}{p!q!r!} = \dbinom{p+q+r}{p}\cdot\dbinom{q+r}{q}\cdot\dbinom{r}{r}
\]
\[
\frac{\permu{p+q+r}{p+q+r}}{\permu{p}{p}\cdot\permu{q}{q}\cdot\permu{r}{r}}
= \combi{p+q+r}{p}\cdot\combi{q+r}{q}\cdot\combi{r}{r}
\]
つまり、左辺は、分子「同じものを区別しない場合の順列の場合の数」を分母「重複度、つまり、同じものを並べた場合の順列の場合の数の総積」で割ることを意味している。一方で、右辺は、空いている並びの位置に同じものを割り当てる組み合わせの場合の数の総積を意味している。
    </p>
  </div>
</div>
<p>
\(n\) ペアの括弧括弧閉じとは同じものの個数 \(n, n\) で表されるものを並べる場合の数である。\(\combi{n}{n} = \binom{n}{n} = 1\) により、先の式に当てはめれば：
\[
\begin{aligned}
\frac{\permu{2n}{2n}}{n!n!} &= \combi{2n}{n}\\
\frac{(2n)!}{n!n!} &= \dbinom{2n}{n}
\end{aligned}
\]
例えば、\(n=1\) のとき：
\[
\begin{aligned}
\frac{(2\cdot 1)!}{1!1!} &= \frac{2}{1\cdot 1} &= 2\\
\dbinom{2\cdot 1}{1} &&= 2\\
\end{aligned}
\]
<div class="container-fluid">
  <div class="row">
    <div class="col-12">
<ol>
<li>()</li>
<li>)(</li>
</ol>
    </div>
  </div>
</div>
例えば、\(n=2\) のとき：
\[
\begin{aligned}
\frac{(2\cdot 2)!}{2!2!} &= \frac{24}{2\cdot 2} &= 6\\
\dbinom{2\cdot 2}{2} &&= 6\\
\end{aligned}
\]
<div class="container-fluid">
  <div class="row">
    <div class="col-12">
<ol>
<li>(())</li>
<li>()()</li>
<li>())(</li>
<li>)(()</li>
<li>)()(</li>
<li>))((</li>
</ol>
    </div>
  </div>
</div>
例えば、\(n=3\) のとき：
\[
\begin{aligned}
\frac{(2\cdot 3)!}{3!3!} &= \frac{720}{6\cdot 6} &= 20\\
\dbinom{2\cdot 3}{3} &&= 20\\
\end{aligned}
\]
<div class="container-fluid">
  <div class="row">
    <div class="col-6">
<ol>
<li>((()))</li>
<li>(()())</li>
<li>(())()</li>
<li>(()))(</li>
<li>()(())</li>
<li>()()()</li>
<li>()())(</li>
<li>())(()</li>
<li>())()(</li>
<li>()))((</li>
</ol>
    </div>
    <div class="col-6">
<ol start="11">
<li>)((())</li>
<li>)(()()</li>
<li>)(())(</li>
<li>)()(()</li>
<li>)()()(</li>
<li>)())((</li>
<li>))((()</li>
<li>))(()(</li>
<li>))()((</li>
<li>)))(((</li>
</ol>
    </div>
  </div>
</div>
<ol>
</ol>
例えば、\(n=4\) のとき：
\[
\begin{aligned}
\frac{(2\cdot 4)!}{4!4!} &= \frac{40320}{24\cdot 24} &= 70\\
\dbinom{2\cdot 4}{4} &&= 70\\
\end{aligned}
\]
<div class="container-fluid">
  <div class="row">
    <div class="col-3">
<ol>
<li>(((())))</li>
<li>((()()))</li>
<li>((())())</li>
<li>((()))()</li>
<li>((())))(</li>
<li>(()(()))</li>
<li>(()()())</li>
<li>(()())()</li>
<li>(()()))(</li>
<li>(())(())</li>
<li>(())()()</li>
<li>(())())(</li>
<li>(()))(()</li>
<li>(()))()(</li>
<li>(())))((</li>
</ol>
    </div>
    <div class="col-3">
<ol start="16">
<li>()((()))</li>
<li>()(()())</li>
<li>()(())()</li>
<li>()(()))(</li>
<li>()()(())</li>
<li>()()()()</li>
<li>()()())(</li>
<li>()())(()</li>
<li>()())()(</li>
<li>()()))((</li>
<li>())((())</li>
<li>())(()()</li>
<li>())(())(</li>
<li>())()(()</li>
<li>())()()(</li>
<li>())())((</li>
<li>()))((()</li>
<li>()))(()(</li>
<li>()))()((</li>
<li>())))(((</li>
</ol>
    </div>
    <div class="col-3">
<ol start="36">
<li>)(((()))</li>
<li>)((()())</li>
<li>)((())()</li>
<li>)((()))(</li>
<li>)(()(())</li>
<li>)(()()()</li>
<li>)(()())(</li>
<li>)(())(()</li>
<li>)(())()(</li>
<li>)(()))((</li>
<li>)()((())</li>
<li>)()(()()</li>
<li>)()(())(</li>
<li>)()()(()</li>
<li>)()()()(</li>
<li>)()())((</li>
<li>)())((()</li>
<li>)())(()(</li>
<li>)())()((</li>
<li>)()))(((</li>
</ol>
    </div>
    <div class="col-3">
<ol start="56">
<li>))(((())</li>
<li>))((()()</li>
<li>))((())(</li>
<li>))(()(()</li>
<li>))(()()(</li>
<li>))(())((</li>
<li>))()((()</li>
<li>))()(()(</li>
<li>))()()((</li>
<li>))())(((</li>
<li>)))(((()</li>
<li>)))((()(</li>
<li>)))(()((</li>
<li>)))()(((</li>
<li>))))((((</li>
</ol>
    </div>
  </div>
</div>
</p>
<h3 style="page-break-before: always;">括弧と括弧閉じを正しく並べる場合の数</h3>
<div class="card">
  <div class="card-body">
    <h4 class="card-title">カタラン数</h4>
    <h5 class="card-subtitle mb-2 text-muted">\(c_n\)</h5>
    <p class="card-text">
カタラン数 \(c_n\) は以下のように表される。
\[
c_n = \frac1{n+1}\dbinom{2n}{n} = \dbinom{2n}{n} - \dbinom{2n}{n-1}
\]
これは、パスカルの三角形で確認してみるとよい。さらに、以下の二項係数の階乗表示：
\[
\dbinom{n}{k} = \frac{n!}{k!(n-k)!}
\]
を用いて以下のように確認できる。\(n! = n(n-1)!\) や \((n+1)! = (n+1)n!\) を利用すると簡単である。
\[
\begin{aligned}
\dbinom{2n}{n} - \dbinom{2n}{n-1}
&= \frac{(2n)!}{n!(2n-n)!} - \frac{(2n)!}{(n-1)!(2n-(n-1))!}\\
&= \frac{(2n)!}{n!(2n-n)!} - \frac{n(2n)!}{n(n-1)!(2n-n+1)!}\\
&= \frac{(2n)!}{n!(2n-n)!} - \frac{n(2n)!/(2n-n+1)}{n!(2n-n)!}\\
&= \frac{(1 - n/(n+1))(2n)!}{n!(2n-n)!}\\
&= \frac1{n+1}\frac{(2n)!}{n!(2n-n)!} = \frac1{n+1}\dbinom{2n}{n}\\
\end{aligned}
\]
    </p>
    <p class="card-text">
カタラン数 \(c_n\) は以下の漸化式で表すことができる。
\[
\begin{aligned}
c_0 &= 1\\
c_{n+1} &= \frac{2(2n+1)}{n+2}c_n\\
&= \sum_{i=0}^{n}c_ic_{n-i}
\end{aligned}
\]
導出は高度なので他に譲る。
    </p>
  </div>
</div>
<p>
先の話題に戻すと、結論からすると、「括弧と括弧閉じが正しく並ぶ場合の数」はすべての場合の数から「括弧と括弧閉じが正しく並ばない場合の数」を引いた数、もしくは、すべての場合の数を「\(n\) ペアに \(1\) 加えた \(n+1\)」で割った数をあらわしている。よって、割合は \(\frac1{n+1}\) となる。
</p>
<p>
例えば、\(n=1\) のとき：
\[
\begin{aligned}
\dbinom{2\cdot 1}{1} - \dbinom{2\cdot 1}{1 -1} &= 2 - 1 &= 1\\
\frac1{1+1}\dbinom{2\cdot 1}{1} &= \frac1{2}2 &= 1\\
\end{aligned}
\]
<div class="container-fluid">
  <div class="row">
    <div class="col-12">
<ol>
<li>()</li>
</ol>
    </div>
  </div>
</div>
例えば、\(n=2\) のとき：
\[
\begin{aligned}
\dbinom{2\cdot 2}{2} - \dbinom{2\cdot 2}{2-1} &= 6 - 4 &= 2\\
\frac1{2+1}\dbinom{2\cdot 2}{2} &= \frac1{3}6 &= 2\\
\end{aligned}
\]
<div class="container-fluid">
  <div class="row">
    <div class="col-12">
<ol>
<li>(())</li>
<li>()()</li>
</ol>
    </div>
  </div>
</div>
例えば、\(n=3\) のとき：
\[
\begin{aligned}
\dbinom{2\cdot 3}{3} - \dbinom{2\cdot 3}{3-1} &= 20 - 15 &= 5\\
\frac1{3+1}\dbinom{2\cdot 3}{3} &= \frac1{4}20 &= 5\\
\end{aligned}
\]
<div class="container-fluid">
  <div class="row">
    <div class="col-12">
<ol>
<li>((()))</li>
<li>(()())</li>
<li>(())()</li>
<li>()(())</li>
<li>()()()</li>
</ol>
    </div>
  </div>
</div>
例えば、\(n=4\) のとき：
\[
\begin{aligned}
\dbinom{2\cdot 4}{4} - \dbinom{2\cdot 4}{4-1} &= 70 - 56 &= 14\\
\frac1{4+1}\dbinom{2\cdot 4}{4} &= \frac1{5}70 &= 14\\
\end{aligned}
\]
<div class="container-fluid">
  <div class="row">
    <div class="col-4">
<ol>
<li>(((())))</li>
<li>((()()))</li>
<li>((())())</li>
<li>((()))()</li>
</ol>
    </div>
    <div class="col-4">
<ol start="5">
<li>(()(()))</li>
<li>(()()())</li>
<li>(()())()</li>
<li>(())(())</li>
<li>(())()()</li>
</ol>
    </div>
    <div class="col-4">
<ol start="10">
<li>()((()))</li>
<li>()(()())</li>
<li>()(())()</li>
<li>()()(())</li>
<li>()()()()</li>
</ol>
    </div>
  </div>
</div>
</p>
<h3>カタラン数の例</h3>
<p>
カタラン数 \(c_n\) は例えば他に以下を表す。
<ul>
<li>縦横 \(n\times n\) マスの格子において左下隅から右上隅まで対角線を超えずに進む最短経路の数</li>
<li>\(n+1\) チームによるトーナメント表の種類の数（試合数 \(n\) ではない）</li>
<li>\(n+1\) 枚の葉による二分木の種類の数</li>
<li>\(n+1\) 変数の積の順序の種類の数</li>
<li>凸 \(n+2\) 角形に対角線を \(n-1\) 本引いて三角形に分割する種類の数</li>
</ul>
</p>
<p>
一般に、縦横 \(n\times m\) マスの格子にて左下隅から右上隅まで進む最短経路の数は 
\[
\frac{(n+m)!}{n!m!} = \binom{n+m}{n} = \binom{n+m}{m}
\]
で与えられる。\(n=m\) なら、\(\frac{(2n)!}{n!n!} = \binom{2n}{n}\) である。このうち、対角線を超えるような最短経路の数は、縦横 \((n-1)\times(n+1)\) マスの格子にて左下隅から右上隅まで進む最短経路の数に等しい。よって、これらの差が、縦横 \(n\times n\) マスの格子において左下隅から右上隅まで対角線を超えずに進む最短経路の数となる。
\[
\binom{2n}{n} - \binom{(n+1)+(n-1)}{n-1}
= \binom{2n}{n} - \binom{2n}{n-1} = c_n
\]
</p>
<p>
トーナメント表で考えれば、優勝 \(1\) チームの左側が \(i\) チームによる \(c_i\) 種類、右側が \(n-i\) チームによる \(c_{n-i}\) 種類で、乗じて \(c_ic_{n-i}\) 種類。これの \(i=0\) から \(n\) までの総和がカタラン数の漸化式である。
</p>
<p>
変数の積の順序は、変数の並びは変えずに \((n+1)-1\) 個の各変数間に \(n\) 組みの括弧括弧閉じのどちらかを正しく挿入すること、つまり本題と等価である。
</p>
 <p>
形は変えども基本的にペアに関する問題設定なので、すべて同等である。実際に問題では、マス数、チーム数、枚数、変数の数、頂点の数などの \(n\) のズレに気をつければよい。
</p>