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

В математике гауссовы биномиальные коэффициенты (также называемые гауссовскими коэффициентами , гауссовыми полиномами или q -биномиальными коэффициентами ) являются q -аналогами биномиальных коэффициентов . Биномиальный коэффициент Гаусса, записанный как ${\binom {n}{k}}_{q}$ или ${\begin{bmatrix}n\\k\end{bmatrix}}_{q}$, представляет собой многочлен от q с целыми коэффициентами, значение которого, когда q установлено в степень простого числа, подсчитывает количество подпространств размерности k в векторном пространстве размерности n над $\mathbb {F} _{q}$, конечное поле с q элементами; т. е. это количество точек в конечном грассманиане $\mathrm {Gr} (k,\mathbb {F} _{q}^{n})$.

Определение

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

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

где m и r — целые неотрицательные числа. Если r > m , это значение равно 0. Для r = 0 значение равно 1, поскольку и числитель, и знаменатель являются пустыми произведениями .

Хотя формула на первый взгляд кажется рациональной функцией , на самом деле она представляет собой полином, поскольку деление точно по Z [ q ]

Все множители в числителе и знаменателе делятся на 1 − q , а частное — это q -число :

$[k]_{q}=\sum _{0\leq i<k}q^{i}=1+q+q^{2}+\cdots +q^{k-1}={\begin{cases}{\frac {1-q^{k}}{1-q}}&{\text{for}}&q\neq 1\\k&{\text{for}}&q=1\end{cases}},$

Разделение этих факторов дает эквивалентную формулу

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

В терминах q- факториала $[n]_{q}!=[1]_{q}[2]_{q}\cdots [n]_{q}$, формулу можно записать как

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

Подставив q = 1 в ${\tbinom {m}{r}}_{q}$ дает обычный биномиальный коэффициент ${\tbinom {m}{r}}$.

Биномиальный коэффициент Гаусса имеет конечные значения: $m\rightarrow \infty$:

${\infty \choose r}_{q}=\lim _{m\rightarrow \infty }{m \choose r}_{q}={\frac {1}{(1-q)(1-q^{2})\cdots (1-q^{r})}}={\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}$

${6 \choose 3}_{q}={\frac {(1-q^{6})(1-q^{5})(1-q^{4})}{(1-q)(1-q^{2})(1-q^{3})}}=(1+q^{2})(1+q^{3})(1+q+q^{2}+q^{3}+q^{4})=1+q+2q^{2}+3q^{3}+3q^{4}+3q^{5}+3q^{6}+2q^{7}+q^{8}+q^{9}$

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

Инверсии

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

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

Так, например, ${4 \choose 2}=6$ слова, в которых используются 0 и 1 , являются $0011,0101,0110,1001,1010,1100$.

Чтобы получить биномиальный коэффициент Гаусса ${\tbinom {m}{r}}_{q}$каждому слову соответствует фактор q ^д , где d — количество инверсий слова, где в данном случае инверсия — это пара позиций, где левая часть пары содержит букву 1 , а правая позиция — букву 0 .

В приведенном выше примере есть одно слово с 0 инверсиями, $0011$, одно слово с 1 обращением, $0101$, два слова с 2 инверсиями, $0110$, $1001$, одно слово с 3 обращениями, $1010$, и одно слово с 4 инверсиями, $1100$. Это также количество сдвигов влево на 1 с от исходного положения.

Они соответствуют коэффициентам в ${4 \choose 2}_{q}=1+q+2q^{2}+q^{3}+q^{4}$.

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

Шары в контейнеры

Позволять $B(n,m,r)$ быть числом способов броска $r$ неразличимые шарики в $m$ неразличимые контейнеры, где каждый контейнер может содержать до $n$ шарики. Биномиальный коэффициент Гаусса можно использовать для характеристики $B(n,m,r)$. Действительно,

$B(n,m,r)=[q^{r}]{n+m \choose m}_{q}.$

где $[q^{r}]P$ обозначает коэффициент $q^{r}$ в полиномиальном $P$ (см. также раздел «Приложения» ниже).

Характеристики

Отражение

Как и обычные биномиальные коэффициенты, гауссовы биномиальные коэффициенты центрально-симметричны, т. е. инвариантны относительно отражения. $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\geq 1\,.$

Предел при q = 1

Оценка гауссовского биномиального коэффициента при q = 1 равна

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

т.е. сумма коэффициентов дает соответствующее биномиальное значение.

Степень полинома

Степень ${\binom {m}{r}}_{q}$ является ${\binom {m+1}{2}}-{\binom {r+1}{2}}-{\binom {(m-r)+1}{2}}=r(m-r)$.

q тождества

Аналоги личности Паскаля

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

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

