|
|
| (359 intermediate revisions by more than 100 users not shown) |
| Line 1: |
Line 1: |
| 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]].
| | This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users. |
|
| |
|
| ==Definition==
| | If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]] |
| | * Only registered users will be able to execute this rendering mode. |
| | * Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere. |
|
| |
|
| The Gaussian binomial coefficients are defined by
| | Registered users will be able to choose between the following three rendering modes: |
|
| |
|
| :<math>{m \choose r}_q | | '''MathML''' |
| = \begin{cases} | | :<math forcemathmode="mathml">E=mc^2</math> |
| \frac{(1-q^m)(1-q^{m-1})\cdots(1-q^{m-r+1})} {(1-q)(1-q^2)\cdots(1-q^r)} & r \le m \\
| |
| 0 & r>m \end{cases}</math>
| |
|
| |
|
| where ''m'' and ''r'' are non-negative integers. For {{nowrap|''r'' {{=}} 0}} the value is 1 since numerator and denominator are both [[empty product]]s. Although the formula in the first clause appears to involve a [[rational function]], it actually designates a polynomial, because the division is exact in '''Z'''<nowiki>[</nowiki>''q''<nowiki>]</nowiki>. Note that the formula can be applied for {{nowrap|''r'' {{=}} ''m'' + 1}}, and gives 0 due to a factor {{nowrap|1 − ''q''<sup>0</sup> {{=}} 0}} in the numerator, in accordance with the second clause (for even larger ''r'' the factor 0 remains present in the numerator, but its further factors would involve negative powers of ''q'', whence explicitly stating the second clause is preferable). All of the factors in numerator and denominator are divisible by {{nowrap|1 − ''q''}}, with as quotient a [[Q-analog#Introductory examples|''q'' number]]:
| | <!--'''PNG''' (currently default in production) |
| :<math>[k]_q=\frac{1-q^k}{1-q}=\sum_{0\leq i<k}q^i=1+q+q^2+\cdots+q^{k-1};</math> | | :<math forcemathmode="png">E=mc^2</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>
| |
| which makes evident the fact that substituting {{nowrap|''q'' {{=}} 1}} into <math>\tbinom mr_q</math> gives the ordinary binomial coefficient <math>\tbinom mr.</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>
| |
| a compact form (often given as only definition), which however hides the presence of many common factors in numerator and denominator. This form does make obvious the symmetry <math>\tbinom mr_q=\tbinom m{m-r}_q</math> for {{nowrap|''r'' ≤ ''m''}}.
| |
|
| |
|
| Instead of these algebraic expressions, one can also give a combinatorial definition of Gaussian binomial coefficients. 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). To obtain from this model the Gaussian binomial coefficient <math>\tbinom mr_q</math>, it suffices to count each word with a factor {{math|''q''<sup>''d''</sup>}}, where {{math|''d''}} is the number of "inversions" of the word: the number of pairs of positions for which the leftmost position of the pair holds a letter 1 and the rightmost position holds a letter 0 in the word. It can be shown that the polynomials so defined satisfy the Pascal identities given below, and therefore coincide with the polynomials given by the algebraic definitions. A visual way to view this definition is to associate to each word a path across a rectangular grid with sides of length {{math|''r''}} and {{math|''m'' − ''r''}}, from the bottom left corner to the top right corner, taking a step left for each letter 0 and a step up for each letter 1. Then the number of inversions of the word equals the area of the part of the rectangle that is to the bottom-right of the path.
| | '''source''' |
| | :<math forcemathmode="source">E=mc^2</math> --> |
|
| |
|
| Unlike the ordinary binomial coefficient, the Gaussian binomial coefficient has finite values for <math>m\rightarrow \infty</math>:
| | <span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples]. |
|
| |
|
| :<math>{\infty \choose r}_q = \lim_{m\rightarrow \infty} {m \choose r}_q = \frac{1}{[r]_q!\,(1-q)^r}</math>
| | ==Demos== |
|
| |
|
| ==Examples== | | Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]: |
|
| |
|
| :<math>{0 \choose 0}_q = {1 \choose 0}_q = 1</math>
| |
|
| |
|
| :<math>{1 \choose 1}_q = \frac{1-q}{1-q}=1</math> | | * accessibility: |
| | ** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)] |
| | ** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]]. |
| | ** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]]. |
| | ** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode. |
|
| |
|
| :<math>{2 \choose 1}_q = \frac{1-q^2}{1-q}=1+q</math>
| | ==Test pages == |
|
| |
|
| :<math>{3 \choose 1}_q = \frac{1-q^3}{1-q}=1+q+q^2</math> | | To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages: |
| | *[[Displaystyle]] |
| | *[[MathAxisAlignment]] |
| | *[[Styling]] |
| | *[[Linebreaking]] |
| | *[[Unique Ids]] |
| | *[[Help:Formula]] |
|
| |
|
| :<math>{3 \choose 2}_q = \frac{(1-q^3)(1-q^2)}{(1-q)(1-q^2)}=1+q+q^2</math>
| | *[[Inputtypes|Inputtypes (private Wikis only)]] |
| | | *[[Url2Image|Url2Image (private Wikis only)]] |
| :<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>
| | ==Bug reporting== |
| | | If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de . |
| ==Properties==
| |
| Like the ordinary binomial coefficients, the Gaussian binomial coefficients are center-symmetric, i.e., invariant under the reflection <math> r \rightarrow m-r </math>:
| |
| | |
| :<math>{m \choose r}_q = {m \choose m-r}_q. </math>
| |
| | |
| In particular,
| |
| | |
| :<math>{m \choose 0}_q ={m \choose m}_q=1 \, ,</math>
| |
| | |
| :<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>
| |
| | |
| The name ''Gaussian binomial coefficient'' stems from the fact{{cn|date=February 2014}} that their evaluation at {{nowrap|''q'' {{=}} 1}} is
| |
| | |
| :<math>{m \choose r}_1 = {m \choose r}</math>
| |
| | |
| for all ''m'' and ''r''.
| |
| | |
| The analogs of [[Pascal's triangle|Pascal identities]] for the Gaussian binomial coefficients are
| |
| | |
| :<math>{m \choose r}_q = q^r {m-1 \choose r}_q + {m-1 \choose r-1}_q</math>
| |
| | |
| and
| |
| | |
| :<math>{m \choose r}_q = {m-1 \choose r}_q + q^{m-r}{m-1 \choose r-1}_q.</math>
| |
| | |
| There are analogs of the binomial formula, and of Newton's generalized version of it for negative integer exponents, although for the former the Gaussian binomial coefficients themselves do not appear as coefficients:
| |
| | |
| :<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>
| |
| | |
| and
| |
| | |
| :<math>\prod_{k=0}^{n-1} \frac{1}{(1-q^kt)}=\sum_{k=0}^\infty
| |
| {n+k-1 \choose k}_q t^k. </math>
| |
| | |
| which, for <math>n\rightarrow\infty</math> become:
| |
| | |
| :<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} </math>
| |
| | |
| and
| |
| | |
| :<math>\prod_{k=0}^\infty \frac{1}{(1-q^kt)}=\sum_{k=0}^\infty
| |
| \frac{t^k}{[k]_q!\,(1-q)^k} . </math>
| |
| | |
| The first Pascal identity allows one to compute the Gaussian binomial coefficients recursively (with respect to ''m'' ) using the initial "boundary" values
| |
| | |
| :<math>{m \choose m}_q ={m \choose 0}_q=1 </math>
| |
| | |
| and also incidentally shows that the Gaussian binomial coefficients are indeed polynomials (in ''q''). The second Pascal identity 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>. Both Pascal identities together imply
| |
| | |
| :<math>{m \choose r}_q = {{1-q^{m}}\over {1-q^{m-r}}} {m-1 \choose r}_q </math>
| |
| | |
| which leads (when applied iteratively for ''m'', ''m'' − 1, ''m'' − 2,....) to an expression for the Gaussian binomial coefficient as given in the definition above.
| |
| | |
| ==Applications==
| |
| | |
| 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
| |
| | |
| :<math>{n+m \choose m}_q</math>
| |
| | |
| 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 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 ''v''<sub>''n'',''k'';''q''</sub> of different ''k''-dimensional vector subspaces of an ''n''-dimensional [[vector space]] over ''F''<sub>''q''</sub> (a [[Grassmannian]]). When expanded as a polynomial in ''q'', it yields the well-known decomposition of the Grassmannian into Schubert cells. Furthermore, when ''q'' is 1 (respectively -1), the Gaussian binomial coefficient yields the Euler characteristic of the corresponding complex (respectively real) Grassmannian. For example, the Gaussian binomial coefficient
| |
| | |
| :<math>{n \choose 1}_q=1+q+q^2+\cdots+q^{n-1}</math>
| |
| | |
| is the number of different lines in ''F''<sub>''q''</sub><sup>''n''</sup> (a [[projective space]]).
| |
| | |
| 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>.
| |
| | |
| ==Triangles== | |
| | |
| The Gaussian binomial coefficients can be arranged in a triangle for each ''q'', which is [[Pascal's triangle]] for ''q''=1.<br>
| |
| Read line by line these triangles form the following sequences in the [[On-Line Encyclopedia of Integer Sequences|OEIS]]:
| |
| * [[oeis:A022166/table|A022166]] for ''q''= 2
| |
| * [[oeis:A022167/table|A022167]] for ''q''= 3
| |
| * [[oeis:A022168/table|A022168]] for ''q''= 4
| |
| * [[oeis:A022169/table|A022169]] for ''q''= 5
| |
| * [[oeis:A022170/table|A022170]] for ''q''= 6
| |
| * [[oeis:A022171/table|A022171]] for ''q''= 7
| |
| * [[oeis:A022172/table|A022172]] for ''q''= 8
| |
| * [[oeis:A022173/table|A022173]] for ''q''= 9
| |
| * [[oeis:A022174/table|A022174]] for ''q''= 10
| |
| | |
| ==References==
| |
| *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
| |
| }} (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
| |
| }}
| |
| * {{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
| |
| |mr=0354537
| |
| |pages=129–132
| |
| }}
| |
| * {{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
| |
| }}
| |
| * {{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
| |
| }}
| |
| * {{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
| |
| |pages=228–240
| |
| |mr=1634713
| |
| }}
| |
| * {{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
| |
| |pages=349–364
| |
| }}
| |
| * {{ cite journal
| |
| |first1=John
| |
| |last1=Konvalina
| |
| |title=A unified interpretation of the Binomial Coefficients, the Stirling numbers, and the Gaussian coefficients
| |
| |journal=Am. Math. Monthly
| |
| |jstor=2695583
| |
| |year=2000
| |
| |pages=901–910
| |
| |volume=107
| |
| |number=10
| |
| |mr=1806919
| |
| }}
| |
| * {{cite journal
| |
| |first1=Boris A.
| |
| |last=Kupershmidt
| |
| |title=q-Newton binomial: from Euler to Gauss
| |
| |journal=J. Nonlin. 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 }}
| |
| * {{ cite journal
| |
| |first1=Henry
| |
| |last1=Cohn
| |
| |journal=Am. Math. Monthly
| |
| |year=2004
| |
| |title=Projective geometry over F1 and the Gaussian Binomial Coefficients
| |
| |volume=111
| |
| |number=6
| |
| |jstor=4145067
| |
| |mr=2076581
| |
| |pages=487–495
| |
| }}
| |
| * {{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 }}
| |
| * {{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}}
| |
| * {{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]]
| |
