Editing Gaussian binomial coefficient (section)

==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).