Content deleted Content added
m →top: another typo in latest edit |
Owen Reich (talk | contribs) Link suggestions feature: 3 links added. |
||
| (137 intermediate revisions by 41 users not shown) | |||
Line 1:
{{Short description|Family of polynomials}}
{{Use American English|date = March 2019}}
{{more footnotes needed|date=March 2019}}
In [[mathematics]], the '''Gaussian binomial coefficients''' (also called '''Gaussian coefficients''', '''Gaussian polynomials''', or '''''q''-binomial coefficients''') are [[q-analog|''q''-analog]]s of the [[binomial coefficients]]. The Gaussian binomial coefficient, written as <math> \binom nk_q</math> or <math>\begin{bmatrix}n\\ k\end{bmatrix}_q</math>, 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 <math>\mathbb{F}_q</math>, a [[finite field]] with ''q'' elements; i.e. it is the number of points in the finite [[Grassmannian]] <math>\mathrm{Gr}(k, \mathbb{F}_q^n)</math>.
==Definition==
The Gaussian binomial coefficients are defined by:<ref>Mukhin, Eugene, chapter 3</ref>
:<math>{m \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 product]]s.
Although the formula at first appears to be a [[rational function]], it actually is a polynomial, because the division is exact in '''Z'''<nowiki>[</nowiki>''q''<nowiki>]</nowiki>
All of the factors in numerator and denominator are divisible by {{math|1 − ''q''}}, and the quotient is the [[Q-analog#Introductory examples|''q''-number]]:
:<math>[k]_q=\sum_{0\leq i<k}q^i=1+q+q^2+\cdots+q^{k-1}=
\begin{cases}
\frac{1-q^k}{1-q} & \text{for} & q \neq 1 \\
k & \text{for} & q = 1
\end{cases},</math>
Dividing out these factors gives the equivalent formula
:<math>{m \choose r}_q=\frac{[m]_q[m-1]_q\cdots[m-r+1]_q}{[1]_q[2]_q\cdots[r]_q}\quad(r\leq m).</math>
In terms of the [[Q-analog#Introductory examples|''q'' factorial]] <math>[n]_q!=[1]_q[2]_q\cdots[n]_q</math>, the formula can be stated as
:<math>{m \choose r}_q=\frac{[m]_q!}{[r]_q!\,[m-r]_q!}\quad(r\leq m).</math>
Substituting {{math|''q'' {{=}} 1}} into <math>\tbinom mr_q</math> gives the ordinary binomial coefficient <math>\tbinom mr</math>.
The Gaussian binomial coefficient has finite values as <math>m\rightarrow \infty</math>:
:<math>{\infty \choose r}_q = \lim_{m\rightarrow \infty} {m \choose r}_q = \frac{1} {(1-q)(1-q^2)\cdots(1-q^r)} = \frac{1}{[r]_q!\,(1-q)^r}</math>
==Examples==
Line 37 ⟶ 50:
:<math>{4 \choose 2}_q = \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</math>
:<math>{6 \choose 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</math>
==Combinatorial descriptions==
===Inversions===
One combinatorial description of Gaussian binomial coefficients involves [[Inversion (discrete mathematics)|inversions]].
The ordinary binomial coefficient <math>\tbinom mr</math> counts the {{math|''r''}}-[[combination]]s 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 <math>{4 \choose 2} = 6</math> words using ''0''s and ''1''s are <math>0011, 0101, 0110, 1001, 1010, 1100</math>.
To obtain the Gaussian binomial coefficient <math>\tbinom mr_q</math>, each word is associated with a factor {{math|''q''<sup>''d''</sup>}}, 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, <math>0011</math>, one word with 1 inversion, <math>0101</math>, two words with 2 inversions, <math>0110</math>, <math>1001</math>, one word with 3 inversions, <math>1010</math>, and one word with 4 inversions, <math>1100</math>. This is also the number of left-shifts of the ''1''s from the initial position.
These correspond to the coefficients in <math>{4 \choose 2}_q = 1+q+2q^2+q^3+q^4</math>.
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.
===Balls into bins===
Let <math>B(n,m,r)</math> be the number of ways of throwing <math>r</math> indistinguishable balls into <math>m</math> indistinguishable bins, where each bin can contain up to <math>n</math> balls.
The Gaussian binomial coefficient can be used to characterize <math>B(n,m,r)</math>.
Indeed,
:<math>B(n,m,r)= [q^r] {n+m \choose m}_q. </math>
where <math>[q^r]P</math> denotes the coefficient of <math>q^r</math> in polynomial <math>P</math> (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 <math> r \mapsto m-r </math>:
:<math>{m \choose r}_q = {m \choose m-r}_q. </math>
Line 49 ⟶ 95:
:<math>{m \choose 1}_q ={m \choose m-1}_q=\frac{1-q^m}{1-q}=1+q+ \cdots + q^{m-1} \quad m \ge 1 \, .</math>
===Limit at q = 1===
The evaluation of a Gaussian binomial coefficient at {{nowrap|''q'' {{=}} 1}} is
:<math>\lim_{q \to 1} \binom{m}{r}_q = \binom{m}{r}</math>
===Degree of polynomial===
The degree of <math>\binom{m}{r}_q</math> is <math>\binom{m+1}{2}-\binom{r+1}{2}-\binom{(m-r)+1}{2} = r(m-r)</math>.
==''q''-identities==
===Analogs of Pascal's identity===
The analogs of [[Pascal's identity]] for the Gaussian binomial coefficients are:<ref>Mukhin, Eugene, chapter 3</ref>
:<math>{m \choose r}_q = q^r {m-1 \choose r}_q + {m-1 \choose r-1}_q</math>
Line 63 ⟶ 119:
:<math>{m \choose r}_q = {m-1 \choose r}_q + q^{m-r}{m-1 \choose r-1}_q.</math>
When <math>q=1</math>, these both give the usual binomial identity. We can see that as <math>m\to\infty</math>, both equations remain valid.
The first Pascal analog allows computation of the Gaussian binomial coefficients recursively (with respect to ''m'' ) using the initial values
:<math>{m \choose m}_q ={m \choose 0}_q=1 </math>
and also shows that the Gaussian binomial coefficients are indeed polynomials (in ''q'').
The second Pascal analog follows from the first using the substitution <math> r \rightarrow m-r </math> and the invariance of the Gaussian binomial coefficients under the reflection <math> r \rightarrow m-r </math>.
These identities have natural interpretations in terms of linear algebra. Recall that <math>\tbinom{m}{r}_q</math> counts ''r''-dimensional subspaces <math>V\subset \mathbb{F}_q^m</math>, and let <math>\pi:\mathbb{F}_q^m \to \mathbb{F}_q^{m-1} </math> be a projection with one-dimensional nullspace <math>E_1 </math>. The first identity comes from the bijection which takes <math>V\subset \mathbb{F}_q^m </math> to the subspace <math>V' = \pi(V)\subset \mathbb{F}_q^{m-1}</math>; in case <math>E_1\not\subset V</math>, the space <math>V'</math> is ''r''-dimensional, and we must also keep track of the linear function <math>\phi:V'\to E_1</math> whose graph is <math>V</math>; but in case <math>E_1\subset V</math>, the space <math>V'</math> is (''r''−1)-dimensional, and we can reconstruct <math>V=\pi^{-1}(V')</math> without any extra information. The second identity has a similar interpretation, taking <math>V</math> to <math>V' = V\cap E_{n-1}</math> for an (''m''−1)-dimensional space <math>E_{m-1}</math>, again splitting into two cases.
===Proofs of the analogs===
Both analogs can be proved by first noting that from the definition of <math>\tbinom{m}{r}_q</math>, we have:
{{NumBlk|:|<math>\binom{m}{r}_q = \frac{1-q^m}{1-q^{m-r}} \binom{m-1}{r}_q</math>|{{EquationRef|1}}}}
{{NumBlk|:|<math>\binom{m}{r}_q = \frac{1-q^m}{1-q^r} \binom{m-1}{r-1}_q</math>|{{EquationRef|2}}}}
{{NumBlk|:|<math>\frac{1-q^r}{1-q^{m-r}}\binom{m-1}{r}_q = \binom{m-1}{r-1}_q</math>|{{EquationRef|3}}}}
As
:<math>\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}}</math>
Equation ({{EquationNote|1}}) becomes:
:<math>\binom{m}{r}_q = q^r\binom{m-1}{r}_q + \frac{1-q^r}{1-q^{m-r}}\binom{m-1}{r}_q</math>
and substituting equation ({{EquationNote|3}}) gives the first analog.
A similar process, using
:<math>\frac{1-q^m}{1-q^r}=q^{m-r}+\frac{1-q^{m-r}}{1-q^r}</math>
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:
:<math>\prod_{k=0}^{n-1} (1+q^kt)=\sum_{k=0}^n q^{k(k-1)/2}
{n \choose k}_q t^k .</math>
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
:<math>\prod_{k=0}^{n-1} \frac{1}{
{n+k-1 \choose k}_q t^k. </math>
:<math>\prod_{k=0}^{\infty} (1+q^kt)=\sum_{k=0}^\infty \frac{q^{k(k-1)/2}t^k}{[k]_q!\,(1-q)^k}
and
:<math>\prod_{k=0}^\infty \frac{1}{
\frac{t^k}{[k]_q!\,(1-q)^k}
Setting <math>t=q</math> 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:
:<math>\sum_{
With ''q''-binomial coefficients, the analog is:
:<math>\sum_{k=0}^n q^{k^2}\binom{n}{k}_q^2 = \binom{2n}{n}_q</math>
==Applications==
===Gauss sums===
Gauss originally used the Gaussian binomial coefficients in his determination of the sign of the [[quadratic Gauss sum]].<ref>{{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}}</ref>
===Symmetric polynomials and partitions===
Gaussian binomial coefficients occur in the counting of [[symmetric polynomial]]s and in the theory of [[partition (number theory)|partitions]]. The coefficient of ''q''<sup>''r''</sup> in
Line 100 ⟶ 202:
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 space]]s defined over a finite field. In particular, for every [[finite field]] ''F''<sub>''q''</sub> with ''q'' elements, the Gaussian binomial coefficient
:<math>{n \choose k}_q</math>
counts the number
:<math>{n \choose 1}_q=1+q+q^2+\cdots+q^{n-1}</math>
is the number of one-dimensional subspaces in (''F''<sub>''q''</sub>)<sup>''n''</sup> (equivalently, the number of points in the
The number of ''k''-dimensional affine subspaces of ''F''<sub>''q''</sub><sup>''n''</sup> is equal to
:<math>q^{n-k} {n \choose k}_q</math>.
This allows another interpretation of the identity
:<math>{m \choose r}_q = {m-1 \choose r}_q + q^{m-r}{m-1 \choose r-1}_q</math>
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===
{{Main|Cyclic sieving}}
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''<sup>''d''</sup> on ''X'' is equal to
:<math>
\binom nk_q
</math>
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
:<math>q^{k^2 - n k}{n \choose k}_{q^2}</math>.
This version of the quantum binomial coefficient is symmetric under exchange of <math>q</math> and <math>q^{-1}</math>.
==
* [[List of q-analogs]]
== References ==
{{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
Line 136 ⟶ 248:
|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)
Line 148 ⟶ 263:
|volume=7
|pages=23–40
|doi=10.1080/00150517.1969.12431177
}}
* {{cite journal
Line 156 ⟶ 272:
|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.
Line 171 ⟶ 287:
|mr=0352557
|doi=10.1137/1016081
|pages=441–484
}}
* {{cite journal
Line 183 ⟶ 300:
|doi=10.1007/BF02075469
|mr=0956175
|s2cid=124884851
}}
* {{cite journal
Line 192 ⟶ 310:
|doi=10.1006/aama.1998.0598
|volume=21
|issue=2
|pages=228–240
|mr=1634713
|doi-access=free
}}
* {{cite journal
Line 203 ⟶ 323:
|doi=10.1016/S0378-3758(98)00261-4
|volume=79
|issue=2
|pages=349–364
|citeseerx=10.1.1.11.7713
}}
* {{ cite journal
Line 209 ⟶ 331:
|last1=Konvalina
|title=A unified interpretation of the Binomial Coefficients, the Stirling numbers, and the Gaussian coefficients
|journal=
|jstor=2695583
|year=2000
Line 216 ⟶ 338:
|number=10
|mr=1806919
|doi=10.2307/2695583
}}
* {{cite journal
|first1=Boris A.
|
|title=q-Newton binomial: from Euler to Gauss
|journal=J.
|year=2000
|volume=7
Line 228 ⟶ 351:
|mr=1763640
|bibcode=2000JNMP....7..244K
|arxiv = math/0004187 |doi = 10.2991/jnmp.2000.7.2.11
}}
* {{ cite journal
|first1=Henry
|last1=Cohn
|journal=
|year=2004
|title=Projective geometry over '''F'''<sub>1</sub> and the Gaussian Binomial Coefficients
Line 241 ⟶ 365:
|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
Line 249 ⟶ 374:
|volume=14
|number=3
|pages=
|year=2007
|doi=10.1134/S1061920807030041
|mr=2341775
|bibcode = 2007RJMP...14..275K |s2cid=122865930
}} * {{cite journal
|first1=T.
Line 264 ⟶ 390:
|doi=10.1134/S1061920808010068
|mr=2390694
|year=2008|bibcode = 2008RJMP...15...51K
}}
* {{cite journal
|first1=Roberto B.
| |||