ガウス二項係数

ガウス二項係数の組み合わせ論的記述の一つは、反転を含む。

通常の二項係数${\displaystyle {\tbinom {m}{r}}}$m個の要素の集合から選択されたr個の組み合わせの数を数えます。これらのm個の要素を長さmの単語内の異なる文字位置とすると、各r 個の組み合わせは、例えば{0,1}のような 2 文字のアルファベットを使用した長さmの単語に対応し、文字 1 がr個(選択された組み合わせ内の位置を示す)、文字0 がm − r個 (残りの位置を示す) あります。

例えば、${\displaystyle {4 \choose 2}=6}$0と1を使った単語は${\displaystyle 0011,0101,0110,1001,1010,1100}$。

ガウス二項係数を取得するには${\displaystyle {\tbinom {m}{r}}_{\!q}}$各単語には因子q ^dが関連付けられており、dは単語の反転の数であり、この場合、反転とは、ペアの左側に文字1があり、右側に文字0がある位置のペアのことです。

上記の例では、0 回の倒置がある単語が 1 つあります。${\displaystyle 0011}$1つの単語に1つの倒置、${\displaystyle 0101}$2つの単語に2つの倒置、${\displaystyle 0110}$、${\displaystyle 1001}$3つの倒置を含む1つの単語、${\displaystyle 1010}$、そして4つの倒置を含む単語が1つ、${\displaystyle 1100}$これは、初期位置から左にシフトした1の数でもあります。

これらは、係数に対応します${\displaystyle {4 \choose 2}_{\!q}=1+q+2q^{2}+q^{3}+q^{4}}$。

別の見方としては、各単語を、高さ r、幅m − rの長方形グリッド上の、左下隅から右上隅までの経路と関連付ける方法があります。この経路は、0ごとに右に 1 歩、1 ごとに上に1歩進みます。反転は、ステップの方向を反転させます (右 + 上 が上 + 右 になり、その逆も同様)。したがって、反転の数は経路の下の面積に等しくなります。

させて${\displaystyle B(n,m,r)}$投げる方法の数 ${\displaystyle r}$区別がつかないボールを${\displaystyle m}$区別がつかない容器で、各容器には最大で${\displaystyle n}$ボール。ガウス二項係数は、${\displaystyle B(n,m,r)}$。 確かに、

${\displaystyle B(n,m,r)=[q^{r}]{n+m \choose m}_{\!q}.}$

どこ${\displaystyle [q^{r}]P}$の係数を表します${\displaystyle q^{r}}$多項式において${\displaystyle P}$（下記の「アプリケーション」の項も参照してください。）

通常の二項係数と同様に、ガウス二項係数は中心対称であり、すなわち鏡映に対して不変である。${\displaystyle r\mapsto m-r}$:

${\displaystyle {m \choose r}_{\!q}={m \choose m-r}_{\!q}.}$

特に、

${\displaystyle {m \choose 0}_{\!q}={m \choose m}_{\!q}=1\,,}$

${\displaystyle {m \choose 1}_{\!q}={m \choose m-1}_{\!q}={\frac {1-q^{m}}{1-q}}=1+q+\cdots +q^{m-1}\quad m\geq 1\,.}$

q = 1におけるガウス二項係数の評価は

${\displaystyle \lim _{q\to 1}{\binom {m}{r}}_{\!q}={\binom {m}{r}}}$

つまり、係数の合計が対応する二項値を与える。

度合い${\displaystyle {\binom {m}{r}}_{\!q}}$は：${\displaystyle {\binom {m+1}{2}}-{\binom {r+1}{2}}-{\binom {(m{-}r)+1}{2}}=r(m-r)}$。

ガウス二項係数に対するパスカルの恒等式の類似式は次のとおりです。 ^{[ 2 ]}

${\displaystyle {m \choose r}_{\!q}=q^{r}{m-1 \choose r}_{\!q}+{m-1 \choose r-1}_{\!q}}$

そして

${\displaystyle {m \choose r}_{\!q}={m-1 \choose r}_{\!q}+q^{m-r}{m-1 \choose r-1}_{\!q}.}$

いつ${\displaystyle q=1}$これらはどちらも通常の二項式恒等式を与える。これは次のように表せる。${\displaystyle m\to \infty }$どちらの式も依然として有効である。

最初のパスカル類似法では、初期値を使用してガウス二項係数を再帰的に（ mに関して）計算することができます。

${\displaystyle {m \choose m}_{\!q}={m \choose 0}_{\!q}=1}$

また、ガウス二項係数が実際に多項式（qに関して）であることも示しています。

2 番目のパスカルの類似式は、置換を用いて最初のものから導き出されます。${\displaystyle r\rightarrow m-r}$反射の下でのガウス二項係数の不変性${\displaystyle r\rightarrow m-r}$。

これらの恒等式は線形代数の観点から自然な解釈が可能である。${\displaystyle {\tbinom {m}{r}}_{q}}$r次元部分空間をカウントする${\displaystyle V\subset \mathbb {F} _{q}^{m}}$、そして${\displaystyle \pi$ :\mathbb {F} _{q}^{m}\to \mathbb {F} _{q}^{m-1}} は一次元零空間を持つ射影である。${\displaystyle E_{1}}$最初の恒等式は、全単射から得られる。${\displaystyle V\subset \mathbb {F} _{q}^{m}}$部分空間へ${\displaystyle V'=\pi (V)\subset \mathbb {F} _{q}^{m-1}}$; 万一に備えて${\displaystyle E_{1}\not \subset V}$空間${\displaystyle V'}$はr次元であり、線形関数も追跡する必要がある。${\displaystyle \phi :V'\to E_{1}}$そのグラフは${\displaystyle V}$; しかし、${\displaystyle E_{1}\subset V}$空間${\displaystyle V'}$は ( r −1) 次元であり、再構成することができる${\displaystyle V=\pi ^{-1}(V')}$追加情報なしで。2 番目の恒等式も同様の解釈が可能で、${\displaystyle V}$に${\displaystyle V'=V\cap E_{n-1}}$( m -1)次元空間の場合${\displaystyle E_{m-1}}$再び2つのケースに分かれる。

どちらの類似も、まず定義から次のことを指摘することで証明できる。${\displaystyle {\tbinom {m}{r}}_{q}}$、 我々は持っています：

として

${\displaystyle {\frac {1-q^{m}}{1-q^{m-r}}}={\frac {1-q^{r}+q^{r}-q^{m}}{1-q^{m-r}}}=q^{r}+{\frac {1-q^{r}}{1-q^{m-r}}}}$

式（１）は次のようになる。

${\displaystyle {\binom {m}{r}}_{q}=q^{r}{\binom {m-1}{r}}_{q}+{\frac {1-q^{r}}{1-q^{m-r}}}{\binom {m-1}{r}}_{q}}$

そして式（３）を代入すると、最初の類似式が得られる。

同様のプロセスで、

${\displaystyle {\frac {1-q^{m}}{1-q^{r}}}=q^{m-r}+{\frac {1-q^{m-r}}{1-q^{r}}}}$

代わりに、2番目の類似点を示します。

q-二項係数に対する二項定理の類似物として、コーシーの二項定理が存在する。

${\displaystyle \prod _{k=0}^{n-1}(1+q^{k}t)=\sum _{k=0}^{n}q^{k(k-1)/2}{n \choose k}_{\!q}t^{k}.}$

通常の二項定理と同様に、この公式には多くの一般化と拡張があります。負のべき乗に対するニュートンの一般化二項定理に対応するその1つは次のとおりです。

${\displaystyle \prod _{k=0}^{n-1}{\frac {1}{1-q^{k}t}}=\sum _{k=0}^{\infty }{n+k-1 \choose k}_{\!q}t^{k}.}$

極限では${\displaystyle n\rightarrow \infty }$これらの式は、

${\displaystyle \prod _{k=0}^{\infty }(1+q^{k}t)=\sum _{k=0}^{\infty }{\frac {q^{k(k-1)/2}t^{k}}{[k]_{q}!\,(1-q)^{k}}}}$

そして

${\displaystyle \prod _{k=0}^{\infty }{\frac {1}{1-q^{k}t}}=\sum _{k=0}^{\infty }{\frac {t^{k}}{[k]_{q}!\,(1-q)^{k}}}}$。

設定${\displaystyle t=q}$それぞれ、異なる部分と任意の部分を持つ分割を数える生成関数を与える。

通常の二項係数を用いると、次のようになります。

${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}^{\!2}={\binom {2n}{n}}}$

q二項係数の場合、類似の式は次のようになります。

${\displaystyle \sum _{k=0}^{n}q^{k^{2}}{\binom {n}{k}}_{\!q}^{\!2}={\binom {2n}{n}}_{\!q}}$

ガウスはもともと、二次ガウス和の符号を決定する際にガウス二項係数を使用していた。^{[ 3 ]}

ガウス二項係数は、対称多項式の計数や分割理論に現れる。 q ^rの係数は

${\displaystyle {n+m \choose m}_{\!q}}$

は、 rをm以下個に分割し、各部分がn以下であるような分割の数です。言い換えれば、 rをn以下個に分割し、各部分がm以下であるような分割の数でもあります。

ガウス二項係数は、有限体上で定義された射影空間の列挙理論においても重要な役割を果たします。特に、すべての有限体に対して${\displaystyle \mathbb {F} _{q}}$q個の要素を持つガウス二項係数

${\displaystyle {n \choose k}_{\!q}}$

n次元ベクトル空間のk 次元ベクトル部分空間の数を数える${\displaystyle \mathbb {F} _{q}}$（グラスマン多様体の点）。qの多項式として展開すると、グラスマン多様体のシューベルトセルへのよく知られた分解が得られます。例えば、ガウス二項係数

${\displaystyle {n \choose 1}_{\!q}=1+q+q^{2}+\cdots +q^{n-1}}$

は ( F _q ) ⁿにおける 1 次元部分空間の数、または同等に、関連する射影空間内の点の数です。さらに、qが 1 (または −1) の場合、ガウス二項係数は、対応する複素 (または実数) グラスマン多様体のオイラー標数を与えます。

F _q ⁿのk次元アフィン部分空間の数は、

${\displaystyle q^{n-k}{n \choose k}_{\!q}}$。

これにより、アイデンティティの別の解​​釈が可能になる。

${\displaystyle {m \choose r}_{\!q}={m-1 \choose r}_{\!q}+q^{m-r}{m-1 \choose r-1}_{\!q}}$

( m -1)次元射影空間の( r -1)次元部分空間を、ある超平面を固定し、その超平面に含まれる部分空間を数え、次にその超平面に含まれない部分空間を数えることによって数える。後者の部分空間は、この固定された超平面を無限遠の超平面として扱うことによって得られる空間の( r -1)次元アフィン部分空間と一対一に対応する。

ガウス二項係数は、巡回篩分け現象において重要な役割を果たします。Cを生成元cを持つ位数nの巡回群とします。Xをn要素集合 {1, 2, ..., n }のk要素部分集合の集合とします。群C は、c を巡回置換(1, 2, ..., n )に 送ることによって与えられるXに対する標準作用を持ちます。X上のc ^dの不動点の数は、

${\displaystyle {\binom {n}{k}}_{\!q}}$

ここで、 qは原始的な n 乗根のd乗とします。

量子群への応用で一般的に用いられる慣例では、少し異なる定義が用いられます。量子二項係数は

${\displaystyle q^{k^{2}-nk}{n \choose k}_{\!q^{2}}}$。

この量子二項係数のバージョンは、交換に対して対称である。${\displaystyle q}$そして${\displaystyle q^{-1}}$。