Gaussian binomial coefficient

Template:Short description Template:Use American English Script error: No such module "Unsubst". 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{matrix} n \\ k \end{matrix}]}_{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 $𝔽_{q}$ , a finite field with q elements; i.e. it is the number of points in the finite Grassmannian $G r (k, 𝔽_{q}^{n})$ .

Definition

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

{(\binom{m}{r})}_{q} = \frac{(1 - q^{m}) (1 - q^{m - 1}) \dots (1 - q^{m - r + 1})}{(1 - q) (1 - q^{2}) \dots (1 - q^{r})}

where m and r are non-negative integers. If $r > m$ Script error: No such module "Check for unknown parameters"., this evaluates to 0. For $r = 0$ Script error: No such module "Check for unknown parameters"., 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$ Script error: No such module "Check for unknown parameters"., and the quotient is the q-number:

[k]_{q} = \sum_{0 \leq i < k} q^{i} = 1 + q + q^{2} + \dots + q^{k - 1} = {\begin{cases} \frac{1 - q^{k}}{1 - q} & for & q \neq 1 \\ k & for & q = 1 \end{cases},

Dividing out these factors gives the equivalent formula

{(\binom{m}{r})}_{q} = \frac{[m]_{q} [m - 1]_{q} \dots [m - r + 1]_{q}}{[1]_{q} [2]_{q} \dots [r]_{q}} (r \leq m) .

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

{(\binom{m}{r})}_{q} = \frac{[m]_{q}!}{[r]_{q}! [m - r]_{q}!} (r \leq m) .

Substituting $q = 1$ Script error: No such module "Check for unknown parameters". into ${(\binom{m}{r})}_{q}$ gives the ordinary binomial coefficient $(\binom{m}{r})$ .

The Gaussian binomial coefficient has finite values as $m \to \infty$ :

{(\binom{\infty}{r})}_{q} = \lim_{m \to \infty} {(\binom{m}{r})}_{q} = \frac{1}{(1 - q) (1 - q^{2}) \dots (1 - q^{r})} = \frac{1}{[r]_{q}! (1 - q)^{r}}

Examples

{(\binom{0}{0})}_{q} = {(\binom{1}{0})}_{q} = 1

{(\binom{1}{1})}_{q} = \frac{1 - q}{1 - q} = 1

{(\binom{2}{1})}_{q} = \frac{1 - q^{2}}{1 - q} = 1 + q

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

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

{(\binom{4}{2})}_{q} = \frac{(1 - q^{4}) (1 - q^{3})}{(1 - q) (1 - q^{2})} = (1 + q^{2}) (1 + q + q^{2}) = 1 + q + 2 q^{2} + q^{3} + q^{4}

{(\binom{6}{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 + 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 $(\binom{m}{r})$ counts the $r$ Script error: No such module "Check for unknown parameters".-combinations chosen from an $m$ Script error: No such module "Check for unknown parameters".-element set. If one takes those $m$ Script error: No such module "Check for unknown parameters". elements to be the different character positions in a word of length $m$ Script error: No such module "Check for unknown parameters"., then each $r$ Script error: No such module "Check for unknown parameters".-combination corresponds to a word of length $m$ Script error: No such module "Check for unknown parameters". using an alphabet of two letters, say ${0,1},$ Script error: No such module "Check for unknown parameters". with $r$ Script error: No such module "Check for unknown parameters". copies of the letter 1 (indicating the positions in the chosen combination) and $m - r$ Script error: No such module "Check for unknown parameters". letters 0 (for the remaining positions).

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

To obtain the Gaussian binomial coefficient ${(\binom{m}{r})}_{q}$ , each word is associated with a factor $q d$ Script error: No such module "Check for unknown parameters"., where $d$ Script error: No such module "Check for unknown parameters". 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 ${(\binom{4}{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 $r$ Script error: No such module "Check for unknown parameters". and width $m - r$ Script error: No such module "Check for unknown parameters"., 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}] {(\binom{n + m}{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 \mapsto m - r$ :

{(\binom{m}{r})}_{q} = {(\binom{m}{m - r})}_{q} .

In particular,

{(\binom{m}{0})}_{q} = {(\binom{m}{m})}_{q} = 1,

{(\binom{m}{1})}_{q} = {(\binom{m}{m - 1})}_{q} = \frac{1 - q^{m}}{1 - q} = 1 + q + \dots + q^{m - 1} m \geq 1 .

Limit at q = 1

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

\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 ${(\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]

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

and

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

When $q = 1$ , these both give the usual binomial identity. We can see that as $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

{(\binom{m}{m})}_{q} = {(\binom{m}{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 \to m - r$ and the invariance of the Gaussian binomial coefficients under the reflection $r \to m - r$ .

These identities have natural interpretations in terms of linear algebra. Recall that ${(\binom{m}{r})}_{q}$ counts r-dimensional subspaces $V \subset 𝔽_{q}^{m}$ , and let $π : 𝔽_{q}^{m} \to 𝔽_{q}^{m - 1}$ be a projection with one-dimensional nullspace $E_{1}$ . The first identity comes from the bijection which takes $V \subset 𝔽_{q}^{m}$ to the subspace $V^{'} = π (V) \subset 𝔽_{q}^{m - 1}$ ; in case $E_{1} \subset̸ V$ , the space $V^{'}$ is r-dimensional, and we must also keep track of the linear function $ϕ : 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 = π^{- 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 ${(\binom{m}{r})}_{q}$ , we have:

Template:NumBlk

As

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

{(\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

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

\prod_{k = 0}^{n - 1} (1 + q^{k} t) = \sum_{k = 0}^{n} q^{k (k - 1) / 2} {(\binom{n}{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_{k = 0}^{n - 1} \frac{1}{1 - q^{k} t} = \sum_{k = 0}^{\infty} {(\binom{n + k - 1}{k})}_{q} t^{k} .

In the limit $n \to \infty$ , these formulas yield

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

.

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

With q-binomial coefficients, the analog is:

\sum_{k = 0}^{n} q^{k^{2}} {(\binom{n}{k})}_{q}^{2} = {(\binom{2 n}{n})}_{q}

Applications

Gauss sums

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

Symmetric polynomials and partitions

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

{(\binom{n + m}{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.

Counting subspaces over a finite field

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

{(\binom{n}{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

{(\binom{n}{1})}_{q} = 1 + q + q^{2} + \dots + 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} {(\binom{n}{k})}_{q}

.

This allows another interpretation of the identity

{(\binom{m}{r})}_{q} = {(\binom{m - 1}{r})}_{q} + q^{m - r} {(\binom{m - 1}{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.

Cyclic sieving phenomena

Script error: No such module "Labelled list hatnote". Gaussian binomial coefficients play an important role in the cyclic sieving phenomenon. Let C be a cyclic group of order n with generator c. Let X be the set of k-element subsets of the n-element set {1, 2, ..., n}. The group C has a canonical action on X given by sending c to the cyclic permutation (1, 2, ..., n). The number of fixed points of c^d on X is equal to

{(\binom{n}{k})}_{q}

where q is taken to be the d-th power of a primitive n-th root of unity.

Quantum groups

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} {(\binom{n}{k})}_{q^{2}}

.

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

References

↑ Mukhin, Eugene, chapter 3
↑ Mukhin, Eugene, chapter 3
↑ Script error: No such module "citation/CS1".

Script error: No such module "Check for unknown parameters".

Exton, H. (1983), q-Hypergeometric Functions and Applications, New York: Halstead Press, Chichester: Ellis Horwood, 1983, Template:ISBN, Template:ISBN, Template:ISBN
Script error: No such module "citation/CS1". (undated, 2004 or earlier).
Ratnadha Kolhatkar, Zeta function of Grassmann Varieties (dated January 26, 2004)
Script error: No such module "Template wrapper".
Script error: No such module "Citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "citation/CS1". (2009).

[1] Mukhin, Eugene, chapter 3

[2] Mukhin, Eugene, chapter 3

[3] Script error: No such module "citation/CS1".

[1]

[2]

[3]

Gaussian binomial coefficient

Contents

Definition

Examples

Combinatorial descriptions

Inversions

Balls into bins

Properties

Reflection

Limit at q = 1

Degree of polynomial

q-identities

Analogs of Pascal's identity

Proofs of the analogs

q-binomial theorem

Central q-binomial identity

Applications

Gauss sums

Symmetric polynomials and partitions

Counting subspaces over a finite field

Cyclic sieving phenomena

Quantum groups

See also

References

Navigation menu

Gaussian binomial coefficient

Definition

Examples

Combinatorial descriptions

Inversions

Balls into bins

Properties

Reflection

Limit at q = 1

Degree of polynomial

q-identities

Analogs of Pascal's identity

Proofs of the analogs

q-binomial theorem

Central q-binomial identity

Applications

Gauss sums

Symmetric polynomials and partitions

Counting subspaces over a finite field

Cyclic sieving phenomena

Quantum groups

See also

References

Navigation menu

Search