In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the Gaussian binomial coefficients (also called Gaussian coefficients, Gaussian polynomials, or ''q''-binomial coefficients) are
''q''-analogs of the
binomial coefficients
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
. 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
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
with ''q'' elements; i.e. it is the number of points in the finite
Grassmannian
In mathematics, the Grassmannian is a space that parameterizes all -Dimension, dimensional linear subspaces of the -dimensional vector space . For example, the Grassmannian is the space of lines through the origin in , so it is the same as the ...
.
Definition
The Gaussian binomial coefficients are defined by:
:
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 product
In mathematics, an empty product, or nullary product or vacuous product, is the result of multiplying no factors. It is by convention equal to the multiplicative identity (assuming there is an identity for the multiplication operation in question ...
s.
Although the formula at first appears to be a
rational function
In mathematics, a rational function is any function that can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the polynomials need not be rat ...
, it actually is a polynomial, because the division is exact in Z
''q''">/nowiki>''q''/nowiki>
All of the factors in numerator and denominator are divisible by , 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 into gives the ordinary binomial coefficient .
The Gaussian binomial coefficient has finite values as :
:
Examples
:
:
:
:
:
:
:
Combinatorial descriptions
Inversions
One combinatorial description of Gaussian binomial coefficients involves inversions.
The ordinary binomial coefficient counts the -combination
In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are th ...
s 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 words using ''0''s and ''1''s are .
To obtain the Gaussian binomial coefficient , 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, , 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 ''1''s 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 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 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
Reflection
Like the ordinary binomial coefficients, the Gaussian binomial coefficients are center-symmetric, i.e., invariant under the reflection :
:
In particular,
:
:
Limit at q = 1
The evaluation of a Gaussian binomial coefficient at is
:
i.e. the sum of the coefficients gives the corresponding binomial value.
Analogs of Pascal's identity
The analogs of Pascal's identity
In mathematics, Pascal's rule (or Pascal's formula) is a combinatorial identity about binomial coefficients. It states that for positive natural numbers ''n'' and ''k'',
+ = ,
where \tbinom is a binomial coefficient; one interpretation of ...
for the Gaussian binomial coefficients are:[Mukhin, Eugene, chapter 3]
:
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
Both analogs can be proved by first noting that from the definition of , we have:
: