組合せ論的解釈
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/02/05 15:32 UTC 版)
n, k は自然数とする。n-元の集合から k-部分集合を選び出す k-順列の総数は下降階乗冪 xk である。同じく k-組合せの総数は二項係数であったから ( n k ) = n k _ k ! {\displaystyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}} なる関係式を得る。これは ( n + k − 1 k ) = n k ¯ k ! {\displaystyle {\binom {n+k-1}{k}}={\frac {n^{\overline {k}}}{k!}}} とも書ける。
※この「組合せ論的解釈」の解説は、「階乗冪」の解説の一部です。
「組合せ論的解釈」を含む「階乗冪」の記事については、「階乗冪」の概要を参照ください。
組合せ論的解釈
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/24 02:37 UTC 版)
「フィボナッチ多項式」の記事における「組合せ論的解釈」の解説
Fn(x) における xk の係数を F(n,k) と表す。すなわち F n ( x ) = ∑ k = 0 n F ( n , k ) x k , {\displaystyle F_{n}(x)=\sum _{k=0}^{n}F(n,k)x^{k},\,} とする。このとき F(n,k) は、 2 × 1 のドミノとちょうど k 個の 1 × 1 の正方形を使って、n−1 × 1 の長方形を埋める方法の数に等しい。また同値であるが、F(n,k) は、1 をちょうど k 回使って、1 と 2 のみからなる順序付の和で n−1 を書く方法の数に等しい。例えば F(6,3)=4 であるが、これ 1 をちょうど 3 回使って、1 と 2 のみからなる順序付の和で 6-1 = 5 を書く方法 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1 の数 4 に等しい。そのような和で用いられる 1 と 2 の数を数えることで、F(n,k) は二項係数 F ( n , k ) = ( n + k − 1 2 k ) {\displaystyle F(n,k)={\binom {\tfrac {n+k-1}{2}}{k}}} に等しい。ここで n と k は異なるパリティ（奇偶性）を持つ。このことから、右図のようにパスカルの三角形からフィボナッチ多項式の係数を求めることが出来る。
※この「組合せ論的解釈」の解説は、「フィボナッチ多項式」の解説の一部です。
「組合せ論的解釈」を含む「フィボナッチ多項式」の記事については、「フィボナッチ多項式」の概要を参照ください。
- 組合せ論的解釈のページへのリンク
