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

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

Определение

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

${m \choose r}_{q}={\begin{cases}{\frac {(1-q^{m})(1-q^{m-1})\cdots (1-q^{m-r+1})}{(1-q)(1-q^{2})\cdots (1-q^{r})}}&r\leqslant m\\0&r>m\end{cases}}$,

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

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

$\left[{\begin{array}{c}m\\r\\\end{array}}\right]_{q}$

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

$[k]_{q}={\frac {1-q^{k}}{1-q}}=\sum _{0\leqslant i<k}q^{i}=1+q+q^{2}+\cdots +q^{k-1};$

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

${m \choose r}_{q}={\frac {[m]_{q}[m-1]_{q}\cdots [m-r+1]_{q}}{[1]_{q}[2]_{q}\cdots [r]_{q}}}\quad (r\leqslant m),$

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

${m \choose r}_{q}={\frac {[m]_{q}!}{[r]_{q}!\,[m-r]_{q}!}}\quad (r\leqslant m)$

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

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

${\infty \choose r}_{q}=\lim _{m\rightarrow \infty }{m \choose r}_{q}={\frac {1}{[r]_{q}!\,(1-q)^{r}}}$

Примеры

${0 \choose 0}_{q}={1 \choose 0}_{q}=1$

${1 \choose 1}_{q}={\frac {1-q}{1-q}}=1$

${2 \choose 1}_{q}={\frac {1-q^{2}}{1-q}}=1+q$

${3 \choose 1}_{q}={\frac {1-q^{3}}{1-q}}=1+q+q^{2}$

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

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

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

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

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

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

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

Свойства

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

${m \choose r}_{q}={m \choose m-r}_{q}.$

В частности,

${m \choose 0}_{q}={m \choose m}_{q}=1\,,$

${m \choose 1}_{q}={m \choose m-1}_{q}={\frac {1-q^{m}}{1-q}}=1+q+\cdots +q^{m-1}\quad m\geqslant 1\,.$

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

$\lim _{q\to 1}{m \choose r}_{q}={m \choose r}$

Для всех m и r.

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

${m \choose r}_{q}=q^{r}{m-1 \choose r}_{q}+{m-1 \choose r-1}_{q}$

и

${m \choose r}_{q}={m-1 \choose r}_{q}+q^{m-r}{m-1 \choose r-1}_{q}.$

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

$\prod _{k=0}^{n-1}(1+q^{k}t)=\sum _{k=0}^{n}q^{k(k-1)/2}{n \choose k}_{q}t^{k}$

и

$\prod _{k=0}^{n-1}{\frac {1}{(1-q^{k}t)}}=\sum _{k=0}^{\infty }{n+k-1 \choose k}_{q}t^{k}.$

и при $n\rightarrow \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), используя начальные «граничные» значения

${m \choose m}_{q}={m \choose 0}_{q}=1$

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

${m \choose r}_{q}={{1-q^{m}} \over {1-q^{m-r}}}{m-1 \choose r}_{q}$

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

Приложения

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

${n+m \choose m}_{q}$

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

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

${n \choose k}_{q}$

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

${n \choose 1}_{q}=1+q+q^{2}+\cdots +q^{n-1}$

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

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

$q^{n-k}{n \choose k}_{q}$.

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

${m \choose r}_{q}={m-1 \choose r}_{q}+q^{m-r}{m-1 \choose r-1}_{q}$

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

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

$q^{k^{2}-nk}{n \choose k}_{q^{2}}$.

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

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

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

Если размещать строки этих треугольников в одну линию, получим следующие последовательности 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