Gaussian binomial coefficient

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 ${\displaystyle {\binom {n}{k}}_{q}}$ or ${\displaystyle {\begin{bmatrix}n\\k\end{bmatrix}}_{q}}$, 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 ${\displaystyle \mathbb {F} _{q}}$, a finite field with q elements; i.e. it is the number of points in the finite Grassmannian ${\displaystyle \mathrm {Gr} (k,\mathbb {F} _{q}^{n})}$.

Definition

The Gaussian binomial coefficients are defined by: ^[1]

${\displaystyle {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})}}}$

where m and r are non-negative integers. If r > m, this evaluates to 0. For r = 0, 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 1 − q, and the quotient is the q-number:

${\displaystyle [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}},}$

Dividing out these factors gives the equivalent formula

${\displaystyle {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).}$

In terms of the q factorial ${\displaystyle [n]_{q}!=[1]_{q}[2]_{q}\cdots [n]_{q}}$, the formula can be stated as

${\displaystyle {m \choose r}_{q}={\frac {[m]_{q}!}{[r]_{q}!\,[m-r]_{q}!}}\quad (r\leq m).}$

Substituting q = 1 into ${\displaystyle {\tbinom {m}{r}}_{q}}$ gives the ordinary binomial coefficient ${\displaystyle {\tbinom {m}{r}}}$.

The Gaussian binomial coefficient has finite values as ${\displaystyle m\rightarrow \infty }$:

${\displaystyle {\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}}}}$

Examples

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

${\displaystyle {1 \choose 1}_{q}={\frac {1-q}{1-q}}=1}$

${\displaystyle {2 \choose 1}_{q}={\frac {1-q^{2}}{1-q}}=1+q}$

${\displaystyle {3 \choose 1}_{q}={\frac {1-q^{3}}{1-q}}=1+q+q^{2}}$

${\displaystyle {3 \choose 2}_{q}={\frac {(1-q^{3})(1-q^{2})}{(1-q)(1-q^{2})}}=1+q+q^{2}}$

${\displaystyle {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}}$

${\displaystyle {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+2q^{2}+3q^{3}+3q^{4}+3q^{5}+3q^{6}+2q^{7}+q^{8}+q^{9}}$

Combinatorial descriptions

Inversions

One combinatorial description of Gaussian binomial coefficients involves inversions.

The ordinary binomial coefficient ${\displaystyle {\tbinom {m}{r}}}$ counts the r-combinations chosen from an m-element set. If one takes those m elements to be the different character positions in a word of length m, then each r-combination corresponds to a word of length m using an alphabet of two letters, say {0,1}, with r copies of the letter 1 (indicating the positions in the chosen combination) and m − r letters 0 (for the remaining positions).

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

To obtain the Gaussian binomial coefficient ${\displaystyle {\tbinom {m}{r}}_{q}}$, each word is associated with a factor q^d, where d 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, ${\displaystyle 0011}$, one word with 1 inversion, ${\displaystyle 0101}$, two words with 2 inversions, ${\displaystyle 0110}$, ${\displaystyle 1001}$, one word with 3 inversions, ${\displaystyle 1010}$, and one word with 4 inversions, ${\displaystyle 1100}$. This is also the number of left-shifts of the 1s from the initial position.

These correspond to the coefficients in ${\displaystyle {4 \choose 2}_{q}=1+q+2q^{2}+q^{3}+q^{4}}$.

Another way to see this is to associate each word with a path across a rectangular grid with height r and width m − r, 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 bins

Let ${\displaystyle B(n,m,r)}$ be the number of ways of throwing ${\displaystyle r}$ indistinguishable balls into ${\displaystyle m}$ indistinguishable bins, where each bin can contain up to ${\displaystyle n}$ balls. The Gaussian binomial coefficient can be used to characterize ${\displaystyle B(n,m,r)}$. Indeed,

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

where ${\displaystyle [q^{r}]P}$ denotes the coefficient of ${\displaystyle q^{r}}$ in polynomial ${\displaystyle P}$ (see also Applications section below).

Properties

Reflection

Like the ordinary binomial coefficients, the Gaussian binomial coefficients are center-symmetric, i.e., invariant under the reflection ${\displaystyle r\rightarrow m-r}$:

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

In particular,

${\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\,.}$

Limit at q = 1

The evaluation of a Gaussian binomial coefficient at q = 1 is

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

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

Degree of polynomial

The degree of ${\displaystyle {\binom {m}{r}}_{q}}$ is ${\displaystyle {\binom {m+1}{2}}-{\binom {r+1}{2}}-{\binom {(m-r)+1}{2}}=r(m-r)}$.

q identities

Analogs of Pascal's identity

The analogs of Pascal's identity for the Gaussian binomial coefficients are: ^[2]

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

and

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

When ${\displaystyle q=1}$, these both give the usual binomial identity. We can see that as ${\displaystyle m\to \infty }$, both equations remain valid.

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

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

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

The second Pascal analog follows from the first using the substitution ${\displaystyle r\rightarrow m-r}$ and the invariance of the Gaussian binomial coefficients under the reflection ${\displaystyle r\rightarrow m-r}$.

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

Proofs of the analogs

Both analogs can be proved by first noting that from the definition of ${\displaystyle {\tbinom {m}{r}}_{q}}$, we have:

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

(1)

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

(2)

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

(3)

As

${\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}}}}$

