Гауссовы биномиальные коэффициенты

Гауссовы биномиальные коэффициенты (а также гауссовы коэффициенты, гауссовы многочлены или q-биномиальные коэффициенты) — это q-аналоги биномиальных коэффициентов. Гауссов биномиальный коэффициент ${(\binom{n}{k})}_{q}$ — это многочлен от q с целыми коэффициентами, значение которого, если положить q равным степени простого числа, подсчитывает число подпространств размерности k в векторном пространстве размерности n над конечным полем с q элементами.

Определение

Гауссовы биномиальные коэффициенты определяются следующим образомШаблон:Sfn

{(\binom{m}{r})}_{q} = {\begin{matrix} \frac{(1 - q^{m}) (1 - q^{m - 1}) \dots (1 - q^{m - r + 1})}{(1 - q) (1 - q^{2}) \dots (1 - q^{r})} & r ⩽ m \\ 0 & r > m \end{matrix}

,

где m и r — неотрицательные целые числа.

В статье СмирноваШаблон:Sfn и книге Васильева вместо круглых скобок использованы квадратные:

{[\begin{matrix} m \\ r \end{matrix}]}_{q}

Для $r = 0$ значение равно 1, поскольку числитель и знаменатель являются Шаблон:Не переведено 5. Хотя формула в первом выражении представляет собой рациональную функцию, на самом деле она задаёт многочлен. Заметим, что формулу можно применить для $r = m + 1$ , что даёт 0 вследствие множителя $1 - q^{0} = 0$ в числителе согласно второму выражению (для любого бо́льшего r множитель 0 присутствует в числителе, но дальнейшие множители будут с отрицательными степенями q, вследствие чего явное второе выражение предпочтительнее). Все множители в числителе и знаменателе делятся на Шаблон:Nowrap с частным в виде q-числа Шаблон:Sfn:

[k]_{q} = \frac{1 - q^{k}}{1 - q} = \sum_{0 ⩽ i < k} q^{i} = 1 + q + q^{2} + \dots + q^{k - 1};

Это даёт эквивалентную формулу

{(\binom{m}{r})}_{q} = \frac{[m]_{q} [m - 1]_{q} \dots [m - r + 1]_{q}}{[1]_{q} [2]_{q} \dots [r]_{q}} (r ⩽ m),

которая делает очевидным факт, что подстановка $q = 1$ в ${(\binom{m}{r})}_{q}$ даёт обыкновенный биномиальный коэффициент $(\binom{m}{r})$ . В терминах q-факториала $[n]_{q}! = [1]_{q} [2]_{q} \dots [n]_{q}$ формулу можно переписать как

{(\binom{m}{r})}_{q} = \frac{[m]_{q}!}{[r]_{q}! [m - r]_{q}!} (r ⩽ m)

Эта компактная форма (часто дающаясяся в качестве определения), однако, прячет существование многих общих множителей в числителе и знаменателе. Этот вид делает очевидной симметрию ${(\binom{m}{r})}_{q} = {(\binom{m}{m - r})}_{q}$ для $r ⩽ m$ .

В отличие от обычного биномиального коэффициента, гауссов биномиальный коэффициент имеет конечные значения для $m \to \infty$ (предел имеет аналитический смысл для $| q | < 1$ ):

{(\binom{\infty}{r})}_{q} = \lim_{m \to \infty} {(\binom{m}{r})}_{q} = \frac{1}{[r]_{q}! (1 - q)^{r}}

Примеры

{(\binom{0}{0})}_{q} = {(\binom{1}{0})}_{q} = 1

{(\binom{1}{1})}_{q} = \frac{1 - q}{1 - q} = 1

{(\binom{2}{1})}_{q} = \frac{1 - q^{2}}{1 - q} = 1 + q

{(\binom{3}{1})}_{q} = \frac{1 - q^{3}}{1 - q} = 1 + q + q^{2}

{(\binom{3}{2})}_{q} = \frac{(1 - q^{3}) (1 - q^{2})}{(1 - q) (1 - q^{2})} = 1 + q + q^{2}

{(\binom{4}{2})}_{q} = \frac{(1 - q^{4}) (1 - q^{3})}{(1 - q) (1 - q^{2})} = (1 + q^{2}) (1 + q + q^{2}) = 1 + q + 2 q^{2} + q^{3} + q^{4}

Комбинаторное описание

Вместо этих алгебраических выражений, можно также дать комбинаторное определение гауссовых биномиальных коэффициентов. Обычный биномиальный коэффициент $(\binom{m}{r})$ подсчитывает Шаблон:Math-сочетания, выбранные из множества с Шаблон:Math элементами. Если распределить Шаблон:Math элементов как различные символы в слове длины Шаблон:Math, то каждое Шаблон:Math-сочетание соответствует слову длины Шаблон:Math, составленное из алфавита с двумя буквами, скажем, Шаблон:Math с Шаблон:Math копиями буквы 1 (указывающей, что буква выбрана) и с Шаблон:Math копиями буквы 0 (для оставшихся позиций).

Слова $(\binom{4}{2}) = 6$ , использующие нули и единицы, это 0011, 0101, 0110, 1001, 1010, 1100.

Чтобы получить из этой модели гауссов биномиальный коэффициент ${(\binom{m}{r})}_{q}$ , достаточно посчитать каждое слово с множителем Шаблон:Math, где Шаблон:Math равно числу «инверсий» в слове — число пар позиций, для которых левая позиция пары равна 1 а правая позиция содержит 0 в слове. Например, существует одно слово с 0 инверсиями, 0011. Есть одно слово с одной инверсией, 0101. Есть два слова с двумя инверсиями, 0110 и 1001. Существует одно слово с тремя инверсиями, 1010, и, наконец, одно слово с четырьмя инверсиями, 1100. Это соответствует коэффициентам в ${(\binom{4}{2})}_{q} = 1 + q + 2 q^{2} + q^{3} + q^{4}$ .

Можно показать, что так определённые многочлены удовлетворяют тождествам Паскаля, данным ниже, а потому совпадают с многочленами, определёнными алгебраически. Визуальный способ видеть это определение — сопоставить каждому слову путь через прямоугольную решётку с высотой Шаблон:Math и шириной Шаблон:Math с нижнего левого угла в правый верхний угол, при этом шаг вправо делается для буквы 0 и шаг вверх для буквы 1. Тогда число инверсий в слове равно площади части прямоугольника снизу под путём.

Свойства

Подобно обычным биномиальным коэффициентам гауссовы биномиальные коэффициенты контрсимметричны, т.е. инвариантны относительно отражения $r \to m - r$ :

{(\binom{m}{r})}_{q} = {(\binom{m}{m - r})}_{q} .

В частности,

{(\binom{m}{0})}_{q} = {(\binom{m}{m})}_{q} = 1,

{(\binom{m}{1})}_{q} = {(\binom{m}{m - 1})}_{q} = \frac{1 - q^{m}}{1 - q} = 1 + q + \dots + q^{m - 1} m ⩾ 1 .

Название гауссов биномиальный коэффициент объясняется фактом, что его значение в точке $q = 1$ равно

\lim_{q \to 1} {(\binom{m}{r})}_{q} = (\binom{m}{r})

Для всех m и r.

Аналоги тождеств Паскаля для гауссовых биномиальных коэффициентов

{(\binom{m}{r})}_{q} = q^{r} {(\binom{m - 1}{r})}_{q} + {(\binom{m - 1}{r - 1})}_{q}

и

{(\binom{m}{r})}_{q} = {(\binom{m - 1}{r})}_{q} + q^{m - r} {(\binom{m - 1}{r - 1})}_{q} .

Есть аналоги биномиальных формул и обобщённые ньютоновы версии их для отрицательных целых степеней, хотя в первом случае гауссовы биномиальные коэффициенты не появляются как коэффициентыШаблон:Sfn:

\prod_{k = 0}^{n - 1} (1 + q^{k} t) = \sum_{k = 0}^{n} q^{k (k - 1) / 2} {(\binom{n}{k})}_{q} t^{k}

и

\prod_{k = 0}^{n - 1} \frac{1}{(1 - q^{k} t)} = \sum_{k = 0}^{\infty} {(\binom{n + k - 1}{k})}_{q} t^{k} .

и при $n \to \infty$ тождества превращаются в

\prod_{k = 0}^{\infty} (1 + q^{k} t) = \sum_{k = 0}^{\infty} \frac{q^{k (k - 1) / 2} t^{k}}{[k]_{q}! (1 - q)^{k}}

и

\prod_{k = 0}^{\infty} \frac{1}{(1 - q^{k} t)} = \sum_{k = 0}^{\infty} \frac{t^{k}}{[k]_{q}! (1 - q)^{k}} .

Первое тождество Паскаля позволяет вычислить гауссовы биномиальные коэффициенты рекурсивно (относительно m), используя начальные «граничные» значения

{(\binom{m}{m})}_{q} = {(\binom{m}{0})}_{q} = 1

И, между прочим, показывает, что гауссовы биномиальные коэффициенты являются реально многочленами (от q). Второе тождество Паскаля следует из первого с помощью подстановки $r \to m - r$ и инвариантности гауссовых биномиальных коэффициентов по отношению к отражению $r \to m - r$ . Из тождеств Паскаля следует

{(\binom{m}{r})}_{q} = \frac{1 - q^{m}}{1 - q^{m - r}} {(\binom{m - 1}{r})}_{q}

что ведёт (при итерациях для m, m − 1, m − 2,....) к выражению для гауссовых биномиальных коэффициентов, как в определении выше.

Приложения

Гауссовы биномиальные коэффициенты появляются в подсчёте симметрических многочленов и в теории разбиений чисел. Коэффициент q^r в

{(\binom{n + m}{m})}_{q}

является числом разбиений числа r на m или менее частей, каждая из которых не больше n. Эквивалентно, это также число разбиений числа r на n или менее частей, каждая из которых не больше m.

Гауссовы биномиальные коэффициенты играют также важную роль в перечислении проективных пространств, определённых над конечным полем. В частности, для любого конечного поля F_q с q элементами, гауссов биномиальный коэффициент

{(\binom{n}{k})}_{q}

подсчитывает число k-мерных векторных подпространств n-размерного векторного пространства над F_q (грассманиан). Если разложить в виде многочлена от q, это даёт хорошо известное разложение грассманиана на ячейки Шуберта. Например, гауссов биномиальный коэффициент

{(\binom{n}{1})}_{q} = 1 + q + q^{2} + \dots + q^{n - 1}

является числом одномерных подпространств в (F_q)ⁿ (эквивалентно, число точек в ассоциированном проективном пространстве). Более того, если q равно 1 (соответственно, −1), гауссов биномиальный коэффициент даёт эйлерову характеристику соответствующего комплексного (соответственно, вещественного) грассманиана.

Число k-мерных аффинных подпространств F_qⁿ равно

q^{n - k} {(\binom{n}{k})}_{q}

.

Это позволяет другую интерпретацию тождества

{(\binom{m}{r})}_{q} = {(\binom{m - 1}{r})}_{q} + q^{m - r} {(\binom{m - 1}{r - 1})}_{q}

как подсчёт (r − 1)-мерных подпространств (m − 1)-мерного проективного пространства для фиксированной гиперплоскости и в этом случае подсчитывается количество подпространств, содержащихся в этой фиксированной гиперплоскости. Эти подпространства находятся в биективном соответствии с (r − 1)-мерными аффинными подпространствами пространства, полученного истолкованием этой фиксированной гиперплоскости как гиперплоскости на бесконечности.

В теории квантовых групп приняты слегка отличные соглашения в определении. Квантовые биномиальные коэффициенты равны

q^{k^{2} - n k} {(\binom{n}{k})}_{q^{2}}

.

Эта версия квантового биномиального коэффициента симметрична относительно $q$ и $q^{- 1}$ .

Треугольники

Гауссовы биномиальные коэффициенты можно расположить в виде треугольника для каждого q и этот треугольник для q=1 совпадает с треугольником Паскаля Шаблон:Sfn.

Если размещать строки этих треугольников в одну линию, получим следующие последовательности OEIS:

A022166 для q= 2
A022167 для q= 3
A022168 для q= 4
A022169 для q= 5
A022170 для q= 6
A022171 для q= 7
A022172 для q= 8
A022173 для q= 9
A022174 для q= 10

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend Шаблон:Rq

Гауссовы биномиальные коэффициенты

Содержание

Определение

Примеры

Комбинаторное описание

Свойства

Приложения

Треугольники

Примечания

Литература

Навигация

Гауссовы биномиальные коэффициенты

Определение

Примеры

Комбинаторное описание

Свойства

Приложения

Треугольники

Примечания

Литература

Навигация

Поиск