Definition
The Gaussian binomial coefficients are defined by
where m and r are non-negative integers. For r = 0 the value is 1 since numerator and denominator are both empty products. 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. Note that the formula can be applied for r = m + 1, and gives 0 due to a factor 1 − q0 = 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 1 − q, with as quotient a q number:
dividing out these factors gives the equivalent formula
which makes evident the fact that substituting q = 1 into gives the ordinary binomial coefficient In terms of the q factorial, the formula can be stated as
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 for r ≤ m.
Instead of these algebraic expressions, one can also give a combinatorial definition of Gaussian binomial coefficients. 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 n 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). To obtain from this model the Gaussian binomial coefficient, it suffices to count each word with a factor qd, where 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 r and 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.
Unlike the ordinary binomial coefficient, the Gaussian binomial coefficient has finite values for :
Read more about this topic: Gaussian Binomial Coefficient
Famous quotes containing the word definition:
“According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
—Ana Castillo (b. 1953)
“It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
—François, Duc De La Rochefoucauld (1613–1680)
“Perhaps the best definition of progress would be the continuing efforts of men and women to narrow the gap between the convenience of the powers that be and the unwritten charter.”
—Nadine Gordimer (b. 1923)