Gaussian binomial coefficient

The Gaussian binomial coefficients are defined by:Mukhin, Eugene, chapter 3

:$\{m\; \backslash choose\; r\}\_q$

=

\frac{(1-q^m)(1-q^{m-1})\cdots(1-q^{m-r+1})} {(1-q)(1-q^2)\cdots(1-q^r)}

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

:

\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\; \backslash choose\; r\}\_q=\backslash frac\{[m]\_q[m-1]\_q\backslash cdots[m-r+1]\_q\}\{[1]\_q[2]\_q\backslash cdots[r]\_q\}\backslash quad(r\backslash leq\; m).$

In terms of the q factorial $[n]\_q!=[1]\_q[2]\_q\backslash cdots[n]\_q$, the formula can be stated as

:$\{m\; \backslash choose\; r\}\_q=\backslash frac\{[m]\_q!\}\{[r]\_q!\backslash ,[m-r]\_q!\}\backslash quad(r\backslash leq\; m).$

Substituting {{math|q {{=}} 1}} into $\backslash tbinom\; mr\_q$ gives the ordinary binomial coefficient $\backslash tbinom\; mr$.

The Gaussian binomial coefficient has finite values as $m\backslash rightarrow\; \backslash infty$:

:$\{\backslash infty\; \backslash choose\; r\}\_q\; =\; \backslash lim\_\{m\backslash rightarrow\; \backslash infty\}\; \{m\; \backslash choose\; r\}\_q\; =\; \backslash frac\{1\}\; \{(1-q)(1-q^2)\backslash cdots(1-q^r)\}\; =\; \backslash frac\{1\}\{[r]\_q!\backslash ,(1-q)^r\}$

:$\{0\; \backslash choose\; 0\}\_q\; =\; \{1\; \backslash choose\; 0\}\_q\; =\; 1$

:$\{1\; \backslash choose\; 1\}\_q\; =\; \backslash frac\{1-q\}\{1-q\}=1$

:$\{2\; \backslash choose\; 1\}\_q\; =\; \backslash frac\{1-q^2\}\{1-q\}=1+q$

:$\{3\; \backslash choose\; 1\}\_q\; =\; \backslash frac\{1-q^3\}\{1-q\}=1+q+q^2$

:$\{3\; \backslash choose\; 2\}\_q\; =\; \backslash frac\{(1-q^3)(1-q^2)\}\{(1-q)(1-q^2)\}=1+q+q^2$

:$\{4\; \backslash choose\; 2\}\_q\; =\; \backslash 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$

:$\{6\; \backslash choose\; 3\}\_q\; =\; \backslash 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$

One combinatorial description of Gaussian binomial coefficients involves inversions.

The ordinary binomial coefficient $\backslash tbinom\; mr$ counts the {{math|r}}-combinations chosen from an {{math|m}}-element set. If one takes those {{math|m}} elements to be the different character positions in a word of length {{math|m}}, then each {{math|r}}-combination corresponds to a word of length {{math|m}} using an alphabet of two letters, say {{math|{0,1},}} with {{math|r}} copies of the letter 1 (indicating the positions in the chosen combination) and {{math|m − r}} letters 0 (for the remaining positions).

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

To obtain the Gaussian binomial coefficient $\backslash tbinom\; mr\_q$, each word is associated with a factor {{math|q^d}}, where {{math|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, $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\; \backslash choose\; 2\}\_q\; =\; 1+q+2q^2+q^3+q^4$.

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

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\; \backslash choose\; m\}\_q.$

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

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

:$\{m\; \backslash choose\; r\}\_q\; =\; \{m\; \backslash choose\; m-r\}\_q.$

In particular,

:$\{m\; \backslash choose\; 0\}\_q\; =\{m\; \backslash choose\; m\}\_q=1\; \backslash ,\; ,$

:$\{m\; \backslash choose\; 1\}\_q\; =\{m\; \backslash choose\; m-1\}\_q=\backslash frac\{1-q^m\}\{1-q\}=1+q+\; \backslash cdots\; +\; q^\{m-1\}\; \backslash quad\; m\; \backslash ge\; 1\; \backslash ,\; .$

