二項係数

<p>
二項係数は、日本の初等教育では \({}_n\mathrm{C}_k\) のように表され、これは \(\dbinom{n}{k}\) に等しい。
</p>
<h3>二項係数の性質</h3>
<p>
\[
\dbinom{n}{0} = \dbinom{n}{n} = 1
\]
\[
\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}
\]
上式はパスカルの三角形の端がすべて \(1\) であることを表し、下式はそれ以外の\((n, k)\)の数がパスカルの三角形の一つ前の次数の左\((n-1, k-1)\)と右\((n-1, k)\)の数の和であることを表している。
\[
\dbinom{n}{k} = \dbinom{n}{n-k}
\]
上式はパスカルの三角形が左右対称であることを表している。
\[
k\dbinom{n}{k} = n\dbinom{n-1}{k-1}
\]
上式は\((n,k)\)の数の \(k\) 倍がパスカルの三角形の一つ前の次数の左\((n-1, k-1)\)の数の \(n\) 倍に等しいことを表している。
\[
\sum_{k=0}^n\dbinom{n}{k} = 2^n
\]
上式はパスカルの三角形で各行における総和が \(2\) の整数冪であることを表している。
\[
\sum_{k=0}^n\dbinom{n}{k}(-1)^k = 0
\]
上式はパスカルの三角形で各行における交代総和が零であることを表している。
</p>
<p>
<table class="table-bordered" style="font-family: monospace; table-layout: fixed; width: 24rem;">
<caption class="text-center">パスカルの三角形（二項係数）</caption>
<thead style="text-align: right;">
<tr><th>\(n\)\\(k\)</th><th> 0</th><th> 1</th><th> 2</th><th> 3</th><th> 4</th><th> 5</th><th> 6</th><th> 7</th><th> 8</th><th> 9</th></tr>
</thead>
<tbody style="text-align: right;">
<tr><th>0</th><td>1</td></tr>
<tr><th>1</th><td>1</td><td>1</td></tr>
<tr><th>2</th><td>1</td><td>2</td><td>1</td></tr>
<tr><th>3</th><td>1</td><td>3</td><td>3</td><td>1</td></tr>
<tr><th>4</th><td>1</td><td>4</td><td>6</td><td>4</td><td>1</td></tr>
<tr><th>5</th><td>1</td><td>5</td><td>10</td><td>10</td><td>5</td><td>1</td></tr>
<tr><th>6</th><td>1</td><td>6</td><td>15</td><td>20</td><td>15</td><td>6</td><td>1</td></tr>
<tr><th>7</th><td>1</td><td>7</td><td>21</td><td>35</td><td>35</td><td>21</td><td>7</td><td>1</td></tr>
<tr><th>8</th><td>1</td><td>8</td><td>28</td><td>56</td><td>70</td><td>56</td><td>28</td><td>8</td><td>1</td></tr>
<tr><th>9</th><td>1</td><td>9</td><td>36</td><td>84</td><td>126</td><td>126</td><td>84</td><td>36</td><td>9</td><td>1</td></tr>
</tbody>
</table>
</p>
<h3>二項係数の階乗表示</h3>
<p>
\[
\dbinom{n}{k} = \frac{n!}{k!(n-k)!}
\]
これを用いて、性質の式を確かめるとよい。
</p>
<div class="accordion" id="accordionOne" style="page-break-before: always;">
  <div class="card">
    <div class="card-header" id="accordionOneHeadingOne">
      <h5 class="mb-0">
        <button class="btn btn-link collapsed" type="button" data-toggle="collapse" data-target="#accordionOneCollapseOne" aria-expanded="false" aria-controls="accordionOneCollapseOne">
\(\binom{n}{k} = \binom{n}{n-k}\) の確認
        </button>
      </h5>
    </div>
    <div id="accordionOneCollapseOne" class="collapse _show border-bottom" aria-labelledby="accordionOneHeadingOne" data-parent="#accordionOne">
      <div class="card-body">
