Введение
Семья полиномов
В математике биномиальные коэффициенты Гаусса (также называемые гауссовыми коэффициентами, гауссовыми полиномами или q-биномиальными коэффициентами) являются q-аналогами биномиальных коэффициентов. Биномиальный коэффициент Гаусса, записываемый как или , является многочленом от q с целыми коэффициентами, значение которого при q, равном степени простого числа, подсчитывает количество подпространств размерности k в векторном пространстве размерности n над , конечным полем с q элементами; то есть это число точек в конечном грассманиане .
Инверсии
Одно из комбинаторных описаний гауссовых биномиальных коэффициентов связано с инверсиями. Обычный биномиальный коэффициент подсчитывает количество комбинаций из r элементов, выбранных из множества, содержащего m элементов. Если рассматривать эти m элементов как различные позиции символов в слове длины m, то каждая комбинация из r элементов соответствует слову длины m, использующему алфавит из двух букв, например, {0,1}, с r копиями буквы 1 (указывающими позиции в выбранной комбинации) и m − r буквами 0 (для оставшихся позиций). Например, слова, составленные из 0 и 1, таковы:
Для получения гауссового биномиального коэффициента каждое слово ассоциируется с фактором q^(d), где d — это количество инверсий в слове. В данном случае инверсией называется пара позиций, в которой левая позиция содержит букву 1, а правая — букву 0. В приведенном выше примере есть одно слово с 0 инверсиями, , одно слово с 1 инверсией, , два слова с 2 инверсиями, , одно слово с 3 инверсиями, и одно слово с 4 инверсиями. Это также соответствует количеству сдвигов единиц влево от их начальной позиции. Другой способ понять это — связать каждое слово с путем на прямоугольной сетке высотой r и шириной m − r, идущим из нижнего левого угла в верхний правый угол. Путь делает шаг вправо для каждой 0 и шаг вверх для каждой 1. Инверсия меняет направления шага (вправо и вверх становится вверх и вправо, и наоборот), следовательно, количество инверсий равно площади под траекторией пути.
To obtain the Gaussian binomial coefficient , each word is associated with a factor q^(d), 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. With the example above, there is one word with 0 inversions, , one word with 1 inversion, , two words with 2 inversions, , , one word with 3 inversions, , and one word with 4 inversions, This is also the number of left shifts of the 1s from the initial position. These correspond to the coefficients in
Another way to see this is to associate each word with a path across a rectangular grid with height r and width 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.
Степень многочлена
Степень — это .