Gaussian binomial coefficient

Template:Short description Template:Use American English Template:More footnotes needed In mathematics, the Gaussian binomial coefficients (also called Gaussian coefficients, Gaussian polynomials, or q-binomial coefficients) are q-analogs of the binomial coefficients. The Gaussian binomial coefficient, written as <math> \binom nk_q</math> or <math>\begin{bmatrix}n\\ k\end{bmatrix}_q</math>, is a polynomial in q with integer coefficients, whose value when q is set to a prime power counts the number of subspaces of dimension k in a vector space of dimension n over <math>\mathbb{F}_q</math>, a finite field with q elements; i.e. it is the number of points in the finite Grassmannian <math>\mathrm{Gr}(k, \mathbb{F}_q^n)</math>.

DefinitionEdit

The Gaussian binomial coefficients are defined by:<ref>Mukhin, Eugene, chapter 3</ref>

<math>{m \choose r}_q

= \frac{(1-q^m)(1-q^{m-1})\cdots(1-q^{m-r+1})} {(1-q)(1-q^2)\cdots(1-q^r)} </math>

where m and r are non-negative integers. If Template:Math, this evaluates to 0. For Template:Math, the value is 1 since both the numerator and denominator are empty products.

Although the formula at first appears to be a rational function, it actually is a polynomial, because the division is exact in Z[q]

All of the factors in numerator and denominator are divisible by Template:Math, and the quotient is the q-number:

<math>[k]_q=\sum_{0\leq i<k}q^i=1+q+q^2+\cdots+q^{k-1}=

\begin{cases} \frac{1-q^k}{1-q} & \text{for} & q \neq 1 \\ k & \text{for} & q = 1 \end{cases},</math>

Dividing out these factors gives the equivalent formula

<math>{m \choose r}_q=\frac{[m]_q[m-1]_q\cdots[m-r+1]_q}{[1]_q[2]_q\cdots[r]_q}\quad(r\leq m).</math>

In terms of the q factorial <math>[n]_q!=[1]_q[2]_q\cdots[n]_q</math>, the formula can be stated as

<math>{m \choose r}_q=\frac{[m]_q!}{[r]_q!\,[m-r]_q!}\quad(r\leq m).</math>

Substituting Template:Math into <math>\tbinom mr_q</math> gives the ordinary binomial coefficient <math>\tbinom mr</math>.

The Gaussian binomial coefficient has finite values as <math>m\rightarrow \infty</math>:

<math>{\infty \choose r}_q = \lim_{m\rightarrow \infty} {m \choose r}_q = \frac{1} {(1-q)(1-q^2)\cdots(1-q^r)} = \frac{1}{[r]_q!\,(1-q)^r}</math>

ExamplesEdit

<math>{0 \choose 0}_q = {1 \choose 0}_q = 1</math>

<math>{1 \choose 1}_q = \frac{1-q}{1-q}=1</math>

<math>{2 \choose 1}_q = \frac{1-q^2}{1-q}=1+q</math>

<math>{3 \choose 1}_q = \frac{1-q^3}{1-q}=1+q+q^2</math>

<math>{3 \choose 2}_q = \frac{(1-q^3)(1-q^2)}{(1-q)(1-q^2)}=1+q+q^2</math>

<math>{4 \choose 2}_q = \frac{(1-q^4)(1-q^3)}{(1-q)(1-q^2)}=(1+q^2)(1+q+q^2)=1+q+2q^2+q^3+q^4</math>

<math>{6 \choose 3}_q = \frac{(1-q^6)(1-q^5)(1-q^4)}{(1-q)(1-q^2)(1-q^3)}=(1+q^2)(1+q^3)(1+q+q^2+q^3+q^4)=1 + q + 2 q^2 + 3 q^3 + 3 q^4 + 3 q^5 + 3 q^6 + 2 q^7 + q^8 + q^9</math>

Combinatorial descriptionsEdit

InversionsEdit

One combinatorial description of Gaussian binomial coefficients involves inversions.

The ordinary binomial coefficient <math>\tbinom mr</math> counts the Template:Math-combinations chosen from an Template:Math-element set. If one takes those Template:Math elements to be the different character positions in a word of length Template:Math, then each Template:Math-combination corresponds to a word of length Template:Math using an alphabet of two letters, say Template:Math with Template:Math copies of the letter 1 (indicating the positions in the chosen combination) and Template:Math letters 0 (for the remaining positions).

So, for example, the <math>{4 \choose 2} = 6</math> words using 0s and 1s are <math>0011, 0101, 0110, 1001, 1010, 1100</math>.

To obtain the Gaussian binomial coefficient <math>\tbinom mr_q</math>, each word is associated with a factor Template:Math, where Template:Math is the number of inversions of the word, where, in this case, an inversion is a pair of positions where the left of the pair holds the letter 1 and the right position holds the letter 0.

