二項係数のソースを表示

[[画像:Pascal's triangle 5.svg|200px|thumb|二項係数の全体を[[パスカルの三角形]]の形に並べることができる。]]
[[画像:Combination.png|300px|thumb|4つの数から2つの数を選ぶ方法は <math>\tbinom 4 2 = 6</math> 通りある。]]
[[画像:binomial_theorem_visualisation.svg|300px|thumb|四次までの二項展開の視覚的説明]]
[[数学]]における'''二項係数'''（にこうけいすう、{{lang-en-short|''binomial coefficients''}}）は[[二項展開]]において[[係数]]として現れる正の[[整数]]の族である。二項係数は2つの非負整数で添字付けられ、添字 {{math2|''n'', ''k''}} を持つ二項係数はふつう {{math|{{binom|''n''|''k''}}}} とか {{math|(''n''¦''k'')}} と書かれる（これは[[二項式|二項]][[冪]] {{math|(1 + ''x''){{sup|''n''}}}} の[[多項式の展開|展開]]における {{mvar|x{{sup|k}}}} の項の係数である。適当な仮定の下で、この係数の値は <math>\tfrac{n!}{k!\,(n-k)!}</math> で与えられる）。二項係数を、連続する整数 {{mvar|n}} に対する各行に {{mvar|k}} を {{math|0}} から {{mvar|n}} まで順に並べて得られる三角形状の数の並びを[[パスカルの三角形]]と呼ぶ。

この整数族は代数学のみならず数学の他の多くの分野、特に[[組合せ数学|組合せ論]]において現れる。{{mvar|n}}元-集合から {{mvar|k}}個の元を（その順番を無視して）選ぶ方法が {{math|{{binom|''n''|''k''}}}} 通りである。二項係数の性質を用いて、記号 {{math|{{binom|''n''|''k''}}}} の意味を、もともとの {{mvar|n}} および {{mvar|k}} が {{math2|''k'' ≤ ''n''}} なる非負整数であった場合を超えて拡張することが可能で、そのような場合もやはり二項係数と称する。

== 歴史と記法 ==
二項係数に関して詳しく知られた最も初期の議論は[[10世紀]]ごろ{{仮リンク|ハラユーダ|en|Halayudha}}が古代[[サンスクリット語]]で書いた "[[Pingala]]'s Chandaḥśāstra" である。[[1150年]]ごろには、[[インド]]の数学者[[バースカラ2世]]が著書 "Lilavati" で二項係数について詳しく述べている<ref>[[Lilavati]] Section 6, Chapter 4 (see {{harvtxt|Knuth|1997}}).</ref>。

記号 {{math|{{binom|''n''|''k''}}}} は{{仮リンク|アンドレアス・フォン・エッチンクハウゼン|en|Andreas von Ettingshausen}}が1826年に導入したものである<ref>{{harvtxt|Higham|1998}}</ref>。
そのほかの記法として {{math|''C''&#x2061;(''n'', ''k'')}}, {{mvar|{{msub|n}}C{{msub|k}}}}, {{mvar|{{msup|n}}C{{msub|k}}}}, {{mvar|C{{su|p=k|b=n}}}}, {{mvar|C{{su|p=n|b=k}}}}<ref>{{harvtxt|Shilov|1977|p={{google books quote|id=5U6loPxlvQkC|page=92|92}}}}</ref>, {{math|''C''{{sub|''n'',''k''}}}}, {{math|(''n''¦''m'')}} などがあり、何れも文字 '''{{mvar|C}}''' は[[組合せ (数学)|組合せ]] ('''c'''ombination) や選択 ('''c'''hoice) を表している。

== 定義と解釈 ==
[[自然数]]（{{math|0}} も含める）{{mvar|n}} および {{mvar|k}} に対し、二項係数 {{math|{{binom|''n''|''k''}}}} は[[二項式|二項冪]] {{math|(1 + ''X''){{sup|''n''}}}} の展開における {{mvar|X{{sup|k}}}} の[[単項式|項]]の[[係数]]として定義できる。同係数は（{{math2|''k'' ≤ ''n''}}のとき）[[二項定理|二項公式]]
{{NumBlk|:|<math>(x+y)^n = \textstyle\sum\limits_{k=0}^n \dbinom{n}{k} x^{n-k} y^k</math>|{{EquationRef|∗}}}}
に現れるため「二項係数」の名がある（この式自体は[[環 (数学)|環]]の互いに可換な任意の元 {{math|''x'', ''y''}} に対して成り立つ）。

[[組合せ論]]においてもまたこの数は、{{mvar|n}} 個の対象から {{mvar|k}} 個選ぶ選び方の総数、より形式的には {{mvar|n}}元-集合の {{mvar|k}}元-部分集合（{{mvar|k}}-項[[組合せ (数学)|組合せ]]）の総数として現れる。この数が先に述べた係数と一致することは、後で述べるこの数の計算法の何れとも独立に示すことができる。実際、冪 {{math2|(1 + ''X''){{sup|''n''}}}} における {{mvar|n}} 個の因子の各々において、一時的に {{mvar|X}} に対し {{math2|1 ≤ ''i'' ≤ ''n''}} なる添字 {{mvar|i}} をそれぞれ付けて区別しておくと、{{mvar|k}} 個の添字からなる部分集合をひとつ選ぶ毎に展開後の {{mvar|X{{sup|k}}}} への寄与が {{math|1}} だけあるから、この項の係数はそのような部分集合の選び方の数に一致する。このことは特に {{math|{{binom|''n''|''k''}}}} が任意の自然数 {{math2|''n'', ''k''}} に対して自然数となることも示している。二項係数の組合せ論的解釈（二項係数展開が答えを与える数え上げ問題）は多く存在する。例えば、各位の和が {{mvar|k}} に一致する {{mvar|n}}桁の[[ビット]]（つまり各位の数は {{math|0}} か {{math|1}}）の語（文字列）の総数は {{math|{{binom|''n''|''k''}}}} で与えられる。また、各 {{mvar|a{{sub|i}}}} が非負整数であるものとして {{math2|''k'' {{=}} ''a''{{sub|1}} + ''a''{{sub|2}} + … + ''a{{sub|n}}''}} と書く方法の総数は {{math|{{binom|''n'' + ''k'' &minus; 1|''n'' &minus; 1}}}} 通りである。これら解釈のほとんどは、{{mvar|k}}-組合せを数えることに同値であることが容易に示される。

== 二項係数の値の計算 ==
{{math|{{binom|''n''|''k''}}}} の値を、実際に二項冪を展開したり {{mvar|k}}-組合せを数え上げたりせずに、計算する方法はいくつかある。

=== 漸化式 ===
一つは、{{math2|''n'', ''k''}} を {{math2|1 ≤ ''k'' ≤ ''n'' &minus; 1}} なる自然数として、純加法的な[[漸化式]]
: <math>\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}k</math>
を初期条件「任意の {{math2|''n'' ≥ 0}} に対し {{math2|1={{binom|''n''|0}} = {{binom|''n''|''n''}} = 1}}」の下で用いることである。

この漸化式自体は、集合 {{math2|{1, 2, 3, …, ''n''} }}において以下のように場合を分けて {{mvar|k}}元-集合を数えることで得られる。特定の元に注目し、ここではそれを “{{mvar|i}}” とする。
* (a) 特定の元 {{mvar|i}} を含む {{mvar|k}} 個の元を集める。この場合、各集まりは既に {{mvar|i}} があることは仮定しているから、残りの {{math2|''k'' &minus; 1}} 個の元を {{mvar|i}} を除く {{math2|''n'' &minus; 1}} 元の中から特定すればよい。
* (b) 特定の元 {{mvar|i}} を全く含まない {{mvar|k}} 個の元を集める。この場合、{{mvar|i}} を除く {{math2|''n'' &minus; 1}} 個の元から {{mvar|k}} 個を選ぶことに他ならない。
この二者で与えられた {{mvar|n}} 個の元から得られるすべての {{mvar|k}}-組合せが数え上げられているので所期の結果を得る。

あるいはまた、{{math2|(1 + ''X''){{sup|''n''}} {{=}} (1 + ''X''){{sup|''n''&minus;1}}(1 + ''X'')}} の両辺における {{mvar|X{{sup|k}}}} への寄与を見ることでもこの漸化式は得られる。{{math|(1 + ''X''){{sup|''n''}}}} において {{math|''X''{{sup|''n''+1}}}} や {{math|''X''{{sup|&minus;1}}}} の項は存在しない（あるいは係数が零である）から、二項係数の定義を上記の境界を越えて延長して、{{math2|{{binom|''n''|''k''}} {{=}} 0 (''k'' > ''n'' &or; ''k'' < 0)}} とすることもできる。

この漸化式は[[パスカルの三角形]]を描くのにも利用できる。

=== 乗法表示 ===
個々の二項係数をより効果的に計算するには
: <math>\binom{n}{k} = \frac{n^{\underline{k}}}{k!} = \frac{n(n-1)(n-2) \cdots (n-(k-1))}{k(k-1)(k-2)\cdots 1} = \textstyle\prod\limits_{i=1}^k \dfrac{n-(k-i)}{i} = \prod\limits_{i=1}^k \dfrac{n+1-i}{i}</math>
で与えられる式を用いる。一つ目の分数の分子に現れる {{math|''n''{{sup|{{underline|k}}}}}} は[[下降階乗冪]]である。この公式を理解するには二項係数の組合せ論的解釈に依るのが最も簡明である。分子は {{mvar|n}} 個の対象からなる集合から選ぶ順番を考慮して相異なる {{mvar|k}} 個の対象を取り出す方法の総数であり、分母は同じ {{mvar|k}}-組合せを与える相異なる並びの数を数えるものである。

=== 階乗表示 ===
最後に、計算論的には不利だが、短く書けるのでしばしば証明や導出に用いられるよく知られた[[階乗]]函数を用いた式は
: <math>\binom{n}{k} = \frac{n!}{k!\,(n-k)!}</math>
で与えられる。ここに {{math|''n''!}} は {{mvar|n}} の階乗である。この式は上記の乗法表示式に、分子分母に対して {{math2|(''n'' &minus; ''k'')!}} を掛けることで得られる（その結果、この式において分母と分子は多くの共通因数を持つことになる）。（特に階乗は非常に速く増加するから）この式を（{{mvar|k}} が小さく {{mvar|n}} が大きい場合に）実際の数値計算に用いることは（先に共通因数を約分しない限り）実用的でない。この式は上記の乗法表示よりは二項係数が対称性
{{NumBlk|:|<math>\binom nk = \binom n{n-k}</math>|{{EquationRef|1}}}}
を持つことを見るのに適している（二項係数の定義から対称性をもつことは分かる）。この対称性を用いれば乗法的な計算をより効果的にすることもできる。下降階乗冪で書けば
: <math>\binom nk = \begin{cases}
n^{\underline{k}}/k! & \text{if }\ k \le \frac{n}{2} \\
n^{\underline{n-k}}/(n-k)! & \text{if }\ k > \frac{n}{2}
\end{cases}</math>
と書ける。

=== 一般化および二項級数 ===
乗法表示を用いれば、{{mvar|n}} を任意の数 {{mvar|α}}（負の整数、実数、複素数、……）あるいは任意の整数が可逆となるような[[可換環]]の元に取り換えて、
: <math>\binom\alpha{k} = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k(k-1)(k-2)\cdots 1}</math>
により二項係数の定義を拡張することができる{{refnest|group="注"|{{Harv|Graham|Knuth|Patashnik|1994}} を参照、これはまた {{math2|''k'' < 0}} のとき {{math2|{{binom|''n''|''k''}} {{=}} 0}} とする。別の一般化として[[ガンマ函数]]を用いて {{math2|''k'' < 0}} のとき {{math|{{binom|''n''|''k''}}}} に非零な値を割り当てることもできるが、それは多くの二項係数に関する公式を満足せず、これを定義として広汎に適用することはできない。そのように非零値を選ぶものの一つとして、見た目の美しい {{harvtxt|Holton|1997}}の「パスカルの風車」("Pascal windmill") が導かれる<ref>{{Citation |last=Holton |first=Pedersen |title=Mathematical Reflections: In a Room With Many Mirrors |publisher=Springer |year=1997 |isbn=978-1-4612-1932-3}}</ref>が、これは{{仮リンク|パスカルの等式|en|Pascal's identity}}も（原点において）成り立たない。}}。この定義により、二項定理（の一方の変数を {{math|1}} としたもの）も一般化して
{{NumBlk|:|<math>(1+X)^\alpha = \textstyle\sum\limits_{k=0}^\infty \dbinom\alpha{k} X^k</math>|{{EquationRef|2}}}}
と書くことができる。故にこの場合も {{math|{{binom|''α''|''k''}}}} を二項係数と呼ぶことは正当化される。この等式は任意の複素数 {{mvar|α}} と {{math2|{{abs|''X''}} < 1}} なる {{mvar|X}} に対して有効である。これはまた {{mvar|X}} を不定元とする[[形式冪級数]]の等式としても解釈でき、それは実際に定数係数 {{math|1}} を持つ級数の任意の冪の定義として機能する。この定義を用いるポイントは、[[冪乗]]として満足することが期待される全ての恒等式（[[指数法則]]）、特に
* <math>(1+X)^\alpha(1+X)^\beta=(1+X)^{\alpha+\beta},</math>
* <math>((1+X)^\alpha)^\beta=(1+X)^{\alpha\beta}</math>
が満足されることである。{{mvar|α}} が非負整数 {{mvar|n}} のとき、{{math2|''k'' > ''n''}} なる全ての項は零であり、上記の無限級数は有限和となり、したがってもともとの二項定理が再び得られる。しかし {{mvar|α}} がそれ以外の値ならば、負の整数や有理数の場合も含めて、上記の級数は実際に無限和になる。

== パスカルの三角形 ==
[[画像:Pascal's triangle - 1000th row.png|150px|thumb|パスカルの三角形の第{{val|1000|u=行}}に並ぶ二項係数を縦に並べたもの。各二項係数を十進表示し、その各桁の数字を0-9に応じたグレイスケールの点で表してある。画像の左の境界は二項係数の対数グラフにほぼ対応しており、これらが{{仮リンク|対数的に凹な数列|label=対数凹列|en|logarithmically concave sequence}}であることが見て取れる。]]
{{Main|パスカルの三角形}}
{{仮リンク|パスカルの法則|en|Pascal's rule}}は重要な[[漸化式]]
{{NumBlk|:|<math>\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1},</math>|{{EquationRef|3}}}}
で、これを用いて {{math|{{binom|''n''|''k''}}}} が任意の自然数 {{mvar|n, k}} に対して自然数となること（別な言い方をすれば、連続する {{mvar|k}}-個の整数の積を {{math|''k''!}} が割り切ること）を[[数学的帰納法|帰納的]]に示すことができる。これは定義 ({{EquationNote|∗}}) や乗法表示からは直ちに明らかなことではない。

パスカルの法則から[[パスカルの三角形]]が生じる:
:{|style="text-align:center;margin:1ex auto 1ex auto"
!style="padding-right:2em"|0:
| || || || || || || ||
|style="padding:0.5em 0.5em"|1|| || || || || || || ||
|-
!style="padding-right:2em"|1:
| || || || || || ||
|style="padding:0.5em 0.5em"|1||
|style="padding:0.5em 0.5em"|1|| || || || || || ||
|-
!style="padding-right:2em"|2:
| || || || || ||
|style="padding:0.5em 0.5em"|1|| ||2||
|style="padding:0.5em 0.5em"|1|| || || || || ||
|-
!style="padding-right:2em"|3:
| || || || ||
|style="padding:0.5em 0.5em"|1|| ||3|| ||3||
|style="padding:0.5em 0.5em"|1|| || || || ||
|-
!style="padding-right:2em"|4:
| || || ||
|style="padding:0.5em 0.5em"|1|| ||4|| ||{{#expr:6}}|| ||4||
|style="padding:0.5em 0.5em"|1|| || || ||
|-
!style="padding-right:2em"|5:
| || ||
|style="padding:0.5em 0.5em"|1|| ||5|| ||{{#expr:10}}|| ||{{#expr:10}}|| ||5||
|style="padding:0.5em 0.5em"|1|| || ||
|-
!style="padding-right:2em"|6:
| ||
|style="padding:0.5em 0.5em"|1|| ||6|| ||{{#expr:15}}|| ||{{#expr:20}}|| ||{{#expr:15}}|| ||6||
|style="padding:0.5em 0.5em"|1|| ||
|-
!style="padding-right:2em"|7:
| |
|style="padding: 0.5em 0.5em"|1|| ||7|| ||{{#expr:21}}|| ||{{#expr:35}}|| ||{{#expr:35}}|| ||{{#expr:21}}|| ||7||
|style="padding:0.5em 0.5em"|1||
|-
!style="padding-right:2em"|8:
|style="padding:0.5em 0.5em"|1|| ||8|| ||{{#expr:28}}|| ||{{#expr:56}}|| ||{{#expr:70}}|| ||{{#expr:56}}|| ||{{#expr:28}}|| ||8||
|style="padding: 0.5em 0.5em"|1
|}
番号 {{mvar|n}} の行には {{math|{{binom|''n''|''k''}}}} の値が {{math2|''k'' {{=}} 0, …, ''n''}} に対して並べられている。これを書くには、一番外側の {{math|1}} から始めて、常に隣り合う２項を加えた数をその真下に書いていけばよい。この方法によって、分数や乗算を使わずに二項係数を手早く計算することができる。

例えば三角形の5行目を見れば
:{{math2|(''x'' + ''y''){{sup|5}} {{=}} '''1''' ''x''{{sup|5}} + '''5''' ''x''{{sup|4}}''y'' + '''10''' ''x''{{sup|3}}''y''{{sup|2}} + '''10''' ''x''{{sup|2}}''y''{{sup|3}} + '''5''' ''x'' ''y''{{sup|4}} + '''1''' ''y''{{sup|5}}}}
が直ちに読み取れる。

他の対角線上の数との差は、上記漸化式 ({{EquationNote|3}}) の帰結として、一つ前の対角線上の数である。

== 解釈 ==
二項係数はよくある数え上げ問題の簡明な公式を与えるという意味で[[組合せ論]]において重要である。
* {{mvar|n}}-元集合から {{mvar|k}}-元を選ぶ方法の総数は {{math|{{binom|''n''|''k''}}}} である（[[組合せ (数学)|組合せ]]を参照）。
* {{mvar|n}}-元集合から重複を許して {{mvar|k}}元を選ぶ方法の総数は{{math|{{binom|''n'' + ''k'' &minus; 1|''k''}}}} 通りある（[[多重集合]]を参照）。
* {{mvar|k}} 個の {{math|1}} と {{mvar|n}} 個の {{math|0}} を含む[[文字列]]は {{math|{{binom|''n'' + ''k''|''k''}}}} 種類存在する。
* {{mvar|k}} 個の {{math|1}} と {{mvar|n}} 個の {{math|0}} を含み、かつどの2つの {{math|1}} も隣り合わない文字列の総数は {{math|{{binom|''n'' + 1|''k''}}}} である<ref>{{Cite journal |first=Muir |last=Thomas |title=Note on selected combinations|journal=Proceedings of the Royal Society of Edinburgh |year=1904 |url=https://books.google.co.jp/books/reader?id=EN8vAAAAIAAJ&output=reader&pg=GBS.PA102&redir_esc=y&hl=ja |doi=10.1017/S0370164600007768}}</ref>。
* [[カタラン数]]：{{math|{{sfrac|''n'' + 1}}{{binom|2''n''|''n''}}}}.
* [[二項分布]]：{{math|{{binom|''n''|''k''}}''p''{{sup|''k''}}(1 &minus; ''p''){{sup|''n''&minus;''k''}}}}.

== 多項式としての性質 ==
{{mvar|t}} を不定元として、任意の非負整数 {{mvar|k}} に対して式
: <math>\binom{t}{k} = \frac{(t)_k}{k!} = \frac{(t)_k}{(k)_k}= \frac{t(t-1)(t-2)\cdots(t-k+1)}{k(k-1)(k-2) \cdots 2 \cdot 1}</math>
は {{mvar|t}} に関する[[有理数|有理]]係数[[多項式]]である。この意味において、{{mvar|t}} には任意の実数あるいは複素数を代入することができ、それによって二項係数の定義を一般化するとき、そのような「一般化された二項係数」は[[二項定理|ニュートンの一般化二項定理]]に現れる。

各 {{mvar|k}} に対し、多項式 {{math|{{binom|''t''|''k''}}}} は {{math2|1=''p''&#x2061;(0) = ''p''&#x2061;(1) = … = ''p''&#x2061;(''k'' &minus; 1) = 0}} かつ {{math2|1=''p''&#x2061;(''k'') = 1}} を満たす唯一の {{mvar|k}}次多項式 {{math|''p''(''t'')}} として特徴づけることができる。

この多項式の係数は{{仮リンク|第一種スターリング数|en|Stirling numbers of the first kind}}を用いて
: <math>\binom{t}{k} = \textstyle\sum\limits_{i=0}^k \displaystyle\left[{k \atop i} \right]\frac{t^i}{k!}</math>
と表すことができる。この導函数は[[対数微分法]]により
: <math>\frac{d}{\mathit{dt}} \binom{t}{k} = \binom{t}{k} \textstyle\sum\limits_{i=0}^{k-1} \dfrac{1}{t-i}</math>
と計算できる。

=== 多項式の空間の基底 ===
[[標数]] {{math|0}} の任意の[[可換体|体]]（すなわち、[[有理数]]体 {{math|'''Q'''}} を含む体）上で、次数が高々 {{mvar|d}} の任意の多項式 {{math|''p''&#x2061;(''t'')}} は二項係数の線型結合
:<math>p(t) = \textstyle\sum\limits_{k=0}^d a_k \dbinom{t}{k}</math>
として一意に書ける。このときの係数 {{mvar|a{{msub|k}}}} は数列 {{math|''p''&#x2061;(0), ''p''&#x2061;(1), …, ''p''&#x2061;(''k'')}} の[[有限差分|第 {{mvar|k}}-階差]]で与えられ、明示的に書けば
{{NumBlk|:|<math>a_k = \textstyle\sum\limits_{i=0}^k (-1)^{k-i} \dbinom{k}{i} p(i)</math>|{{EquationRef|4}}}}
で決まる<ref group="注">これは[[テイラーの定理]]の離散版として理解でき、[[ニュートン多項式]]と近しい。この形の[[交代和]]は[[ネールント&ndash;ライス積分]]として表せる。</ref>。

=== 整数値多項式 ===
{{main|{{仮リンク|整数値多項式|en|Integer-valued polynomial}}}}
各二項係数多項式 {{math|{{binom|''t''|''k''}}}} は整数値（整数を代入したとき必ず整数を返す）である（これは例えば{{仮リンク|パスカルの等式|en|Pascal's identity}}を用いて {{mvar|k}} に関する帰納法で示せる）。従って、二項係数多項式の任意の整係数線型結合もまた整数値多項式になる。逆に等式 ({{EquationNote|4}}) により任意の整数値多項式がこれら二項係数多項式の正係数線型結合となることが示せる。より一般に標数 {{math|0}} の体の任意の部分環 {{mvar|R}} に対し、{{math|''K''[''t'']}} に属する多項式が任意の整数において {{mvar|R}} に値をとるための必要十分条件はそれが二項係数多項式の {{mvar|R}}-係数線型結合となっていることである。

== 二項係数に関する等式 ==
階乗表示を用いれば近くにある二項係数の関係を容易に知ることができる。例えば {{mvar|k}} を正整数、{{mvar|n}} は任意として
{{NumBlk|:|<math>\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}</math>|{{EquationRef|5}}}}
が成り立ち、また少しの計算で
: <math>\binom {n-1}{k} - \binom{n-1}{k-1} = \frac{n-2k}{n} \binom{n}{k}</math>
が得られる。さらに言えば以下の結果
: <math>\binom{n}{h}\binom{n-h}{k}=\binom{n}{k}\binom{n-k}{h}</math>
は有用である。例えば定数 {{mvar|n}} に対して以下の漸化式
: <math>\binom{n}{k} = \frac{n+1-k}{k} \binom{n}{k-1}</math>
を得ることができる。

=== 二項係数を含む級数 ===
等式
{{NumBlk|:|<math>\textstyle\sum\limits_{k=0}^n \dbinom{n}{k} = 2^n</math>|{{EquationRef|∗∗}}}}
は等式 ({{EquationNote|∗}}) において {{math2|''x'' {{=}} 1}} かつ {{math2|''y'' {{=}} 1}} とすれば得られる。これはパスカルの三角形の各行において現れる全ての数を足し合わせれば[[2の冪| {{math|2}} の整数冪]]になると言っても同じである。この事実の組合せ論的解釈は{{仮リンク|二通りに数える論法|en|double counting (proof technique)}} (double counting) で {{mvar|n}}元-集合 {{mvar|S}} の位数 {{mvar|i}} {{math2|(''i'' {{=}} 1, 2, …, ''n'')}} の部分集合を数えることである。任意の位数 {{mvar|i}} に対する部分集合を数えているのだから、その和は {{mvar|S}} の部分集合の総数に等しく、それが {{math|2{{sup|''n''}}}} であることはよく知られている。すなわち、等式 ({{EquationNote|∗∗}}) は [[有限集合|{{mvar|n}}元-集合]]の[[冪集合]]の位数が {{math|2{{sup|''n''}}}} であることを述べるものである。より明確に、{{mvar|n}}-桁のビット列を考えれば、このビット列は {{math|2{{sup|''n''}}}} 個の数を表すことに利用できる。その中で一つも {{math|1}} を含まないビット列を考えれば、これは {{math2|{{binom|''n''|0}} {{=}} 1}} 通りである。ちょうど一つ {{math|1}} を含むビット列は {{math2|{{binom|''n''|1}} {{=}} ''n''}} 通りである。このように数えて行けば上記の式を得る。

等式
{{NumBlk|:|<math>\textstyle\sum\limits_{k=0}^n k \dbinom{n}{k} = n 2^{n-1}</math>|{{EquationRef|6}}}}
および
: <math>\textstyle\sum\limits_{k=0}^n k^2 \dbinom{n}{k} = (n+n^2) 2^{n-2}</math>
は等式 ({{EquationNote|2}}) を {{mvar|x}} に関して（後者は2回）微分して {{math2|''x'' {{=}} 1}} と置けば得られる。

{{仮リンク|朱ファンデルモンドの等式|en|Chu–Vandermonde identity}}
{{NumBlk|:|<math>\textstyle\sum\limits_{j=0}^k \dbinom{m}{j} \dbinom{n-m}{k-j} = \dbinom{n}{k}</math>|{{EquationRef|7}}}}
は任意の複素数 {{math2|''m'', ''n''}} と任意の非負整数 {{mvar|k}} に対して成立する。これは {{math2|(1 + ''x''){{sup|''m''}}&thinsp;(1 + ''x''){{sup|''n''&minus;''m''}} {{=}} (1 + ''x''){{sup|''n''}}}} の展開における {{mvar|x{{sup|k}}}} の係数として、等式 ({{EquationNote|2}}) を用いて求めることができる。{{math|''m'' {{=}} 1}} のとき等式 ({{EquationNote|7}}) は等式 ({{EquationNote|3}}) に簡約される。

任意の整数 {{math2|''j'', ''k'', ''n'' (0 ≤ ''j'' ≤ ''k'' ≤ ''n'')}} に対して適用できる同様の等式
{{NumBlk|:|<math>\textstyle\sum\limits_{m=0}^n \dbinom{m}{j} \dbinom{n-m}{k-j} = \dbinom{n+1}{k+1}</math>|{{EquationRef|8}}}}
は、<math>\frac{x^l}{(1-x)^{l+1}} = \textstyle\sum\limits_{p=0}^\infty \dbinom{p}{l} x^p</math> を用いれば
: <math>x\left( \tfrac{x^j}{(1-x)^{j+1}}\right) \left(\tfrac{x^{k-j}}{(1-x)^{k-j+1}}\right) = \tfrac{x^{k+1}}{(1-x)^{k+2}}</math>
の展開における {{math|''x''{{sup|''n''+1}}}} の係数として求められる。{{math2|''j'' {{=}} ''k''}} のとき等式 ({{EquationNote|8}}) は
: <math>\textstyle\sum\limits_{m=0}^n \dbinom{m}{k} = \dbinom{n+1}{k+1}</math>
となる。展開 ({{EquationNote|7}}) を {{math2|1=''n'' = 2''m'', ''k'' = ''m''}} に対して用い、({{EquationNote|1}}) を使えば
{{NumBlk|:|<math>\textstyle\sum\limits_{j=0}^m \dbinom{m}{j}^2 = \dbinom{2m}{m}</math>|{{EquationRef|9}}}}
を得る。

{{math|''F''&#x2061;(''n'')}} で {{mvar|n}} 番目の[[フィボナッチ数]]を表せば、パスカルの三角形の対角和に関する等式
{{NumBlk|:|<math>\textstyle\sum\limits_{k=0}^{\lfloor n/2\rfloor} \dbinom{n-k}{k} = F(n+1)</math>|{{EquationRef|10}}}}
を得る。これは等式 ({{EquationNote|3}}) を用いた帰納法、あるいは[[ゼッケンドルフの定理|ゼッケンドルフの表現]]によって示すことができる（左辺は {{math2|{''F''&#x2061;(2), …, ''F''&#x2061;(''n'')} }}の連続した元を含まない部分集合の総数を与えるものであり、そのようなものはまた {{math|''F''&#x2061;(''n'' + 1)}} 以下の数の全体を成すということに他ならないことに注意）。組合せ論的証明は後述。

等式 ({{EquationNote|8}}) から従う別の等式として、{{math|''j'' {{=}} ''k'' &minus; 1}} とおいて {{math2|1={{sum|''j''=''k''|''n''}} (''n'' + 1 &minus; ''j''){{binom|''j'' &minus; 1|''k'' &minus; 1}} = {{binom|''n'' + 1|''k'' + 1}}}} を得る。

{{math2|{{sum|''j''{{=}}0|''k''}} {{binom|''n''|''j''}}}} に対する閉じた式は（[[超幾何函数]]を用いなければ）ない<ref>{{Citation |last=Boardman |first=Michael |issue=5 |journal=[[Mathematics Magazine]] |jstor=3219201 |mr=1573776 |quote=it is well known that there is no closed form (that is, direct formula) for the partial sum of binomial coefficients |pages=368-372 |title=The Egg-drop numbers |volume=77 |year=2004}}.</ref>が、再び等式 ({{EquationNote|3}}) および帰納法により {{math2|''k'' {{=}} 0, …, ''n'' &minus; 1}} に対して {{math2|1={{sum|''j''=0|''k''}} (&minus;1)&thinsp;{{sup|''j''}} {{binom|''n''|''j''}} = (&minus;1){{sup|''k''}} {{binom|''n'' &minus; 1|''k''}}}} を得る。同様に {{math2|1={{sum|''j''=0|''n''}} (&minus;1)&thinsp;{{sup|''j''}} {{binom|''n''|''j''}} = 0}} を得る<ref>see induction developed in eq (7) p.1389 in {{Citation |last=Aupetit |first=Michael |journal=[[Neurocomputing]] |pages=1379-1389 |title=Nearly homogeneous multi-partitioning with a deterministic generator |volume=72 |number=7-9 |year=2009 |issn=0925-2312 |doi=10.1016/j.neucom.2008.12.024}}.</ref>（{{math2|''n'' {{=}} 0}} の自明な場合は除く。このときは {{math|1}} になる）。これ自身は次数高々 {{mvar|n}} の任意の多項式 {{math2|''P''&#x2061;(''x'')}} に対する[[和分差分学]]における結果<ref>{{cite journal |last=Ruiz |first=Sebastian |title=An algebraic identity leading to Wilson's theorem|journal=The Mathematical Gazette |year=1996 |volume=80 |issue=489 |pages=579-582 |url=http://www.jstor.org/stable/3618534 |doi=10.2307/3618534}}</ref>{{math2|1={{sum|''j''=0|''n''}} (&minus;1)&thinsp;{{sup|''j''}} {{binom|''n''|''j''}} ''P''(''j'') = 0}} の特別の場合である。{{math2|''P''&#x2061;(''x'') {{=}} ''x''(''x'' &minus; 1)…(''x'' &minus; ''k'' + 1) (0 ≤ ''k'' < ''n'')}} に対しては等式 ({{EquationNote|2}}) を {{mvar|k}} 回微分して {{math2|''x'' {{=}} &minus;1}} と置けば得られる。一般の場合はこれらの線型結合を作ればよい。

{{mvar|n}}次以下の多項式 {{math2|''P''(''x'')}} に対して
{{NumBlk|:|<math>\textstyle\sum\limits_{j=0}^n (-1)^j \dbinom{n}{j}P(n-j) = n!a_n</math>|{{EquationRef|11}}}}
が成り立つ。ここで {{mvar|a{{msub|n}}}} は {{math2|''P''(''x'')}} の {{mvar|n}}次係数である。等式 ({{EquationNote|11}}) はより一般に、複素数 {{math2|''m'', ''d''}} に対して
: <math>\textstyle\sum\limits_{j=0}^n (-1)^j \binom{n}{j} P(m+(n-j)d) = d^n n! a_n</math>
とできる。これは {{math2|''P''&#x2061;(''x'')}} の代わりに多項式 {{math2|''Q''&#x2061;(''x'') :{{=}} ''P''&#x2061;(''m'' + ''d&sdot;x'')}} とするとき、{{math2|''Q''&#x2061;(''x'')}} がやはり {{mvar|n}}次以下の多項式であることと {{mvar|n}}次係数が {{math2|d''{{sup|n}}''&sdot;''a{{sub|n}}''}} であることに注意すれば、等式 ({{EquationNote|11}}) を適用して直ちに得られる。

[[級数]]
: <math>\frac{k-1}{k} \textstyle\sum\limits_{j=0}^\infty \dfrac{1}{\binom{j+x}{k}} = \dfrac{1}{\binom{x-1}{k-1}}</math>
は {{math2|''k'' ≥ 2}} に対して収束する。この等式は{{仮リンク|ドイツの戦車問題|en|German tank problem}}を調べるのに利用できる。これを見るには
: <math>\frac{k-1}{k} \textstyle\sum\limits_{j=0}^M \dfrac{1}{\binom{j+x}{k}} = \dfrac{1}{\binom{x-1}{k-1}} - \dfrac{1}{\binom{M+x}{k-1}}</math>
が成り立つことを {{mvar|M}} に関する帰納法で示せばよい。

等式 ({{EquationNote|9}}) から {{math2|1={{sum|''i''=0|''n''}} ''i'' {{binom|''n''|''i''}}{{sup|2}} = {{sfrac|''n''|2}} {{binom|2''n''|''n''}}}} および {{math|1={{sum|''i''=0|''n''}} ''i''{{sup|2}} {{binom|''n''|''i''}}{{sup|2}} = ''n''{{sup|2}} {{binom|2''n'' &minus; 2|''n'' &minus; 1}}}} が得られる。

{{仮リンク|Series multisection|en|Series multisection}}により、{{math2|0 ≤ ''t'' < ''s''}} として {{mvar|t}} を境に {{mvar|s}} 刻みに取った二項係数の総和と {{mvar|s}} 項の閉じた形の式の和との間の等式
: <math>\binom{n}{t} + \binom{n}{t+s} + \binom{n}{t+2s} + \dotsb = \frac{1}{s} \textstyle\sum\limits_{j=0}^{s-1} \left( 2\cos \dfrac{\pi j}{s} \right)^n \cos \dfrac{\pi(n-2t)j}{s}</math>
が示せる。

=== 組合せ論的に証明できる等式 ===
二項係数を含む多くの等式が{{仮リンク|組合せ論的証明|label=組合せ論的に|en|Combinatorial proof}}証明することができる。例えば {{math2|''n'' ≥ ''q''}} なる非負整数に対して
: <math>\textstyle\sum\limits_{k=q}^n \dbinom{n}{k} \dbinom{k}{q} = 2^{n-q} \dbinom{n}{q}</math>
（{{math2|''q'' {{=}} 1}} のとき ({{EquationNote|6}}) に簡約される）は、以下のように{{仮リンク|二通りに数える論法|label=二通りの仕方で数えて証明|en|Double counting (proof technique)}}できる。左辺は集合 {{math2|[''n''] {{=}} {1, 2, …, ''n''} }}の少なくとも {{mvar|q}} 個の元を含む部分集合を選び、選ばれた元のうち {{mvar|q}} 個に印をつける方法を数えている。右辺も同じものを数えるのだけれども、{{mvar|n}} 個の元のうち {{mvar|q}} 個に印をつける方法が {{math|{{binom|''n''|''q''}}}} 通りあり、その各々について印をつけた {{mvar|q}} 個を含む部分集合を得るには印の付いた {{mvar|q}} 個に残りの {{math2|''n'' &minus; ''q''}} 個の元から任意に追加すればよいから、そのような仕方は {{math|2{{sup|''n''&minus;''q''}}}} 通りである。

パスカルの法則
: <math>\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}</math>
の両辺は集合 {{math|[''n'']}} の {{mvar|k}}元-部分集合を数えているのだけれども、右辺は特定の元（例えば {{mvar|n}}）を含むように選ぶ場合と含まないように選ぶ場合に分けて数えている。

等式 ({{EquationNote|9}}), 再掲すると
: <math>\textstyle\sum\limits_{k=0}^n \dbinom{n}{k}^2 = \dbinom{2n}{n}</math>
も組合せ論的に証明できる。{{math|2''n''}} 個の□を一列に並べ、それらのうちの {{mvar|n}} 個を選んで印を付けることを考える。そのような方法は {{math|{{binom|2''n''|''n''}}}} 通りである（右辺）。他方、そのような {{mvar|n}} 個の□を選ぶときに、{{mvar|k}} 個は前半の {{mvar|n}} 個から、残り {{math2|''n'' &minus; ''k''}} 個は後半の {{mvar|n}} 個から選ぶとして {{math2|1 ≤ ''k'' ≤ ''n''}} に亙って考える。これにより {{math2|1={{sum|''k''=0|''n''}} {{binom|''n''|''k''}}{{binom|''n''|''n'' &minus; ''k''}} = {{binom|2''n''|''n''}}}} が得られるから、等式 ({{EquationNote|1}}) を適用して所期の結果を得る。

[[画像:1N3E SVG.svg|300px|thumb|2次元格子上の経路の例]]
等式 ({{EquationNote|10}}) も組合せ論的に証明できる。{{math|{{binom|''n'' &minus; ''k''|''k''}}}} は、2次元格子上で {{math2|(0, 0)}} から {{math2|(''k'', ''n'' &minus; ''k'')}} まで、{{math|(0, 1)}} または {{math2|(1, 1)}} 刻みで移動して辿った経路の総数を表す。そのことは全部で {{math2|''n'' &minus; ''k''}} 個の点を亙るために必ずちょうど {{mvar|k}} 回だけ {{math2|(1, 1)}} 刻みの移動をしなければならないのだから明らかである。さてここでちょうど {{mvar|k}} 個ある {{math2|(1, 1)}} 刻みを {{math2|(0, 2)}} 刻みで置き換えると、{{math2|(0, 1)}} 刻みと {{math2|(0, 2)}} 刻みを合わせて {{math|(0, ''n'')}} へ到達することになる。これを {{math2|0 ≤ ''k'' ≤ &lfloor;''n''&thinsp;/&thinsp;2&rfloor;}} なる各 {{mvar|k}} に亙って考えれば、{{math2|(0, 0)}} から {{math2|(0, 1)}} 刻みと {{math2|(0, 2)}} 刻みを合わせて {{math|(0, ''n'')}} へ到達する方法の総数が数え上げられる。そのような方法の総数が {{math2|''F''(''n'' + 1)}} 通りあることは明らかである。

=== ディクソンの等式 ===
{{仮リンク|ディクソンの等式|en|Dixon's identity}}は
: <math>\textstyle\sum\limits_{k=-a}^a (-1)^k \dbinom{2a}{k+a}^3 =\dfrac{(3a)!}{(a!)^3}</math>
あるいはより一般に
: <math>\textstyle\sum\limits_{k=-a}^a (-1)^k \dbinom{a+b}{a+k} \dbinom{b+c}{b+k} \dbinom{c+a}{c+k} = \dfrac{(a+b+c)!}{a!\,b!\,c!}</math>
で与えられる。ここに {{math2|''a'', ''b'', ''c''}} は非負整数である。

=== 連続等式 ===
ある種の三角積分は二項係数で表される値を持つ。{{math2|''m'', ''n''}} を非負整数として:
* <math>\int_{-\pi}^{\pi} \cos((2m-n)x) \cos^n x\ dx = \frac{\pi}{2^{n-1}} \binom{n}{m}</math>
* <math>\int_{-\pi}^{\pi} \sin((2m-n)x) \sin^n x\ dx = \begin{cases}
(-1)^{m+\frac{n+1}{2}} \dfrac{\pi}{2^{n-1}} \dbinom{n}{m} &(n \text{: odd}) \\
0 & (\text{otherwise})
\end{cases}</math>
* <math>\int_{-\pi}^{\pi} \cos((2m-n)x)\sin^n x\ dx = \begin{cases}
(-1)^{m+\frac{n+1}{2}} \dfrac{\pi}{2^{n-1}} \dbinom{n}{m} &(n \text{: even}) \\
0 &(\text{otherwise})
\end{cases}</math>
これらは[[オイラーの公式]]で[[三角函数]]を複素指数函数に変換して、二項定理で展開して項別積分すれば示せる。

== 母函数 ==
=== 通常母函数 ===
固定した {{mvar|n}} に対して作られる数列 {{math2|{{binom|''n''|0}}, {{binom|''n''|1}}, {{binom|''n''|2}}, …}} の通常母函数は
: <math>\textstyle\sum\limits_{k=0}^{\infty} \dbinom{n}{k} x^k = (1+x)^n</math>
で与えられる。固定した {{mvar|k}} に対して作られる数列 {{math2|{{binom|0|''k''}}, {{binom|1|''k''}}, {{binom|2|''k''}}, …}} の通常母函数は
: <math>\textstyle\sum\limits_{n=k}^\infty \dbinom{n}{k} y^n = \dfrac{y^k}{(1-y)^{k+1}}</math>
である。一般の非負整数 {{math2|''n'', ''k''}} に対する二項係数の{{仮リンク|二変数母函数|en|bivariate generating function}} は
: <math>\textstyle\sum\limits_{n,k} \dbinom{n}{k} x^k y^n = \dfrac{1}{1-y-xy}</math>
を満たす。二項係数に対する別の形の二変数母函数は、対称函数として
: <math>\textstyle\sum\limits_{n,k} \dbinom{n+k}{k} x^k y^n = \dfrac{1}{1-x-y}</math>
で与えられる。

=== 指数型母函数 ===
二項係数に関する{{仮リンク|指数型母函数|en|exponential generating function|label=指数型二変数母函数}}は
: <math>\sum_{n,k} \frac{1}{(n+k)!}\binom{n+k}{k} x^k y^n = e^{x+y}</math>
となる。

== 可除性 ==
{{main|{{仮リンク|クンマーの定理|en|Kummer's theorem}}|{{仮リンク|リュカの定理|en|Lucas' theorem}}}}
1852年、[[エルンスト・クンマー|クンマー]]は非負整数 {{mvar|m, n}} および素数 {{mvar|p}} に対し、{{math|{{binom|''m'' + ''n''|''m''}}}} を整除する最大の {{mvar|p}}-冪が {{mvar|p{{sup|c}}}} であるとき、{{mvar|c}} は {{mvar|m}} と {{mvar|n}} を加えるときに生じる {{mvar|p}}-進表示における繰り上がりの数に等しいことを示した{{sfn|Knuth|1997|p={{google books quote|id=x9AsAwAAQBAJ|page=30|30}}}}。同じことだが、{{math|{{binom|''n''|''k''}}}} における素因子 {{mvar|p}} の冪指数は {{math|{{fraction|''k''|''p''&thinsp;{{sup|''j''}}}}}} の{{仮リンク|小数部|en|fractional part}} が {{math|{{fraction|''n''|''p''&thinsp;{{sup|''j''}}}}}} の小数部よりも大きくなるような非負整数 {{mvar|j}} の総数に等しい。これにより、{{math|{{binom|''n''|''k''}}}} が {{math|{{fraction|''n''|[[最大公約数|gcd]](''n'',''k'')}}}} で割り切れることが導かれる。したがって特に、任意の正整数 {{mvar|r}} および {{math2|''s'' < ''p''{{sup|''r''}}}} なる正整数 {{mvar|s}} に対して {{mvar|p}} は {{math|{{binom|''p''{{sup|''r''}}|''s''}}}} を割り切る。しかしより高次の {{mvar|p}}-冪に対してこれは正しくない（例えば {{math|9}} は {{math|{{binom|9|6}}}} を割り切らない）。

{{harvtxt|Singmaster|1974}} は「任意の整数が[[ほとんど全て]]の二項係数を整除する」という幾分驚くべき結果を与えた。より精確に言えば、整数 {{mvar|d}} を固定して、{{math2|''f''&#x2061;(''N'')}} は {{math2|''n'' < ''N''}} なる二項係数 {{math|{{binom|''n''|''k''}}}} のうち {{mvar|d}} で割り切れるものの総数を表すものとすると、
: <math>\lim_{N\to\infty} \frac{f(N)}{N(N+1)/2} = 1</math>
が成り立つというものである。{{math2|''n'' < ''N''}} なる二項係数 {{math|{{binom|''n''|''k''}}}} の総数は {{math|{{sfrac|1|2}}''N''(''N'' + 1)}} であるから、これは {{mvar|d}} で整除可能なものの占める密度が {{math|1}} に収束することを意味する。

別の事実として、整数 {{math2|''n'' ≥ 2}} が素数となる必要十分条件は、中間二項係数
: <math>\binom{n}{1}, \binom{n}{2}, \ldots, \binom{n}{n-1}</math>
の全てが {{mvar|n}} で整除可能なことである。実際、{{mvar|p}} が素数ならば、{{math2|0 < ''k'' < ''p''}} なる任意の {{mvar|k}} に対して {{mvar|p}} は
: <math>\binom{p}{k} = \frac{p \cdot (p-1) \cdots (p-k+1)}{k \cdot (k-1) \cdots 1}</math>
を割り切る。これは分子は素因数 {{mvar|p}} を含むが分母は {{mvar|p}} を素因数に持たないことによる。{{mvar|n}} が合成数のとき、{{mvar|p}} を {{mvar|n}} を割り切る最小の素因数とし、{{math2|''k'' {{=}} {{sfrac|''n''|''p''}}}} と置けば、{{math|0 < ''p'' < ''n''}} かつ
: <math>\binom{n}{p} = \frac{n(n-1)(n-2)\cdots(n-p+1)}{p!}=\frac{k(n-1)(n-2)\cdots(n-p+1)}{(p-1)!}</math>
は {{mvar|n}} で割り切れない。仮に割り切れるとすると分子 {{math2|''k''(''n'' &minus; 1)(''n'' &minus; 2) × … × (''n'' &minus; ''p'' + 1)}} が {{math|''n'' {{=}} ''k'' &times; ''p''}} で割り切れることになり、それは {{math|(''n'' &minus; 1)(''n'' &minus; 2) × … × (''n'' &minus; ''p'' + 1)}} が {{mvar|p}} で割り切れる場合しかありえないが、{{mvar|n}} は {{mvar|p}} で割り切れるのだから、{{mvar|p}} は {{math2|''n'' &minus; 1, ''n'' &minus; 2, …, ''n'' &minus; ''p'' + 1}} を割り切らず、{{mvar|p}} は素数だから従って {{math2|(''n'' &minus; 1)(''n'' &minus; 2) × … × (''n'' &minus; ''p'' + 1)}} も割り切らず、それゆえ分子が {{mvar|n}} で割り切られることもない。

== 上界・下界と漸近公式 ==
{{math|{{binom|''n''|''k''}}}} に関して以下の評価
:<math>\left( \frac{n}{k} \right)^k \le \binom{n}{k} \le \frac{n^k}{k!} \le \left( \frac{n\cdot e}{k} \right)^k</math>
が {{math2|1 ≤ ''k'' ≤ ''n''}} に対して成立する。[[スターリングの近似]]からは {{math|{{sqrt|''n''}}&thinsp;{{binom|2''n''|''n''}} ≥ 2{{sup|2''n''&minus;1}}}}, 一般に
: <math>\sqrt{n}\binom{mn}{n} \ge \frac{m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}</math>
が {{math2|''m'' ≥ 2}} かつ {{math2|''n'' ≥ 1}} に対して成立する。また {{math2|''n'' → ∞}} のとき近似
: <math>\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}</math>
が成り立つ。{{math2|''n'', ''k''}} がともに 1 より十分大きければスターリング近似からは以下の漸近近似
: <math>\log_2 \binom{n}{k} \sim n H\left(\frac{k}{n}\right) </math>
も従う。ここに {{math2|''H''&#x2061;(ε) {{=}} &minus;εlog{{sub|2}}&#x2061;(ε) &minus; (1 &minus; ε)log{{sub|2}}&#x2061;(1 &minus; ε)}} は {{math|ε}} の[[二値エントロピー関数]]である。より精確に、任意の整数 {{math2|''n'' ≥ ''k'' ≥ 1}} と {{math2|ε ≐ {{sfrac|''k''|''n''}} ≤ {{sfrac|1|2}}}} に対して、最初の {{math2|''k'' + 1}} 個の二項係数の和を
:<math>\frac{1}{\sqrt{8n\epsilon(1-\epsilon)}} \cdot 2^{H(\epsilon) \cdot n} \leq \sum_{i=0}^k \binom{n}{i} \leq 2^{H(\epsilon) \cdot n}</math>
と評価することができる<ref>see e.g. {{harvtxt |Ash|1990|p=121}} or {{harvtxt |Flum|Grohe|2006| p=427}}.</ref>。

{{mvar|n}} が大きく、{{mvar|k}} が {{mvar|n}} に対して十分小さいとき <math>\textstyle \binom{n}{k} = \frac{n(n-1)\dots(n-k+1)}{k!} \approx \frac{(n-k/2)^k}{ k^k e^{-k} \sqrt{2\pi k}} = \frac{(n/k-0.5)^k e^k}{\sqrt{2\pi k}}</math> と書くことができるので、
: <math>\log \binom{n}{k} \approx k \ln( \frac{n}{k} -0.5)+k-0.5 \ln(2 \pi k)</math>
を得る。より精度を望むならば、{{math2|ln&#x2061;(''n''(''n'' &minus; 1)…(''n'' &minus; ''k'' + 1))}} を積分で近似して
: <math>\log \binom{n}{k} \approx (n+0.5) \ln\frac{n+0.5}{n-k+0.5} + k \ln \frac{n-k+0.5}{k} - 0.5 \ln(2 \pi k)</math>
となる。{{math2|''n'' {{=}} 20}} かつ {{math2|''k'' {{=}} 10}} に対して {{math2|log&#x2061;{{binom|''n''|''k''}} &asymp; 12.127}} およびこれら近似式からそれぞれ近似値 {{math2|12.312}} および {{math2|12.133}} を得る。

[[ガンマ函数]]の無限積表示に基づく無限積
:<math>(-1)^k \binom{z}{k}= \binom{-z+k-1}{k} = \frac{1}{\Gamma(-z)} \frac{1}{(k+1)^{z+1}} \prod_{j=k+1} \frac{(1+\frac{1}{j})^{-z-1}}{1-\frac{z+1}{j}}</math>
から漸近公式
:<math>\binom{z}{k} \approx \frac{(-1)^k}{\Gamma(-z) k^{z+1}}, \quad \binom{z+k}{k} = \frac{k^z}{\Gamma(z+1)}\left( 1+\frac{z(z+1)}{2k}+\mathcal{O}\left(k^{-2}\right)\right)</math>
が {{math2|''k'' → ∞}} で成り立つ。この漸近挙動は近似
: <math>\binom{z+k}{k}\approx \frac{e^{z(H_k-\gamma)}}{\Gamma(z+1)}</math>
にも表れている。ここに、{{mvar|H{{sub|k}}}} は {{mvar|k}}番目の[[調和数 (発散列)|調和数]]で、{{math|γ}} は[[オイラー&ndash;マスケローニ定数]]である。さらに、{{math2|''k'' → ∞}} かつ適当な複素数 {{mvar|x}} に対して {{math2|{{sfrac|''j''|''k''}} → ''x''}} なるとき、漸近公式
:<math>\frac{\binom{z+k}{j}}{\binom{k}{j}}\to \left(1-\frac{j}{k}\right)^{-z},
\quad \frac{\binom{j}{j-k}}{\binom{j-z}{j-k}}\to \left(\frac{j}{k}\right)^z</math>
が成り立つ。

二項係数の和について、[[二項定理]]を用いると
:<math>\sum_{i=0}^k \binom{n}{i} \leq \sum_{i=0}^k n^i\cdot 1^{k-i} = (1+n)^k</math>
という単純で粗い上界が得られる。

== 近似 ==
{{mvar|n}} が十分大きいとき、
:<math>\binom{n}{k} = \frac{2^n}{\sqrt{\tfrac{1}{2}n \pi}} e^{-\frac{(k-(n/2))^2}{n/2}}\left[1+O\left(\frac{1}{\sqrt{n}}\right)\right]</math>
は二項係数と正規分布との関係に基づく近似を与える。これは、二項分布と等しい期待値と分散 {{math2|(''np'', ''np''(1-''p''))}} を持つ正規分布をとり、{{math2|1=''p'' = 1 &minus; ''p'' = {{sfrac|1|2}}}} として、{{math|2{{sup|''n''}}}} を掛ければ、[[中心極限定理]]に対する評価から従う。

== 一般化 ==
=== 多項への一般化 ===
{{main|多項係数}}
二項係数を一般化するものとして
: <math>\binom{n}{k_1,k_2,\ldots,k_r} =\frac{n!}{k_1!k_2!\cdots k_r!}\qquad (\textstyle\sum\limits_{i=1}^r k_i = n)</math>
で定義される数を'''多項係数'''と呼ぶ。二項係数が {{math|(''x'' + ''y''){{sup|''n''}}}} の係数であったのに対し、多項係数は {{math2|(''x''{{sub|1}} + ''x''{{sub|2}} + … + ''x''{{sub|''r''}}){{sup|''n''}}}} の多項式展開の係数であり、{{math2|''r'' {{=}} 2}} のとき二項係数を与える:
: <math>\binom{n}{k_1,k_2}= \binom{n}{k_1, n-k_1}=\binom{n}{k_1}= \binom{n}{k_2}.</math>

多項係数は、区別可能な {{mvar|n}} 個の元を {{mvar|r}} 個の箱に分けて入れるとき、箱の番号 {{math2|''i'' (1 ≤ ''i'' ≤ ''r'')}} に対して各箱がちょうど {{mvar|k{{sub|i}}}} 個の元を含むような分け方の総数として組合せ論的に解釈できる。

多項係数は二項係数の性質とよく似たたくさんの性質を満たす。例えば漸化式
: <math>\binom{n}{k_1,k_2,\ldots,k_r} = \binom{n-1}{k_1-1,k_2,\ldots,k_r}+ \binom{n-1}{k_1,k_2-1,\ldots,k_r}+\dotsb+\binom{n-1}{k_1,k_2,\ldots,k_r-1}</math>
および任意の[[置換 (数学)|置換]] {{mvar|σ}} に関する対称性
: <math>\binom{n}{k_1,k_2,\ldots,k_r} =\binom{n}{k_{\sigma_1},k_{\sigma_2},\ldots,k_{\sigma_r}}</math>
が挙げられる。ただし、{{math|(σ{{sub|''i''}})}} は {{math2|(1,2, …,''r'')}} を並べ替えたものである。

=== テイラー級数 ===
{{仮リンク|第一種スターリング数|en|Stirling numbers of the first kind}}を用いれば、二項係数の任意に選んだ点 {{math|''z''{{msub|0}}}} の周りでの[[テイラー展開]]は
:<math>\begin{align}
\binom{z}{k} = \frac{1}{k!}\sum_{i=0}^k z^i s_{k,i} &=\sum_{i=0}^k (z- z_0)^i \sum_{j=i}^k \binom{z_0}{j-i} \frac{s_{k+i-j,i}}{(k+i-j)!} \\
  &=\sum_{i=0}^k (z-z_0)^i \sum_{j=i}^k z_0^{j-i} \binom{j}{i} \frac{s_{k,j}}{k!}
\end{align}</math>
と与えられる。

=== 半整数に対する二項係数 ===
二項係数の定義（積による表示）は {{mvar|n}} が実数、{{mvar|k}} が整数の場合にも意味を持つ。特に {{math2|''n'' {{=}} {{sfrac|1|2}}}} のとき任意の非負整数 {{mvar|k}} に対して
: <math>\binom{1/2}{k} = \binom{2k}{k}\frac{(-1)^{k+1}}{2^{2k}(2k-1)}</math>
が成り立つ。これは二項級数展開 {{math2|{{sqrt|1 + ''x''}} {{=}} {{sum|''k''≥0}} {{binom|1/2|''k''}}''x{{sup|k}}''}} に現れる。

=== 二項係数の積 ===
二項係数の積は二項係数の線型結合として
: <math>\binom{z}{m} \binom{z}{n} = \textstyle\sum\limits_{k=0}^m \dbinom{m+n-k}{k,m-k,n-k} \dbinom{z}{m+n-k}</math>
と表すことができる。この展開の結合係数は多項係数で与えられる。ラベル付けられた組合せ論的対象を用いて言えば、この結合係数はそれぞれ重み {{mvar|m}} および {{mvar|n}} のラベル付けられた対象の対で最初の {{mvar|k}} 個のラベルが一致するようなものに {{math2|''m'' + ''n'' &minus; ''k''}} をラベル付ける方法の総数、あるいはそれらを貼り合せて新たに重み {{math2|''m'' + ''n'' &minus; ''k''}} でラベル付けられた対象を付け加える方法（つまり、このラベルを一方の対象の貼り合せない部分、他方の対象の貼り合せない部分、両者の貼り合せ部分の3つの部分に分ける方法）の総数である。このように見ると、二項係数の母函数は[[下降階乗冪]]に対する通常母函数に対応する指数型母函数である。

=== 部分分数分解 ===
二項係数の逆数の[[部分分数分解]]は
: <math>\frac{1}{\binom{z}{n}}= \textstyle\sum\limits_{i=0}^{n-1} (-1)^{n-1-i} \dbinom{n}{i} \dfrac{n-i}{z-i}</math>
および
: <math>\frac{1}{\binom{z+n}{n}}= \textstyle\sum\limits_{i=1}^n (-1)^{i-1} \dbinom{n}{i} \dfrac{i}{z+i}</math>
で与えられる。

=== ニュートンの一般二項級数 ===
{{main|[[二項級数]]}}
[[アイザック・ニュートン]]に名を因むニュートンの二項級数は、二項定理の級数版
: <math>(1+z)^{\alpha} = \textstyle\sum\limits_{n=0}^{\infty} \dbinom\alpha{n} z^n = 1+ \dbinom\alpha{1} z+ \dbinom\alpha{2} z^2 + \dotsb</math>
である。これが成り立つことは両辺が[[微分方程式]] {{math2|(1 + ''z'')''f'''(''z'') {{=}} α''f''(''z'')}} を満たすことを見ればよい。

この級数の[[収束半径]]は {{math|1}} である。
: <math>\frac{1}{(1-z)^{\alpha+1}} = \textstyle\sum\limits_{n=0}^{\infty} \dbinom{n+\alpha}{n} z^n</math>
とも書ける。

=== 上昇版二項係数 ===
{{main|{{仮リンク|多重集合係数|en|Multiset coefficient}}}}
二項係数は与えられた集合から決められた位数の部分集合を数え上げるものであった。関連する組合せ論的問題として、与えられた集合から元をとって作られる決められた位数の[[多重集合]]を数え上げる問題、すなわち与えられた集合から重複を許して決められた数の元を選び出す重複組合せの問題がある。その総数は'''多重集合係数'''と呼ばれ<ref>{{Citation |last=Munarini |first=Emanuele |doi=10.2298/AADM110609014M |issue=2 |journal=Applicable Analysis and Discrete Mathematics |mr=2867317 |pages=176-200 |title=Riordan matrices and sums of harmonic numbers |volume=5 |year=2011}}.</ref>、{{mvar|n}} 個の元から {{mvar|k}} 個選ぶ重複組合せの総数は <math>\left(\!\tbinom{n}{ k}\!\right)</math> と書かれる。

以下議論の便宜のため {{mvar|n}} を使わずに、その代わり {{math2|''f'' {{=}} ''r'' + (''k'' &minus; 1)}} および {{math2|''r'' {{=}} ''f'' &minus; (''k'' &minus; 1)}} なる非負整数 {{math2|''f'', ''r''}} を用いる。

多重集合係数は以下に示す関係
: <math>\binom{f}{k}=\left(\!\!\binom{r}{k}\!\!\right)=\binom{r+k-1}{k}</math>
により二項係数として書ける。この等式を以下のようにも特徴づけることができる。
: <math>\begin{align}
(f)_k &=f^{\underline k}=(f-k+1)\cdots(f-3)\cdot(f-2)\cdot(f-1)\cdot f,\\
r^{(k)} &=r^{\overline k}=\,r\cdot(r+1)\cdot(r+2)\cdot(r+3)\cdots(r+k-1)
\end{align}</math>
が等しいことに注意すれば、二項係数を[[下降階乗冪]]を用いて 
: <math>\binom{f}{k} = \frac{(f)_{k}}{k!} =\frac{(f-k+1)\cdots(f-2)\cdot(f-1)\cdot f}{1\cdot2\cdot3\cdot4\cdot5\cdots k}</math>
と書くとき、対応する多重集合係数は下降階乗冪を対応する上昇階乗冪で置き換えた
: <math>\left(\!\!\binom{r}{k}\!\!\right)=\frac{r^{(k)}}{k!}=\frac{r\cdot(r+1)\cdot(r+2)\cdots(r+k-1)}{1\cdot2\cdot3\cdot4\cdot5\cdots k}</math>
として与えられる。

==== 負の二項係数 ====
任意の {{mvar|n}} に対して
: <math>\begin{align}
\binom{-n}{k} &= \frac{-n\cdot-(n+1)\dots-(n+k-2)\cdot-(n+k-1)}{k!} \\
  &=(-1)^k\;\frac{n \cdot (n+1) \cdot (n+2) \cdots (n+k-1)}{k!} \\
  &=(-1)^k\binom{n+k-1}{k}\\
  &=(-1)^k\left(\!\!\binom{n}{k}\!\!\right)
\end{align}</math>
が成り立つ。特に、負の整数における二項係数は符号付多重集合係数である。{{math|''n'' {{=}} &minus;1}} なる特別の場合には、これは <math>(-1)^k=\tbinom{-1}{k}=\big(\!\tbinom{-k}{k}\!\big)</math> と簡単になる。

=== 両引数が実数または複素数の場合 ===
[[ガンマ函数]]や[[ベータ函数]]を用いて
: <math>\binom{x}{y} = \frac{\Gamma(x+1)}{\Gamma(y+1) \Gamma(x-y+1)}= \frac{1}{(x+1) \Beta(x-y+1,y+1)}</math>
と書けば、二項係数の2つの引数を任意の実数または複素数まで一般化することができる。この定義においてガンマ函数の性質を用いれば、
: <math>\binom{x}{y} = \frac{\sin (y \pi)}{\sin(x \pi)} \binom{-y-1}{-x-1} = \frac{\sin((x-y) \pi)}{\sin (x \pi)} \binom{y-x-1}{y}</math>
が満たされることも分かる。特に
: <math>\binom{x}{y} \cdot \binom{y}{x}= \frac{\sin((x-y) \pi)}{(x-y) \pi}</math>
である。この一般化に関する研究は少ないが、{{Harv|Fowler|1996}} などにはすでに現れている。通常の二項係数に関する多くの等式がもはや成り立たなくなっていることに注意すべきである（例えば正の {{mvar|n}} に対して {{math2|{{binom|''n''|''m''}} {{=}} {{binom|''n''|''n'' &minus; ''m''}}}} や {{math2|{{binom|&minus;&thinsp;''n''|''m''}} {{=}} {{binom|&minus;&thinsp;''n''|&minus;&thinsp;''n'' &minus; ''m''}}}} は一般には正しくない）。その挙動は極めて複雑で、{{mvar|x}}軸、{{mvar|y}}軸と直線 {{math2|''y'' {{=}} ''x''}} で分けられる八分象限 (octant) のどの位置にあるかで著しく異なる。負の {{mvar|x}} に対しては負の整数の位置に特異点を持ち、正と負の領域が市松模様を成す:
* {{math2|0 ≤ ''y'' ≤ ''x''}} なる八分象限では、通常の二項係数を滑らかに補間し、稜線を成す（「パスカルの稜線」("Pascal's ridge")）。
* {{math2|0 ≤ ''x'' ≤ ''y''}} なる八分象限または {{math2|''x'' ≥ 0, ''y'' ≥ 0}} なる四分象限では、函数は零に近い。
* {{math2|''x'' ≤ 0, ''y'' ≥ 0}} なる四分象限では、四点 {{math2|(&minus;''n'', ''m'' + 1), (&minus;''n'', ''m''), (&minus;''n'' &minus; 1, ''m'' &minus; 1), (&minus;''n'' &minus; 1, ''m'')}} を頂点とする平行四辺形ごとに非常に大きな正の値と負の値を交互に取る。
* {{math2|0 > ''x'' > ''y''}} なる八分象限では、やはり非常に大きな正の値と負の値を交互に取るが、今度は正方形の格子で起こる。
* {{math2|&minus;1 > ''y'' > ''x'' + 1}} なる八分象限では、特異点の近くを除けば零に近い。

=== {{mvar|q}}-二項係数 ===
二項係数の[[q-類似| {{mvar|q}}-類似]]は{{仮リンク|ガウスの二項係数|en|Gaussian binomial coefficient}}と呼ばれる。

=== 無限基数の二項係数 ===
部分集合の数を数える二項係数の組合せ論的定義を、基数 {{mvar|α, β}} に対して[[濃度 (数学)|濃度]] {{mvar|α}} を持つ適当な集合 {{mvar|A}} をとって
: <math>\binom\alpha\beta = | \{ B \subseteq A : |B| = \beta \} |</math>
の形に表せば、[[無限基数]]に対しても一般化できる。基数 {{mvar|α}} を表す集合 {{mvar|A}} の取り方に依らず {{math|({{subsup||β|α}})}} が等しいという意味でこの一般化は[[well-defined|うまく定義されている]]。有限基数に対してこれが通常の二項係数の定義に一致するのは明らかであろう。

[[選択公理]]を仮定すれば、任意の無限基数 {{mvar|α}} に対して {{math2|{{binom|''α''|''α''}} {{=}} 2{{sup|α}}}} が示せる。

== 関連項目 ==
* {{仮リンク|二項変換|en|Binomial transform}}
* [[中心二項係数]]
* {{仮リンク|クンマーの定理|en|Kummer's theorem}}：二項係数の素冪因子に関する&mdash;<!--
* [[List of factorial and binomial topics]]-->
* {{仮リンク|リュカの定理|en|Lucas' theorem}}
* {{仮リンク|パスカルの三角形における各数の重複度|en|Multiplicities of entries in Pascal's triangle}}
* {{仮リンク|ダビデの星の定理|en|Star of David theorem}}
* {{仮リンク|孫の奇妙な等式|en|Sun's curious identity}}
* {{仮リンク|ニュートン級数の一覧|en|Table of Newtonian series}}
* {{仮リンク|三項係数|en|Trinomial expansion}}
* [[ポッホハマー記号]]

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist2}}
=== 出典 ===
{{Reflist|colwidth=25em}}

== 参考文献 ==
{{refbegin|colwidth=25em}}
* {{Cite book |first=Robert B. |last=Ash |title=Information Theory |publisher=Dover Publications, Inc. |origyear=1965 |year=1990 |isbn=0-486-66521-6 |url=http://www.amazon.com/Information-Theory-Dover-Books-Mathematics/dp/0486665216 |ref=harv}}
* {{Cite book |last1=Benjamin |first1=Arthur T. |last2=Jennifer |first2=Quinn |year=2003 |title=Proofs that Really Count: The Art of Combinatorial Proof |publisher=Mathematical Association of America |isbn=978-0-88385-333-7 |url=https://www.maa.org/press/books/proofs-that-really-count-the-art-of-combinatorial-proof |ref=harv}}
* {{Cite book |first=Victor |last=Bryant |authorlink=Victor Bryant |title=Aspects of Combinatorics |publisher=Cambridge University Press |year=1993 |isbn=0-521-41974-3}}
* {{Cite book |last=Flum |first=Jörg |last2=Grohe |first2=Martin |title=Parameterized Complexity Theory |year=2006 |publisher=Springer |url=http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0 |isbn=978-3-540-29952-3 |ref=harv}}
* {{Cite journal |doi=10.2307/2975209 |title=The binomial coefficient function |first=David |last=Fowler |journal=[[The American Mathematical Monthly]] |volume=103 |date=1996-01 |pages=1-17 |issue=1 |publisher=Mathematical Association of America |ref=harv |postscript=<!--None--> |jstor=2975209}}
* {{Cite journal |first=P. |last=Goetgheluck |title=Computing binomial coefficients |journal=American Math. Monthly |volume=94 |year=1987 |pages=360-365 |doi=10.2307/2323099}}
* {{Cite book |first=Ronald L. |last=Graham |authorlink= Ronald Graham |first2=Donald E. |last2=Knuth     |author2-link=Donald Knuth |first3=Oren |last3=Patashnik |author3-link=Oren Patashnik |title=Concrete Mathematics |publisher=Addison-Wesley |year=1994 |edition=Second |isbn=0-201-55802-5 |pages=153-256 |ref=harv}}
* {{Cite book |first=Nicholas J. |last=Higham |authorlink=Nicholas J. Higham |title=Handbook of Writing for the Mathematical Sciences |publisher=[[Society for Industrial and Applied Mathematics|SIAM]] |isbn=0-89871-420-6 |year=1998 |page=25 |ref=harv}}
* {{Cite book |first=Donald E. |last=Knuth |authorlink=Donald Knuth |title=The Art of Computer Programming, Volume 1: ''Fundamental Algorithms'' |edition=Third |publisher=Addison-Wesley |year=1997 |isbn=0-201-89683-4 |pages=52-74 |ref=harv}}
* {{Cite journal |first=David |last=Singmaster |authorlink=David Singmaster |title=Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients |journal=Journal of the London Mathematical Society |volume=8 |issue=3 |year=1974 |pages=555-560 |doi=10.1112/jlms/s2-8.3.555 |ref=harv}}
* {{Cite book |first=G. E. |last=Shilov |title=Linear Algebra |publisher=Dover Publications |year=1977 |isbn=978-0-486-63518-7|ref=harv}}
{{refend}}

== 外部リンク ==
* {{高校数学の美しい物語|588|二項係数の有名公式一覧と2つの証明方針}}
* {{高校数学の美しい物語|1285|二項係数の和，二乗和，三乗和}}

* {{SpringerEOM|title=Binomial coefficients|urlname=Binomial_coefficients}}
* {{Cite journal |author=[[Andrew Granville]] |url=http://www.cecm.sfu.ca/organics/papers/granville/Binomial/toppage.html |title=Arithmetic properties of binomial coefficients I. Binomial coefficients modulo prime powers |journal=CMS Conf. Proc |volume=20 |pages=151-162 |year=1997}}

{{PlanetMath attribution
|id = 30273 |title = Binomial Coefficient
|id2 = 34074 |title2 = Bounds for binomial coefficients
|id3 = 36744 |title3 = Proof that C(n,k) is an integer
|id4 = 36309 |title4 = Generalized binomial coefficients
}}

{{DEFAULTSORT:にこうけいすう}}
[[Category:組合せ論]]
[[Category:整数の類]]
[[Category:数学に関する記事]]
[[Category:数の三角形]]