Gaussian binomial coefficient

(Redirected from Gaussian 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 or , 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; i.e. it is the number of points in the finite Grassmannian .

Definition

edit

The Gaussian binomial coefficients are defined by:[1]

 

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:

 

Dividing out these factors gives the equivalent formula

 

In terms of the q factorial  , the formula can be stated as

 

Substituting q = 1 into   gives the ordinary binomial coefficient  .

The Gaussian binomial coefficient has finite values as  :

 

Examples

edit
 
 
 
 
 
 
 

Combinatorial descriptions

edit

Inversions

edit

One combinatorial description of Gaussian binomial coefficients involves inversions.

The ordinary binomial coefficient   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 mr letters 0 (for the remaining positions).

So, for example, the   words using 0s and 1s are  .

To obtain the Gaussian binomial coefficient  , each word is associated with a factor qd, 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,  , one word with 1 inversion,  , two words with 2 inversions,  ,  , one word with 3 inversions,  , and one word with 4 inversions,  . This is also the number of left-shifts of the 1s from the initial position.

These correspond to the coefficients in  .

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

edit

Let   be the number of ways of throwing   indistinguishable balls into   indistinguishable bins, where each bin can contain up to   balls. The Gaussian binomial coefficient can be used to characterize  . Indeed,

 

where   denotes the coefficient of   in polynomial   (see also Applications section below).

Properties

edit

Reflection

edit

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

 

In particular,

 
 

Limit at q = 1

edit

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

 

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

Degree of polynomial

edit

The degree of   is  .

q identities

edit

Analogs of Pascal's identity

edit

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

 

and

 

When  , these both give the usual binomial identity. We can see that as  , both equations remain valid.

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

 

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

The second Pascal analog follows from the first using the substitution   and the invariance of the Gaussian binomial coefficients under the reflection  .

These identities have natural interpretations in terms of linear algebra. Recall that   counts r-dimensional subspaces  , and let   be a projection with one-dimensional nullspace  . The first identity comes from the bijection which takes   to the subspace  ; in case  , the space   is r-dimensional, and we must also keep track of the linear function   whose graph is  ; but in case  , the space   is (r−1)-dimensional, and we can reconstruct   without any extra information. The second identity has a similar interpretation, taking   to   for an (m−1)-dimensional space  , again splitting into two cases.

Proofs of the analogs

edit

Both analogs can be proved by first noting that from the definition of  , we have:

  (1)
  (2)
  (3)

As

 

Equation (1) becomes:

 

and substituting equation (3) gives the first analog.

A similar process, using

 

instead, gives the second analog.

q-binomial theorem

edit

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

 

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

 

In the limit  , these formulas yield

 

and

 .

Setting   gives the generating functions for distinct and any parts respectively. (See also Basic hypergeometric series.)

Central q-binomial identity

edit

With the ordinary binomial coefficients, we have:

 

With q-binomial coefficients, the analog is:

 

Applications

edit

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 qr in

 

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 Fq with q elements, the Gaussian binomial coefficient

 

counts the number of k-dimensional vector subspaces of an n-dimensional vector space over Fq (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

 

is the number of one-dimensional subspaces in (Fq)n (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 Fqn is equal to

 .

This allows another interpretation of the identity

 

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

 .

This version of the quantum binomial coefficient is symmetric under exchange of   and  .

See also

edit

References

edit
  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)