The evaluation of a Gaussian binomial coefficient at {{nowrap|q {{=}} 1}} is

:$\backslash lim\_\{q\; \backslash to\; 1\}\; \backslash binom\{m\}\{r\}\_q\; =\; \backslash binom\{m\}\{r\}$

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

The degree of $\backslash binom\{m\}\{r\}\_q$ is $\backslash binom\{m+1\}\{2\}-\backslash binom\{r+1\}\{2\}-\backslash binom\{(m-r)+1\}\{2\}\; =\; r(m-r)$.

The analogs of Pascal's identity for the Gaussian binomial coefficients are:Mukhin, Eugene, chapter 3

:$\{m\; \backslash choose\; r\}\_q\; =\; q^r\; \{m-1\; \backslash choose\; r\}\_q\; +\; \{m-1\; \backslash choose\; r-1\}\_q$

and

:$\{m\; \backslash choose\; r\}\_q\; =\; \{m-1\; \backslash choose\; r\}\_q\; +\; q^\{m-r\}\{m-1\; \backslash choose\; r-1\}\_q.$

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

:$\{m\; \backslash choose\; m\}\_q\; =\{m\; \backslash 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\; \backslash rightarrow\; m-r$ and the invariance of the Gaussian binomial coefficients under the reflection $r\; \backslash rightarrow\; m-r$.

These identities have natural interpretations in terms of linear algebra. Recall that $\backslash tbinom\{m\}\{r\}\_q$ counts r-dimensional subspaces $V\backslash subset\; \backslash mathbb\{F\}\_q^m$, and let $\backslash pi:\backslash mathbb\{F\}\_q^m\; \backslash to\; \backslash mathbb\{F\}\_q^\{m-1\}$ be a projection with one-dimensional nullspace $E\_1$. The first identity comes from the bijection which takes $V\backslash subset\; \backslash mathbb\{F\}\_q^m$ to the subspace $V\text{'}\; =\; \backslash pi(V)\backslash subset\; \backslash mathbb\{F\}\_q^\{m-1\}$; in case $E\_1\backslash not\backslash subset\; V$, the space $V\text{'}$ is r-dimensional, and we must also keep track of the linear function $\backslash phi:V\text{'}\backslash to\; E\_1$ whose graph is $V$; but in case $E\_1\backslash subset\; V$, the space $V\text{'}$ is (r−1)-dimensional, and we can reconstruct $V=\backslash pi^\{-1\}(V\text{'})$ without any extra information. The second identity has a similar interpretation, taking $V$ to $V\text{'}\; =\; V\backslash cap\; E\_\{n-1\}$ for an (m−1)-dimensional space $E\_\{m-1\}$, again splitting into two cases.

Both analogs can be proved by first noting that from the definition of $\backslash tbinom\{m\}\{r\}\_q$, we have:

{{NumBlk|:|$\backslash binom\{m\}\{r\}\_q\; =\; \backslash frac\{1-q^m\}\{1-q^\{m-r\}\}\; \backslash binom\{m-1\}\{r\}\_q$|{{EquationRef|1}}}}

{{NumBlk|:|$\backslash binom\{m\}\{r\}\_q\; =\; \backslash frac\{1-q^m\}\{1-q^r\}\; \backslash binom\{m-1\}\{r-1\}\_q$|{{EquationRef|2}}}}

{{NumBlk|:|$\backslash frac\{1-q^r\}\{1-q^\{m-r\}\}\backslash binom\{m-1\}\{r\}\_q\; =\; \backslash binom\{m-1\}\{r-1\}\_q$|{{EquationRef|3}}}}

As

:$\backslash frac\{1-q^m\}\{1-q^\{m-r\}\}=\backslash frac\{1-q^r+q^r-q^m\}\{1-q^\{m-r\}\}=q^r+\backslash frac\{1-q^r\}\{1-q^\{m-r\}\}$

Equation ({{EquationNote|1}}) becomes:

:$\backslash binom\{m\}\{r\}\_q\; =\; q^r\backslash binom\{m-1\}\{r\}\_q\; +\; \backslash frac\{1-q^r\}\{1-q^\{m-r\}\}\backslash binom\{m-1\}\{r\}\_q$

and substituting equation ({{EquationNote|3}}) gives the first analog.

A similar process, using

:$\backslash frac\{1-q^m\}\{1-q^r\}=q^\{m-r\}+\backslash frac\{1-q^\{m-r\}\}\{1-q^r\}$

instead, gives the second analog.

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

:$\backslash prod\_\{k=0\}^\{n-1\}\; (1+q^kt)=\backslash sum\_\{k=0\}^n\; 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

:$\backslash prod\_\{k=0\}^\{n-1\}\; \backslash frac\{1\}\{1-q^kt\}=\backslash sum\_\{k=0\}^\backslash infty$

{n+k-1 \choose k}_q t^k.

In the limit $n\backslash rightarrow\backslash infty$, these formulas yield

:$\backslash prod\_\{k=0\}^\{\backslash infty\}\; (1+q^kt)=\backslash sum\_\{k=0\}^\backslash infty\; \backslash frac\{q^\{k(k-1)/2\}t^k\}\{[k]\_q!\backslash ,(1-q)^k\}$

and

:$\backslash prod\_\{k=0\}^\backslash infty\; \backslash frac\{1\}\{1-q^kt\}=\backslash sum\_\{k=0\}^\backslash 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.)

With the ordinary binomial coefficients, we have:

:$\backslash sum\_\{k=0\}^n\; \backslash binom\{n\}\{k\}^2\; =\; \backslash binom\{2n\}\{n\}$

With q-binomial coefficients, the analog is:

:$\backslash sum\_\{k=0\}^n\; q^\{k^2\}\backslash binom\{n\}\{k\}\_q^2\; =\; \backslash binom\{2n\}\{n\}\_q$

Gauss originally used the Gaussian binomial coefficients in his determination of the sign of the quadratic Gauss sum.{{Cite book |last=Gauß |first=Carl Friedrich |date=1808 |title=Summatio quarumdam serierum singularium |url=https://eudml.org/doc/203313 |language=LA|location=Göttingen|publisher=Dieterich}}

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

:$\{n+m\; \backslash 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\; \backslash 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\; \backslash choose\; 1\}\_q=1+q+q^2+\backslash 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\; \backslash choose\; k\}\_q$.

This allows another interpretation of the identity

:$\{m\; \backslash choose\; r\}\_q\; =\; \{m-1\; \backslash choose\; r\}\_q\; +\; q^\{m-r\}\{m-1\; \backslash 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\; \backslash choose\; k\}\_\{q^2\}$.

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

• List of q-analogs

{{Reflist}}

• Exton, H. (1983), q-Hypergeometric Functions and Applications, New York: Halstead Press, Chichester: Ellis Horwood, 1983, {{ISBN|0853124914}}, {{ISBN|0470274530}}, {{ISBN|978-0470274538}}
• {{cite web

|first1=Eugene

|last1=Mukhin

|url=http://mathcircle.berkeley.edu/BMC3/SymPol.pdf

|title= Symmetric Polynomials and Partitions

|archive-url=https://web.archive.org/web/20160304041707/http://mathcircle.berkeley.edu/BMC3/SymPol.pdf

|archive-date=March 4, 2016

|url-status=dead

}} (undated, 2004 or earlier).

• Ratnadha Kolhatkar, [http://www.math.mcgill.ca/goren/SeminarOnCohomology/GrassmannVarieties%20.pdf Zeta function of Grassmann Varieties] (dated January 26, 2004)
• {{MathWorld| urlname=q-BinomialCoefficient|title=q-Binomial Coefficient}}
• {{cite journal

|first1=Henry

|last1=Gould

|journal=Fibonacci Quarterly

|year=1969

|title=The bracket function and Fontene-Ward generalized binomial coefficients with application to Fibonomial coefficients

|mr=0242691

|volume=7

|pages=23–40

|doi=10.1080/00150517.1969.12431177

}}

• {{cite journal

|first1= G. L.

|last1=Alexanderson|author1-link=Gerald L. Alexanderson

|journal=Fibonacci Quarterly

|year=1974

|volume=12

|title=A Fibonacci analogue of Gaussian binomial coefficients

|issue=2 |mr=0354537

|pages=129–132

|doi=10.1080/00150517.1974.12430746 }}

• {{cite journal

|first1=George E.

|last1=Andrews

|author1-link=George Andrews (mathematician)

|title=Applications of basic hypergeometric functions

|journal=SIAM Rev.

|year=1974

|volume=16

|number=4

|jstor=2028690

|mr=0352557

|doi=10.1137/1016081

|pages=441–484

}}

• {{cite journal

|first1=Peter B.

|last1=Borwein

|title=Padé approximants for the q-elementary functions

|journal=Construct. Approx.

|year=1988

|volume=4

|number=1

|pages=391–402

|doi=10.1007/BF02075469

|mr=0956175

|s2cid=124884851

}}

• {{cite journal

|first1=John

|last1=Konvalina

|title=Generalized binomial coefficients and the subset-subspace problem

|journal=Adv. Appl. Math.

|year=1998

|doi=10.1006/aama.1998.0598

|volume=21

|issue=2

|pages=228–240

|mr=1634713

|doi-access=free

}}

• {{cite journal

|first1=A.

|last1=Di Bucchianico

|title=Combinatorics, computer algebra and the Wilcoxon-Mann-Whitney test

|journal=J. Stat. Plann. Inf.

|year=1999

|doi=10.1016/S0378-3758(98)00261-4

|volume=79

|issue=2

|pages=349–364

|citeseerx=10.1.1.11.7713

}}

• {{ cite journal

|first1=John

|last1=Konvalina

|title=A unified interpretation of the Binomial Coefficients, the Stirling numbers, and the Gaussian coefficients

|journal=Amer. Math. Monthly

|jstor=2695583

|year=2000

|pages=901–910

|volume=107

|number=10

|mr=1806919

|doi=10.2307/2695583

}}

• {{cite journal

|first1=Boris A.

|last1=Kupershmidt

|title=q-Newton binomial: from Euler to Gauss

|journal=J. Nonlinear Math. Phys.

|year=2000

|volume=7

|number=2

|pages=244–262

|mr=1763640

|bibcode=2000JNMP....7..244K

|arxiv = math/0004187 |doi = 10.2991/jnmp.2000.7.2.11 |s2cid=125273424

}}

• {{ cite journal

|first1=Henry

|last1=Cohn

|journal=Amer. Math. Monthly

|year=2004

|title=Projective geometry over F₁ and the Gaussian Binomial Coefficients

|volume=111

|number=6

|jstor=4145067

|mr=2076581

|pages=487–495

|url=http://www.maa.org/programs/maa-awards/writing-awards/projective-geometry-over-f1-and-the-gaussian-binomial-coefficients

|doi=10.2307/4145067

}}

• {{cite journal

|first1=T.

|last1=Kim

|title=q-Extension of the Euler formula and trigonometric functions

|journal=Russ. J. Math. Phys.

|volume=14

|number=3

|pages=–275–278

|year=2007

|doi=10.1134/S1061920807030041

|mr=2341775

|bibcode = 2007RJMP...14..275K |s2cid=122865930

}}

• {{cite journal

|first1=T.

|last1=Kim

|title=q-Bernoulli numbers and polynomials associated with Gaussian binomial coefficients

|journal = Russ. J. Math. Phys.

|volume=15

|number=1

|pages=51–57

|doi=10.1134/S1061920808010068

|mr=2390694

|year=2008|bibcode = 2008RJMP...15...51K |s2cid=122966597

}}

• {{cite journal

|first1=Roberto B.

|last1=Corcino

|title= On p,q-binomial coefficients

|journal=Integers

|volume=8

|year=2008

|pages=#A29

|mr=2425627

}}

• {{cite web

|first1=Gevorg

|last1=Hmayakyan

|url=http://ghmath.files.wordpress.com/2010/06/mobius.pdf

|title= Recursive Formula Related To The Mobius Function

}} (2009).

Category:Q-analogs

Category:Factorial and binomial topics