With the example above, there is one word with 0 inversions, <math>0011</math>, one word with 1 inversion, <math>0101</math>, two words with 2 inversions, <math>0110</math>, <math>1001</math>, one word with 3 inversions, <math>1010</math>, and one word with 4 inversions, <math>1100</math>. This is also the number of left-shifts of the 1s from the initial position.

These correspond to the coefficients in <math>{4 \choose 2}_q = 1+q+2q^2+q^3+q^4</math>.

Another way to see this is to associate each word with a path across a rectangular grid with height Template:Math and width Template:Math, going from the bottom left corner to the top right corner. The path takes a step right for each 0 and a step up for each 1. An inversion switches the directions of a step (right+up becomes up+right and vice versa), hence the number of inversions equals the area under the path.

Balls into binsEdit

Let <math>B(n,m,r)</math> be the number of ways of throwing <math>r</math> indistinguishable balls into <math>m</math> indistinguishable bins, where each bin can contain up to <math>n</math> balls. The Gaussian binomial coefficient can be used to characterize <math>B(n,m,r)</math>. Indeed,

<math>B(n,m,r)= [q^r] {n+m \choose m}_q. </math>

where <math>[q^r]P</math> denotes the coefficient of <math>q^r</math> in polynomial <math>P</math> (see also Applications section below).

PropertiesEdit

ReflectionEdit

Like the ordinary binomial coefficients, the Gaussian binomial coefficients are center-symmetric, i.e., invariant under the reflection <math> r \mapsto m-r </math>:

<math>{m \choose r}_q = {m \choose m-r}_q. </math>

In particular,

<math>{m \choose 0}_q ={m \choose m}_q=1 \, ,</math>

<math>{m \choose 1}_q ={m \choose m-1}_q=\frac{1-q^m}{1-q}=1+q+ \cdots + q^{m-1} \quad m \ge 1 \, .</math>

Limit at q = 1Edit

The evaluation of a Gaussian binomial coefficient at Template:Nowrap is

<math>\lim_{q \to 1} \binom{m}{r}_q = \binom{m}{r}</math>

i.e. the sum of the coefficients gives the corresponding binomial value.

Degree of polynomialEdit

The degree of <math>\binom{m}{r}_q</math> is <math>\binom{m+1}{2}-\binom{r+1}{2}-\binom{(m-r)+1}{2} = r(m-r)</math>.

q identitiesEdit

Analogs of Pascal's identityEdit

The analogs of Pascal's identity for the Gaussian binomial coefficients are:<ref>Mukhin, Eugene, chapter 3</ref>

<math>{m \choose r}_q = q^r {m-1 \choose r}_q + {m-1 \choose r-1}_q</math>

and

<math>{m \choose r}_q = {m-1 \choose r}_q + q^{m-r}{m-1 \choose r-1}_q.</math>

When <math>q=1</math>, these both give the usual binomial identity. We can see that as <math>m\to\infty</math>, both equations remain valid.

The first Pascal analog allows computation of the Gaussian binomial coefficients recursively (with respect to m ) using the initial values

<math>{m \choose m}_q ={m \choose 0}_q=1 </math>

and also shows that the Gaussian binomial coefficients are indeed polynomials (in q).

The second Pascal analog follows from the first using the substitution <math> r \rightarrow m-r </math> and the invariance of the Gaussian binomial coefficients under the reflection <math> r \rightarrow m-r </math>.

These identities have natural interpretations in terms of linear algebra. Recall that <math>\tbinom{m}{r}_q</math> counts r-dimensional subspaces <math>V\subset \mathbb{F}_q^m</math>, and let <math>\pi:\mathbb{F}_q^m \to \mathbb{F}_q^{m-1} </math> be a projection with one-dimensional nullspace <math>E_1 </math>. The first identity comes from the bijection which takes <math>V\subset \mathbb{F}_q^m </math> to the subspace <math>V' = \pi(V)\subset \mathbb{F}_q^{m-1}</math>; in case <math>E_1\not\subset V</math>, the space <math>V'</math> is r-dimensional, and we must also keep track of the linear function <math>\phi:V'\to E_1</math> whose graph is <math>V</math>; but in case <math>E_1\subset V</math>, the space <math>V'</math> is (r−1)-dimensional, and we can reconstruct <math>V=\pi^{-1}(V')</math> without any extra information. The second identity has a similar interpretation, taking <math>V</math> to <math>V' = V\cap E_{n-1}</math> for an (m−1)-dimensional space <math>E_{m-1}</math>, again splitting into two cases.

Proofs of the analogsEdit

Both analogs can be proved by first noting that from the definition of <math>\tbinom{m}{r}_q</math>, we have:

Template:NumBlk \binom{m-1}{r}_q</math>|Template:EquationRef}}

Template:NumBlk

