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

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

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

${\displaystyle {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 — неотрицательные целые числа.

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

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

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

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

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

${\displaystyle {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),}$

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

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

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

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

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

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

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

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

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

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

${\displaystyle {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}}$

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

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

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

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

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

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

В частности,

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

${\displaystyle {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\,.}$

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

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

Для всех m и r.

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

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

и

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

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

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

и

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

и при ${\displaystyle n\rightarrow \infty }$ тождества превращаются в

${\displaystyle \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}}}}$

и

${\displaystyle \prod _{k=0}^{\infty }{\frac {1}{(1-q^{k}t)}}=\sum _{k=0}^{\infty }{\frac {t^{k}}{[k]_{q}!\,(1-q)^{k}}}.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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