Когда $q=1$, оба они дают обычное биномиальное тождество. Мы можем видеть это как $m\to \infty$, оба уравнения остаются в силе.

) вычислять гауссовы биномиальные коэффициенты, Первый аналог Паскаля позволяет рекурсивно (по отношению к m используя начальные значения.

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

а также показывает, что гауссовы биномиальные коэффициенты действительно являются полиномами (по q ).

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

Эти тождества имеют естественную интерпретацию в терминах линейной алгебры. Напомним, что ${\tbinom {m}{r}}_{q}$ считает r -мерные подпространства $V\subset \mathbb {F} _{q}^{m}$, и пусть $\pi :\mathbb {F} _{q}^{m}\to \mathbb {F} _{q}^{m-1}$ быть проекцией с одномерным нулевым пространством $E_{1}$. Первое тождество возникает из биекции, которая принимает $V\subset \mathbb {F} _{q}^{m}$ в подпространство $V'=\pi (V)\subset \mathbb {F} _{q}^{m-1}$; в случае $E_{1}\not \subset V$, пространство $V'$ является r -мерной, и мы также должны отслеживать линейную функцию $\phi :V'\to E_{1}$ чей график $V$; но в случае $E_{1}\subset V$, пространство $V'$ является ( r −1)-мерным, и мы можем восстановить $V=\pi ^{-1}(V')$ без какой-либо дополнительной информации. Второе тождество имеет аналогичную интерпретацию, принимая $V$ к $V'=V\cap E_{n-1}$ для ( m −1)-мерного пространства $E_{m-1}$, снова разбиваясь на два случая.

Доказательства аналогов

Оба аналога можно доказать, заметив сначала, что из определения ${\tbinom {m}{r}}_{q}$, у нас есть:

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

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

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

Как

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

Уравнение ( 1 ) становится:

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

и замена уравнения ( 3 ) дает первый аналог.

Аналогичный процесс с использованием

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

вместо этого дает второй аналог.

q -биномиальная теорема

Существует аналог биномиальной теоремы для 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}}}$.

Параметр $t=q$ дает производящие функции для различных и любых частей соответственно. (См. также Основные гипергеометрические ряды .)

Центральная q-биномиальная идентичность

С обычными биномиальными коэффициентами мы имеем:

$\sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}$

С q-биномиальными коэффициентами аналог:

$\sum _{k=0}^{n}q^{k^{2}}{\binom {n}{k}}_{q}^{2}={\binom {2n}{n}}_{q}$

Приложения

Первоначально Гаусс использовал биномиальные коэффициенты Гаусса при определении знака квадратичной суммы Гаусса .

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

${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-аналогов

Ссылки

• Экстон, Х. (1983), q-гипергеометрические функции и приложения , Нью-Йорк: Halstead Press, Чичестер: Эллис Хорвуд, 1983, ISBN   0853124914 , ISBN   0470274530 , ISBN   978-0470274538
• Мухин, Евгений. «Симметричные полиномы и разбиения» (PDF) . Архивировано из оригинала (PDF) 4 марта 2016 г. (без даты, 2004 г. или ранее).
• Ратнадха Колхаткар, дзета-функция сортов Грассмана (от 26 января 2004 г.)
• Вайсштейн, Эрик В. «q-биномиальный коэффициент» . Математический мир .
• Гулд, Генри (1969). «Скобочная функция и обобщенные биномиальные коэффициенты Фонтена-Уорда с применением к фибономиальным коэффициентам». Ежеквартальный журнал Фибоначчи . 7 : 23–40. МР   0242691 .
• Александерсон, GL (1974). «Аналог Фибоначчи биномиальных коэффициентов Гаусса». Ежеквартальный журнал Фибоначчи . 12 : 129–132. МР   0354537 .
• Эндрюс, Джордж Э. (1974). «Приложения основных гипергеометрических функций». СИАМ преп . 16 (4): 441–484. дои : 10.1137/1016081 . JSTOR   2028690 . МР   0352557 .
• Борвейн, Питер Б. (1988). «Аппроксимации Паде для q-элементарных функций». Построить. Прибл . 4 (1): 391–402. дои : 10.1007/BF02075469 . МР   0956175 . S2CID   124884851 .
• Конвалина, Джон (1998). «Обобщенные биномиальные коэффициенты и проблема подмножества-подпространства» . Адв. Прил. Математика . 21 (2): 228–240. дои : 10.1006/aama.1998.0598 . МР   1634713 .
• Ди Буккьянико, А. (1999). «Комбинаторика, компьютерная алгебра и тест Уилкоксона-Манна-Уитни». J.Stat. План. Инф . 79 (2): 349–364. CiteSeerX   10.1.1.11.7713 . дои : 10.1016/S0378-3758(98)00261-4 .
• Конвалина, Джон (2000). «Единая интерпретация биномиальных коэффициентов, чисел Стирлинга и коэффициентов Гаусса». амер. Математика. Ежемесячно . 107 (10): 901–910. дои : 10.2307/2695583 . JSTOR   2695583 . МР   1806919 .
• Купершмидт, Борис А. (2000). «Бином q-Ньютона: от Эйлера до Гаусса». Дж. Нелинейная математика. Физ . 7 (2): 244–262. arXiv : math/0004187 . Бибкод : 2000JNMP....7..244K . дои : 10.2991/jnmp.2000.7.2.11 . МР   1763640 . S2CID   125273424 .
• Кон, Генри (2004). «Проективная геометрия над F ₁ и биномиальные коэффициенты Гаусса» . амер. Математика. Ежемесячно . 111 (6): 487–495. дои : 10.2307/4145067 . JSTOR   4145067 . МР   2076581 .
• Ким, Т. (2007). «q-Расширение формулы Эйлера и тригонометрические функции». Расс. Дж. Математика. Физ . 14 (3): –275–278. Бибкод : 2007RJMP...14..275K . дои : 10.1134/S1061920807030041 . МР   2341775 . S2CID   122865930 .
• Ким, Т. (2008). «q-числа Бернулли и полиномы, связанные с биномиальными коэффициентами Гаусса». Расс. Дж. Математика. Физ . 15 (1): 51–57. Бибкод : 2008RJMP...15...51K . дои : 10.1134/S1061920808010068 . МР   2390694 . S2CID   122966597 .
• Корчино, Роберто Б. (2008). «О p,q-биномиальных коэффициентах». Целые числа . 8 : #A29. МР   2425627 .
• Амаякян, Геворг. «Рекурсивная формула, связанная с функцией Мебиуса» (PDF) . (2009).