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 ${\binom {n}{k}}_{q}$ or ${\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 a finite field with q elements.

Definition

The Gaussian binomial coefficients are defined by

${m \choose r}_{q}={\begin{cases}{\frac {(1-q^{m})(1-q^{m-1})\cdots (1-q^{m-r+1})}{(1-q)(1-q^{2})\cdots (1-q^{r})}}&r\leq m\\0&r>m\end{cases}}$

where m and r are non-negative integers. For r = 0 the value is 1 since numerator and denominator are both empty products. Although the formula in the first clause appears to involve a rational function, it actually designates a polynomial, because the division is exact in Z[q]. Note that the formula can be applied for r = m + 1, and gives 0 due to a factor 1 − q⁰ = 0 in the numerator, in accordance with the second clause (for even larger r the factor 0 remains present in the numerator, but its further factors would involve negative powers of q, whence explicitly stating the second clause is preferable). All of the factors in numerator and denominator are divisible by 1 − q, with as quotient a q number:

$[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

${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),$

which makes evident the fact that substituting q = 1 into ${\tbinom {m}{r}}_{q}$ gives the ordinary binomial coefficient ${\tbinom {m}{r}}.$ In terms of the q factorial $[n]_{q}!=[1]_{q}[2]_{q}\cdots [n]_{q}$, the formula can be stated as

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

a compact form (often given as only definition), which however hides the presence of many common factors in numerator and denominator. This form does make obvious the symmetry ${\tbinom {m}{r}}_{q}={\tbinom {m}{m-r}}_{q}$ for r ≤ m.

Unlike the ordinary binomial coefficient, the Gaussian binomial coefficient has finite values for $m\rightarrow \infty$ (the limit being analytically meaningful for |q|<1):

${\infty \choose r}_{q}=\lim _{m\rightarrow \infty }{m \choose r}_{q}={\frac {1}{[r]_{q}!\,(1-q)^{r}}}$

Examples

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

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

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

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

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

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

Combinatorial description

Instead of these algebraic expressions, one can also give a combinatorial definition of Gaussian binomial coefficients. The ordinary binomial coefficient ${\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).

The ${4 \choose 2}=6$ words using 0s and 1s would be 0011, 0101, 0110, 1001, 1010, 1100.

To obtain from this model the Gaussian binomial coefficient ${\tbinom {m}{r}}_{q}$, it suffices to count each word with a factor q^d, where d is the number of "inversions" of the word: the number of pairs of positions for which the leftmost position of the pair holds a letter 1 and the rightmost position holds a letter 0 in the word. For example, there is one word with 0 inversions, 0011. There is 1 with only a single inversion, 0101. There are two words with 2 inversions, 0110, and 1001. There is one with 3, 1010, and finally one word with 4 inversions, 1100. This corresponds to the coefficients in ${4 \choose 2}_{q}=1+q+2q^{2}+q^{3}+q^{4}$.

It can be shown that the polynomials so defined satisfy the Pascal identities given below, and therefore coincide with the polynomials given by the algebraic definitions. A visual way to view this definition is to associate to each word a path across a rectangular grid with sides of height r and width m − r, from the bottom left corner to the top right corner, taking a step right for each letter 0 and a step up for each letter 1. Then the number of inversions of the word equals the area of the part of the rectangle that is to the bottom-right of the path.

Balls into bins (urns)

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

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

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

Properties

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

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

In particular,

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

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

The name Gaussian binomial coefficient stems from the fact that their evaluation at q = 1 is

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

for all m and r.

The analogs of Pascal identities for the Gaussian binomial coefficients are

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

and

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

There are analogs of the binomial formula, and of Newton's generalized version of it for negative integer exponents, although for the former the Gaussian binomial coefficients themselves do not appear as coefficients:

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

and

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

which, for $n\rightarrow \infty$ become:

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

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

The first Pascal identity allows one to compute the Gaussian binomial coefficients recursively (with respect to m ) using the initial "boundary" values

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

and also incidentally shows that the Gaussian binomial coefficients are indeed polynomials (in q). The second Pascal identity follows from the first using the substitution $r\rightarrow m-r$ and the invariance of the Gaussian binomial coefficients under the reflection $r\rightarrow m-r$. Both Pascal identities together imply

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

which leads (when applied iteratively for m, m − 1, m − 2,....) to an expression for the Gaussian binomial coefficient as given in the definition above.

Applications

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

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

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

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

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

This allows another interpretation of the identity

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

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

This version of the quantum binomial coefficient is symmetric under exchange of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle q} and $q^{-1}$.

Triangles

The Gaussian binomial coefficients can be arranged in a triangle for each q, which is Pascal's triangle for q=1.
Read line by line these triangles form the following sequences in the OEIS:

• A022166 for q= 2
• A022167 for q= 3
• A022168 for q= 4
• A022169 for q= 5
• A022170 for q= 6
• A022171 for q= 7
• A022172 for q= 8
• A022173 for q= 9
• A022174 for q= 10

References

• 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.
• 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.
• 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.
• 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.
• 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).