Gaussian binomial coefficient explained

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 nk _{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 F _{q} , a finite field with q elements; i.e. it is the number of points in the finite Grassmannian Gr (k, F ^{n)} _{q} .

Definition

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

{m \choose r} _{q =} (( 1- q ^{m)(1-q} ^{m-1} ) … ( 1- q ^{m-r+1} ))/(( 1- q)( 1- q ^{2) … (1-q} ^{r)})

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

[k] _{q=\sum} _{0\leq} q ^{i=1+q+q} ^{2+ … +q} ^{k-1} = \begin{cases} (1- q ^{k})/(1- q) & for & q ≠ 1 \\ k & for & q = 1 \end{cases},

Dividing out these factors gives the equivalent formula

{m \choose r} _{q = ([m] _{q[m-1]} _{q … [m-r+1]} _{q})/([ 1 ] _{q[2]} _{q … [r]} _{q})} (r\leq m). [n] _{q!=[1]} _{q[2]} _{q … [n]} _{q} , the formula can be stated as{m \choose r} _{q = ([m] _{q!})/([r] _{q![m-r]} _{q!})} (r\leq m).

Substituting into

\tbinom mr _{q} gives the ordinary binomial coefficient \tbinom mr .

The Gaussian binomial coefficient has finite values as

m → inf ty :{ inf ty \choose r} _{q} = \lim _{m →} {m \choose r} _{q} = (1)/(( 1- q)( 1- q ^{2) … (1-q} ^{r)}) = (1)/([r] ^{r} _{q!( 1- q)})

Examples

{ 0 \choose 0 } _{q} = { 1 \choose 0 } _{q} = 1 { 1 \choose 1 } _{q} = (1- q)/(1- q) =1 { 2 \choose 1 } _{q} = (1- q ^{2})/(1- q) =1+ q { 3 \choose 1 } _{q} = (1- q ^{3})/(1- q) =1+ q + q ^{2} { 3 \choose 2 } _{q} = (( 1- q ^{3)(1-q} ^{2)})/(( 1- q)( 1- q ^{2)}) =1+ q + q ^{2} { 4 \choose 2 } _{q} = (( 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} { 6 \choose 3 } _{q} = (( 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}

Combinatorial descriptions

Inversions

One combinatorial description of Gaussian binomial coefficients involves inversions.

The ordinary binomial coefficient

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

So, for example, the

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

To obtain the Gaussian binomial coefficient

\tbinom mr _{q} , each word is associated with a factor, where 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,

0011 , one word with 1 inversion, 0101 , two words with 2 inversions, 0110 , 1001 , one word with 3 inversions, 1010 , and one word with 4 inversions, 1100 . This is also the number of left-shifts of the 1s from the initial position.

These correspond to the coefficients in

{ 4 \choose 2 } _{q} = 1+ q +2 q ^{2+q} ^{3+q} ^{4} .

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

B(n,m,r) be the number of ways of throwing r indistinguishable balls into m indistinguishable bins, 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

Reflection

Like the ordinary binomial coefficients, the Gaussian binomial coefficients are center-symmetric, i.e., invariant under the reflection

r → 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 = (1- q ^{m})/(1- q)} =1+ q + … + q ^{m-1} m \ge 1 .

Limit at q = 1

The evaluation of a Gaussian binomial coefficient at is

\lim _{q} \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

\binom{m}{r} _{q} is \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]

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

When

q =1 , these both give the usual binomial identity. We can see that as m\to inf ty , both equations remain valid.

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

{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

r → m - r and the invariance of the Gaussian binomial coefficients under the reflection r → m - r .

These identities have natural interpretations in terms of linear algebra. Recall that

\tbinom{m}{r} _{q} counts r-dimensional subspaces V\subset F ^{m} _{q} , and let \pi: F ^{m} _{q} \to F ^{m -1} _{q} be a projection with one-dimensional nullspace E _{1} . The first identity comes from the bijection which takes V\subset F ^{m} _{q} to the subspace V' = \pi(V)\subset F ^{m -1} _{q} ; in case E _{1\not\subset} V , the space V' is r-dimensional, and we must also keep track of the linear function \phi:V'\to E _{1} whose graph is V ; but in case E _{1\subset} V , the space V' is (r−1)-dimensional, and we can reconstruct V = \pi ^{-1} (V') without any extra information. The second identity has a similar interpretation, taking V to V' = V\cap E _{n-1} for an (m−1)-dimensional space 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

\tbinom{m}{r} _{q} , we have:

As

(1- q ^{m})/(= 1- q ^{m-r}) (1- q ^{r+q} ^{r-q} ^{m})/(1- q ^{m-r}) = q ^{r + (1- q ^{r})/(1- q ^{m-r})}

Equation becomes:

\binom{m}{r} _{q} = q ^{r\binom{m -1 }{r}} _{q} + (1- q ^{r})/(1- q ^{m-r}) \binom{m -1 }{r} _{q}

and substituting equation gives the first analog.

A similar process, using

(1- q ^{m})/(1- q ^{r}) = q ^{m-r} + (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:

\prod ^{n -1} _{k =0} ( 1+ q ^{n} _{k =0} 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

\prod ^{n -1} _{k =0} (1)/(1- q ^{kt}) = \sum ^{inf ty} _{k =0} {n + k -1 \choose k} _{q} t ^{k.}

In the limit

n → inf ty , these formulas yield\prod ^{inf ty} _{k =0} ( 1+ q ^{inf ty} _{k =0} (q ^{k(k-1)/2} t ^{k})/([k] ^{k} _{q!( 1- q)})

and

\prod ^{inf ty} _{k =0} (1)/(1- q ^{kt}) = \sum ^{inf ty} _{k =0} (t ^{k})/([k] ^{k} _{q!( 1- q)}) .

Setting

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:

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

With q-binomial coefficients, the analog is:

\sum ^{n} _{k =0} q ^{k ^{2}} \binom{n}{k} ^{2} _{q} = \binom{ 2 n}{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

{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 } ^{2+ … + q} _{q =1+ q + 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} - n k} {n \choose k} _{q ^{2}} .This version of the quantum binomial coefficient is symmetric under exchange of q and q ^{-1} .

See also

• List of q-analogs

References

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

Notes and References

1. Mukhin, Eugene, chapter 3
2. Mukhin, Eugene, chapter 3
3. Gauß . Carl Friedrich . 1808 . Summatio quarumdam serierum singularium . LA.