<p>
\[
\begin{aligned}
\dbinom{n}{k} &= \frac{n!}{k!(n-k)!} = \frac{n!}{(n-k)!k!}\\
&= \frac{n!}{(n-k)!(n-(n-k))!} = \dbinom{n}{n-k}\\
\dbinom{n}{n-k} &= \frac{n!}{(n-k)!(n-(n-k))!}= \frac{n!}{k!(n-k)!} = \dbinom{n}{k}\\
\end{aligned}
\]
どちらかで示せばよいので、断然後者の方が簡単である。
</p>
      </div>
    </div>
  </div>
</div>
<div class="accordion" id="accordionTwo">
  <div class="card">
    <div class="card-header" id="accordionTwoHeadingTwo">
      <h5 class="mb-0">
        <button class="btn btn-link collapsed" type="button" data-toggle="collapse" data-target="#accordionTwoCollapseTwo" aria-expanded="false" aria-controls="accordionTwoCollapseTwo">
\(\binom{n}{0} = \binom{n}{n} = 1, \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) の確認
        </button>
      </h5>
    </div>
    <div id="accordionTwoCollapseTwo" class="collapse _show border-bottom" aria-labelledby="accordionTwoHeadingTwo" data-parent="#accordionTwo">
      <div class="card-body">
<p>
\[
\dbinom{n}{0} = \frac{n!}{0!(n-0)!} = \frac{n!}{n!} = 1
\]
\[
\dbinom{n}{n} = \frac{n!}{n!(n-n)!} = \frac{n!}{n!} = 1
\]
\(\binom{n}{k} = \binom{n}{n-k}\) が既知ならどちらかを示して、\(\binom{n}{0} = \binom{n}{n-0}\) を使えばよい。
\[
\begin{aligned}
\binom{n-1}{k-1} + \binom{n-1}{k}
&= \frac{(n-1)!}{(k-1)!((n-1)-(k-1))!} + \frac{(n-1)!}{k!((n-1)-k)!}\\
&= \frac{k(n-1)!}{k!(n-k)!} + \frac{(n-k)(n-1)!}{k!(n-k)!}\\
&= \frac{n(n-1)!}{k!(n-k)!} = \frac{n!}{k!(n-k)!} = \dbinom{n}{k}\\
\end{aligned}
\]
\(j(j-1)! = j!\) であることを利用して分母を揃えればよい。 
</p>
      </div>
    </div>
  </div>
</div>
<div class="accordion" id="accordionThree">
  <div class="card">
    <div class="card-header" id="accordionThreeHeadingThree">
      <h4 class="mb-0">
        <button class="btn btn-link collapsed" type="button" data-toggle="collapse" data-target="#accordionThreeCollapseThree" aria-expanded="false" aria-controls="accordionThreeCollapseThree">
\(k\binom{n}{k} = n\binom{n-1}{k-1}\) の確認
        </button>
      </h5>
    </div>
    <div id="accordionThreeCollapseThree" class="collapse _show border-bottom" aria-labelledby="accordionThreeHeadingThree" data-parent="#accordionThree">
      <div class="card-body">
<p>
\[
\begin{aligned}
k\binom{n}{k}
&= \frac{kn!}{k!(n-k)!} = \frac{n(n-1)!}{(k-1)!(n-k)!}\\
&= \frac{n(n-1)!}{(k-1)!(n-1-(k-1))!} = n\binom{n-1}{k-1}\\
n\binom{n-1}{k-1}
&= \frac{n(n-1)!}{(k-1)!(n-1-(k-1))!}\\
&= \frac{kn!}{k!(n-k)!} = k\binom{n}{k}
\end{aligned}
\]
どちらかで示せばよいので、断然後者の方が簡単である。
</p>
      </div>
    </div>
  </div>