Equation ( 1 ) becomes:

${\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}}$

and substituting equation ( 3 ) gives the first analog.

A similar process, using

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

instead, gives the second analog.

q-binomial theorem

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

${\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}.}$

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

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

In the limit ${\displaystyle n\rightarrow \infty }$, these formulas yield

${\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}}}}$

and

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

Setting ${\displaystyle t=q}$ gives the generating functions for distinct and any parts respectively. (See also Basic hypergeometric series.)

Central q-binomial identity

With the ordinary binomial coefficients, we have:

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

With q-binomial coefficients, the analog is:

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

Applications

Gauss originally used the Gaussian binomial coefficients in his determination of the sign of the quadratic Gauss sum. ^[3]

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

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

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

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

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

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

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

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

This allows another interpretation of the identity

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

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

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

This version of the quantum binomial coefficient is symmetric under exchange of ${\displaystyle q}$ and ${\displaystyle q^{-1}}$.

See also

• List of q-analogs

References

1. Mukhin, Eugene, chapter 3
2. Mukhin, Eugene, chapter 3
3. Gauß, Carl Friedrich (1808). "Summatio quarumdam serierum singularium" (in Latin).{{cite journal}}: Cite journal requires |journal= (help)

• Exton, H. (1983), q-Hypergeometric Functions and Applications, New York: Halstead Press, Chichester: Ellis Horwood, 1983, ISBN   0853124914, ISBN   0470274530, ISBN   978-0470274538
• Mukhin, Eugene. "Symmetric Polynomials and Partitions" (PDF). Archived from the original (PDF) on March 4, 2016. (undated, 2004 or earlier).
• Ratnadha Kolhatkar, Zeta function of Grassmann Varieties (dated January 26, 2004)
• Weisstein, Eric W. "q-Binomial Coefficient". MathWorld .
• Gould, Henry (1969). "The bracket function and Fontene-Ward generalized binomial coefficients with application to Fibonomial coefficients". Fibonacci Quarterly . 7: 23–40. MR   0242691.
• Alexanderson, G. L. (1974). "A Fibonacci analogue of Gaussian binomial coefficients". Fibonacci Quarterly . 12: 129–132. MR   0354537.
• Andrews, George E. (1974). "Applications of basic hypergeometric functions". SIAM Rev. 16 (4): 441–484. doi:10.1137/1016081. JSTOR   2028690. MR   0352557.
• Borwein, Peter B. (1988). "Padé approximants for the q-elementary functions". Construct. Approx. 4 (1): 391–402. doi:10.1007/BF02075469. MR   0956175. S2CID   124884851.
• Konvalina, John (1998). "Generalized binomial coefficients and the subset-subspace problem". Adv. Appl. Math. 21 (2): 228–240. doi: 10.1006/aama.1998.0598 . MR   1634713.
• Di Bucchianico, A. (1999). "Combinatorics, computer algebra and the Wilcoxon-Mann-Whitney test". J. Stat. Plann. Inf. 79 (2): 349–364. CiteSeerX   10.1.1.11.7713 . doi:10.1016/S0378-3758(98)00261-4.
• Konvalina, John (2000). "A unified interpretation of the Binomial Coefficients, the Stirling numbers, and the Gaussian coefficients". Amer. Math. Monthly. 107 (10): 901–910. doi:10.2307/2695583. JSTOR   2695583. MR   1806919.
• Kupershmidt, Boris A. (2000). "q-Newton binomial: from Euler to Gauss". J. Nonlinear Math. Phys. 7 (2): 244–262. arXiv: math/0004187 . Bibcode:2000JNMP....7..244K. doi:10.2991/jnmp.2000.7.2.11. MR   1763640. S2CID   125273424.
• Cohn, Henry (2004). "Projective geometry over F₁ and the Gaussian Binomial Coefficients". Amer. Math. Monthly. 111 (6): 487–495. doi:10.2307/4145067. JSTOR   4145067. MR   2076581.
• Kim, T. (2007). "q-Extension of the Euler formula and trigonometric functions". Russ. J. Math. Phys. 14 (3): –275–278. Bibcode:2007RJMP...14..275K. doi:10.1134/S1061920807030041. MR   2341775. S2CID   122865930.
• Kim, T. (2008). "q-Bernoulli numbers and polynomials associated with Gaussian binomial coefficients". Russ. J. Math. Phys. 15 (1): 51–57. Bibcode:2008RJMP...15...51K. doi:10.1134/S1061920808010068. MR   2390694. S2CID   122966597.
• Corcino, Roberto B. (2008). "On p,q-binomial coefficients". Integers. 8: #A29. MR   2425627.
• Hmayakyan, Gevorg. "Recursive Formula Related To The Mobius Function" (PDF). (2009).