二項係数
アイザック・ニュートンに名を因むニュートンの二項級数は、二項定理の級数版
( 1 + z ) α = ∑ n = 0 ∞ ( α n ) z n = 1 + ( α 1 ) z + ( α 2 ) z 2 + ⋯ {\displaystyle (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 }
である。これが成り立つことは両辺が微分方程式 (1 + z)f'(z) = αf(z) を満たすことを見ればよい。
この級数の収束半径は 1 である。
1 ( 1 − z ) α + 1 = ∑ n = 0 ∞ ( n + α n ) z n {\displaystyle {\frac {1}{(1-z)^{\alpha +1}}}=\textstyle \sum \limits _{n=0}^{\infty }{\dbinom {n+\alpha }{n}}z^{n}}
とも書ける。
部分集合の数を数える二項係数の組合せ論的定義を、基数 α, β に対して濃度 α を持つ適当な集合 A をとって
( α β ) = | { B ⊆ A : | B | = β } | {\displaystyle {\binom {\alpha }{\beta }}=|\{B\subseteq A:|B|=\beta \}|}
の形に表せば、無限基数に対しても一般化できる。基数 α を表す集合 A の取り方に依らず (αβ ) が等しいという意味でこの一般化はうまく定義されている。有限基数に対してこれが通常の二項係数の定義に一致するのは明らかであろう。
選択公理を仮定すれば、任意の無限基数 α に対して (αα) = 2 が示せる。
∑ k = 0 n ( n k ) 2 = ( 2 n n ) {\displaystyle \textstyle \sum \limits _{k=0}^{n}{\dbinom {n}{k}}^{2}={\dbinom {2n}{n}}}
も組合せ論的に証明できる。2n 個の□を一列に並べ、それらのうちの n 個を選んで印を付けることを考える。そのような方法は (2nn) 通りである(右辺)。他方、そのような n 個の□を選ぶときに、k 個は前半の n 個から、残り n − k 個は後半の n 個から選ぶとして 1 ≤ k ≤ n に亙って考える。これにより ∑n (nk)(nn − k) = (2nn) が得られるから、等式 (1) を適用して所期の結果を得る。
等式 (10) も組合せ論的に証明できる。(n − kk) は、2次元格子上で (0, 0) から (k, n − k) まで、(0, 1) または (1, 1) 刻みで移動して辿った経路の総数を表す。そのことは全部で n − k 個の点を亙るために必ずちょうど k 回だけ (1, 1) 刻みの移動をしなければならないのだから明らかである。さてここでちょうど k 個ある (1, 1) 刻みを (0, 2) 刻みで置き換えると、(0, 1) 刻みと (0, 2) 刻みを合わせて (0, n) へ到達することになる。これを 0 ≤ k ≤ ⌊n / 2⌋ なる各 k に亙って考えれば、(0, 0) から (0, 1) 刻みと (0, 2) 刻みを合わせて (0, n) へ到達する方法の総数が数え上げられる。そのような方法の総数が F(n + 1) 通りあることは明らかである。