</div>
<div class="accordion" id="accordionFour">
  <div class="card">
    <div class="card-header" id="accordionFourHeadingFour">
      <h4 class="mb-0">
        <button class="btn btn-link collapsed" type="button" data-toggle="collapse" data-target="#accordionFourCollapseFour" aria-expanded="false" aria-controls="accordionFourCollapseFour">
\(\sum_{k=0}^n\binom{n}{k} = 2^n\) の確認
        </button>
      </h5>
    </div>
    <div id="accordionFourCollapseFour" class="collapse _show border-bottom" aria-labelledby="accordionFourHeadingFour" data-parent="#accordionFour">
      <div class="card-body">
<p>
二項定理の公式：
\[
(x + y)^n = \sum_{k=0}^{n}\dbinom{n}{k}x^{n-k}y^k
\]
ここで、\(x=1, y=1\) とすればよい。
\[
\begin{aligned}
(1+1)^n &= \sum_{k=0}^{n}\dbinom{n}{k}1^{n-k}1^k\\
2^n &= \sum_{k=0}^{n}\dbinom{n}{k}\\
\end{aligned}
\]
</p>
      </div>
    </div>
  </div>
</div>
<div class="accordion" id="accordionFive">
  <div class="card">
    <div class="card-header" id="accordionFiveHeadingFive">
      <h4 class="mb-0">
        <button class="btn btn-link collapsed" type="button" data-toggle="collapse" data-target="#accordionFiveCollapseFive" aria-expanded="false" aria-controls="accordionFiveCollapseFive">
\(\sum_{k=0}^n\binom{n}{k}(-1)^k = 0\) の確認
        </button>
      </h5>
    </div>
    <div id="accordionFiveCollapseFive" class="collapse _show border-bottom" aria-labelledby="accordionFiveHeadingFive" data-parent="#accordionFive">
      <div class="card-body">
<p>
二項定理の公式：
\[
(x + y)^n = \sum_{k=0}^{n}\dbinom{n}{k}x^{n-k}y^k
\]
ここで、\(x=1, y=-1\) とすればよい。
\[
\begin{aligned}
(1-1)^n &= \sum_{k=0}^{n}\dbinom{n}{k}1^{n-k}(-1)^k\\
0 &= \sum_{k=0}^{n}\dbinom{n}{k}(-1)^k\\
\end{aligned}
\]
</p>
      </div>
    </div>
  </div>
</div>
<hr/>
<h2 style="page-break-before: always;">二項係数の添え字の操作</h2>
<p>
添え字が１つズレた二項係数を係数を掛けてズレを直す。
\[
\begin{aligned}
\dbinom{n-1}{k-1}
&%= \frac{(n-1)!}{(k-1)!(n-k)!}
= \frac{kn(n-1)!}{nk(k-1)!(n-k)!}
%= \frac{k}{n}\frac{n!}{k!(n-k)!}
= \frac{k}{n}\dbinom{n}{k}\\
\dbinom{n+1}{k+1}
&= \frac{(n+1)!}{(k+1)!(n-k)!}
= \frac{n+1}{k+1}\frac{n!}{k!(n-k)!}
= \frac{n+1}{k+1}\dbinom{n}{k}\\
%
\dbinom{n}{k-1}
&%= \frac{n!}{(k-1)!(n-k+1)!}
= \frac{kn!}{k(k-1)!(n-k+1)(n-k)!}
%= \frac{k}{n-k+1}\frac{n!}{k!(n-k)!}
= \frac{k}{n-k+1}\dbinom{n}{k}\\
\dbinom{n}{k+1}
&%= \frac{n!}{(k+1)!(n-k-1)!}
= \frac{(n-k)n!}{(k+1)k!(n-k)(n-k-1)!}
%= \frac{n-k}{k+1}\frac{n!}{k!(n-k)!}
= \frac{n-k}{k+1}\dbinom{n}{k}\\
%
\dbinom{n-1}{k}
&%= \frac{(n-1)!}{k!(n-k-1)!}
= \frac{(n-k)n(n-1)!}{nk!(n-k)(n-k-1)!}
%= \frac{n-k}{n}\frac{n!}{k!(n-k)!}
= \frac{n-k}{n}\dbinom{n}{k}\\
\dbinom{n+1}{k}
&%= \frac{(n+1)!}{k!(n-k+1)!}
= \frac{(n+1)n!}{k!(n-k+1)(n-k)!}
%= \frac{n+1}{n-k+1}\frac{n!}{k!(n-k)!}
= \frac{n+1}{n+1-k}\dbinom{n}{k}
\end{aligned}
\]
すべては覚える必要はない。なぜなら、
\[
\begin{aligned}
\frac{n}{k}\dbinom{n-1}{k-1}
&= \dbinom{n}{k}\\
\frac{n-k+1}{k}\dbinom{n}{k-1}
&= \dbinom{n}{k}\\
\frac{n}{n-k}\dbinom{n-1}{k}
&= \dbinom{n}{k}\\
\end{aligned}
\]
ここで、\(n-1\to n\) や \(k-1\to k\) と置き換えれば、以下のように導けるからである。
\[
\begin{aligned}
\frac{n+1}{k+1}\dbinom{n}{k}
&= \dbinom{n+1}{k+1}\\
\frac{n-k}{k+1}\dbinom{n}{k}
&= \dbinom{n}{k+1}\\
\frac{n+1}{n+1-k}\dbinom{n}{k}
&= \dbinom{n+1}{k}\\
\end{aligned}
\]
ここで、\(n+1\to n\) や \(k+1\to k\) と置き換えてもまた然りである。
</p>