Template:NumBlk\binom{m-1}{r}_q = \binom{m-1}{r-1}_q</math>|Template:EquationRef}}

As

Equation (Template:EquationNote) becomes:

<math>\binom{m}{r}_q = q^r\binom{m-1}{r}_q + \frac{1-q^r}{1-q^{m-r}}\binom{m-1}{r}_q</math>

and substituting equation (Template:EquationNote) gives the first analog.

A similar process, using

instead, gives the second analog.

q-binomial theoremEdit

There is an analog of the binomial theorem for q-binomial coefficients, known as the Cauchy binomial theorem:

<math>\prod_{k=0}^{n-1} (1+q^kt)=\sum_{k=0}^n q^{k(k-1)/2}

{n \choose k}_q t^k .</math>

Like the usual binomial theorem, this formula has numerous generalizations and extensions; one such, corresponding to Newton's generalized binomial theorem for negative powers, is

<math>\prod_{k=0}^{n-1} \frac{1}{1-q^kt}=\sum_{k=0}^\infty

{n+k-1 \choose k}_q t^k. </math>

In the limit <math>n\rightarrow\infty</math>, these formulas yield

<math>\prod_{k=0}^{\infty} (1+q^kt)=\sum_{k=0}^\infty \frac{q^{k(k-1)/2}t^k}{[k]_q!\,(1-q)^k}</math>

and

<math>\prod_{k=0}^\infty \frac{1}{1-q^kt}=\sum_{k=0}^\infty

\frac{t^k}{[k]_q!\,(1-q)^k}</math>.

Setting <math>t=q</math> gives the generating functions for distinct and any parts respectively. (See also Basic hypergeometric series.)

Central q-binomial identityEdit

With the ordinary binomial coefficients, we have:

<math>\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}</math>

With q-binomial coefficients, the analog is:

<math>\sum_{k=0}^n q^{k^2}\binom{n}{k}_q^2 = \binom{2n}{n}_q</math>

ApplicationsEdit

Gauss originally used the Gaussian binomial coefficients in his determination of the sign of the quadratic Gauss sum.<ref>Template:Cite book</ref>

Gaussian binomial coefficients occur in the counting of symmetric polynomials and in the theory of partitions. The coefficient of q^r in

<math>{n+m \choose m}_q</math>

is the number of partitions of r with m or fewer parts each less than or equal to n. Equivalently, it is also the number of partitions of r with n or fewer parts each less than or equal to m.

Gaussian binomial coefficients also play an important role in the enumerative theory of projective spaces defined over a finite field. In particular, for every finite field F_q with q elements, the Gaussian binomial coefficient

<math>{n \choose k}_q</math>

counts the number of k-dimensional vector subspaces of an n-dimensional vector space over F_q (a Grassmannian). When expanded as a polynomial in q, it yields the well-known decomposition of the Grassmannian into Schubert cells. For example, the Gaussian binomial coefficient

<math>{n \choose 1}_q=1+q+q^2+\cdots+q^{n-1}</math>

is the number of one-dimensional subspaces in (F_q)ⁿ (equivalently, the number of points in the associated projective space). Furthermore, when q is 1 (respectively −1), the Gaussian binomial coefficient yields the Euler characteristic of the corresponding complex (respectively real) Grassmannian.

The number of k-dimensional affine subspaces of F_qⁿ is equal to

<math>q^{n-k} {n \choose k}_q</math>.

This allows another interpretation of the identity

<math>{m \choose r}_q = {m-1 \choose r}_q + q^{m-r}{m-1 \choose r-1}_q</math>

as counting the (r − 1)-dimensional subspaces of (m − 1)-dimensional projective space by fixing a hyperplane, counting such subspaces contained in that hyperplane, and then counting the subspaces not contained in the hyperplane; these latter subspaces are in bijective correspondence with the (r − 1)-dimensional affine subspaces of the space obtained by treating this fixed hyperplane as the hyperplane at infinity.

In the conventions common in applications to quantum groups, a slightly different definition is used; the quantum binomial coefficient there is

<math>q^{k^2 - n k}{n \choose k}_{q^2}</math>.

This version of the quantum binomial coefficient is symmetric under exchange of <math>q</math> and <math>q^{-1}</math>.

ReferencesEdit

Template:Reflist

Exton, H. (1983), q-Hypergeometric Functions and Applications, New York: Halstead Press, Chichester: Ellis Horwood, 1983, Template:ISBN, Template:ISBN, Template:ISBN
{{#invoke:citation/CS1|citation

|CitationClass=web }} (undated, 2004 or earlier).

Ratnadha Kolhatkar, Zeta function of Grassmann Varieties (dated January 26, 2004)
{{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web

|_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:q-BinomialCoefficient%7Cq-BinomialCoefficient.html}} |title = q-Binomial Coefficient |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}

|CitationClass=web }} (2009).