Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Gaussian binomial coefficient
Summary
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 or , 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 , a finite field with q elements; i.e. it is the number of points in the finite Grassmannian .
The Gaussian binomial coefficients are defined by:
where m and r are non-negative integers. If r > m, this evaluates to 0. For 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 1 − q, and the quotient is the q-number:
Dividing out these factors gives the equivalent formula
In terms of the q factorial , the formula can be stated as
Substituting q = 1 into gives the ordinary binomial coefficient .
The Gaussian binomial coefficient has finite values as :
One combinatorial description of Gaussian binomial coefficients involves inversions.
The ordinary binomial coefficient counts the r-combinations chosen from an m-element set. If one takes those m elements to be the different character positions in a word of length m, then each r-combination corresponds to a word of length m using an alphabet of two letters, say {0,1}, with r copies of the letter 1 (indicating the positions in the chosen combination) and m − r letters 0 (for the remaining positions).
So, for example, the words using 0s and 1s are .
To obtain the Gaussian binomial coefficient , each word is associated with a factor qd, where 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.