<h2>二項定理の式をズラす</h2>
<p>
以下の公式にて、\(n\) や \(k\) を置き換える。
\[
(x + y)^n = \sum_{k=0}^{n}\dbinom{n}{k}x^{n-k}y^k
\]
<br/>
\(n\to n-1, k\to k-1\)
\[
\begin{aligned}
(x + y)^{n-1} &= \sum_{k=1}^{n}\dbinom{n-1}{k-1}x^{n-1-k+1}y^{k-1}\\
&= \sum_{k=1}^{n}\frac{k}{n}\dbinom{n}{k}x^{n-1-k+1}y^{k-1}\\
\end{aligned}
\]
\(x=1, y=1\)
\[
\begin{aligned}
2^{n-1} &= \sum_{k=1}^{n}\frac{k}{n}\dbinom{n}{k}\\
n2^{n-1} &= \sum_{k=1}^{n}k\dbinom{n}{k}\\
% n:11; sum(k*binomial(n,k),k,1,n)/n;
\end{aligned}
\]
\(x=1, y=-1\)
\[
\begin{aligned}
(1 - 1)^{n-1} &= \sum_{k=1}^{n}\frac{k}{n}\dbinom{n}{k}(-1)^{k-1}\\
0 &= \sum_{k=1}^{n}k\dbinom{n}{k}(-1)^{k-1}\\
% n:10; sum(k*binomial(n,k)*(-1)^(k-1),k,1,n);
\end{aligned}
\]

\(n\to n-1\)
\[
\begin{aligned}
(x + y)^{n-1}
&= \sum_{k=0}^{n-1}\dbinom{n-1}{k}x^{n-k-1}y^k\\
&= \sum_{k=0}^{n-1}\frac{n-k}{n}\dbinom{n}{k}x^{n-k-1}y^k\\
\end{aligned}
\]
\(x=1, y=1\)
\[
\begin{aligned}
(1 + 1)^{n-1}
&= \sum_{k=0}^{n-1}\frac{n-k}{n}\dbinom{n}{k}\\
2^{n-1}
&= \sum_{k=0}^{n-1}\frac{n-k}{n}\dbinom{n}{k}\\
n2^{n-1}
&= \sum_{k=0}^{n-1}(n-k)\dbinom{n}{k}\\
% n:11; sum((n-k)*binomial(n,k),k,0,n-1)/n;
&= \sum_{k=0}^{n-1}(n-k)\dbinom{n}{n-k}\\
\end{aligned}
\]
\(k\to n-k\)
\[
\begin{aligned}
n2^{n-1}
&= \sum_{k=1}^{n}k\dbinom{n}{k}\\
% n:11; sum(k*binomial(n,k),k,1,n)/n;
\end{aligned}
\]
\(x=1, y=-1\)
\[
\begin{aligned}
(1 - 1)^{n-1}
&= \sum_{k=0}^{n-1}\frac{n-k}{n}\dbinom{n}{k}(-1)^k\\
0
&= \sum_{k=0}^{n-1}(n-k)\dbinom{n}{k}(-1)^k\\
% n:10; sum((n-k)*binomial(n,k)*(-1)^k,k,0,n-1);
&= \sum_{k=0}^{n-1}(n-k)\dbinom{n}{n-k}(-1)^k\\
\end{aligned}
\]
\(k\to n-k\)
\[
\begin{aligned}
0
&= \sum_{k=1}^{n}k\dbinom{n}{k}(-1)^{n-k}\\
\end{aligned}
% n:10; sum(k*binomial(n,k)*(-1)^(n-k),k,1,n);
\]
</p>

<h2>２つの二項係数の積</h2>
<p>
一般に、２つの二項係数の積の添え字が互い違いに等しいとき（下例では \(j\)）、もしくは、２つの二項係数の積の１つ目の添え字の差が一方の２つ目の添え字に等しいとき（下例では \(n-j\)）、以下のように互い違いに異なる添え字の二項係数との積に書き換えることができる（下例では \(j\) を片方の二項係数の添え字に追いやる効能がある）。
\[
\begin{aligned}
\dbinom{n}{j}\dbinom{j}{h}
&= \dbinom{n}{n-j}\dbinom{j}{h}\\
&= \frac{n!}{j!(n-j)!}\frac{j!}{h!(j-h)!}
= \frac{n!}{h!(n-h)!}\frac{(n-h)!}{(n-j)!(j-h)!}\\
&= \dbinom{n}{h}\dbinom{n-h}{n-j} = \dbinom{n}{n-h}\dbinom{n-h}{n-j}
\end{aligned}
\]
さらに、\(n=m+h\) と置き換えればわかるように、同様に以下のような２つの二項係数の積も書き換えることができる（下例では \(m\) を片方の二項係数に追いやる効能がある）。
\[
\begin{aligned}
\dbinom{m+h}{h}\dbinom{m}{k}
&= \dbinom{m+h}{m}\dbinom{m}{k}\\
&= \frac{(m+h)!}{h!m!}\frac{n!}{k!(m-k)!}
= \frac{(m+h)!}{(h+k)!(m-k)!}\frac{(h+k)!}{k!h!}\\
&= \dbinom{m+h}{h+k}\dbinom{h+k}{h}
= \dbinom{m+h}{m-k}\dbinom{h+k}{h}\\
\end
{aligned}
\]
以上の事実を整理すると（\(j=n-k, m=n-h\)）、以下のような公式として紹介されることが常であるが、公式だけでは上記の２例目などは見逃しやすいので注意しよう。
\[
\begin{aligned}
\dbinom{n}{n-h}\dbinom{n-h}{k}
&= \dbinom{n}{n-k}\dbinom{n-k}{h}\\
\equiv
\dbinom{n}{h}\dbinom{n-h}{k}
&= \dbinom{n}{k}\dbinom{n-k}{h}
\\
\end{aligned}
\]
\[
\begin{aligned}
\dbinom{n}{h}\dbinom{n-h}{k}
&= \frac{n!}{h!(n-h)!}\frac{(n-h)!}{k!(n-h-k)!}\\
&= \frac{n!}{k!(n-k)!}\frac{(n-k)!}{h!(n-k-h)!}
= \dbinom{n}{k}\dbinom{n-k}{h}
\end{aligned}
\]
</p>