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

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

Определение

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

${\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\leq m\\0&r>m\end{cases}}}$

куда м и р неотрицательные целые числа. За р = 0 значение равно 1, поскольку числитель и знаменатель равны пустые продукты. Хотя формула в первом предложении, похоже, включает рациональная функция, он фактически обозначает многочлен, потому что деление точное в Z[q]. Обратите внимание, что формула может применяться для р = м + 1, и дает 0 из-за множителя 1 − q⁰ = 0 в числителе в соответствии со вторым предложением (для еще большего р множитель 0 остается в числителе, но его дальнейшие множители будут включать отрицательные степени q, поэтому явное указание второго предложения предпочтительнее). Все множители в числителе и знаменателе делятся на 1 − q, с частным a q номер:

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

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

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

что делает очевидным тот факт, что подстановка 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\leq m),}$

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

В отличие от обычного биномиального коэффициента, биномиальный коэффициент Гаусса имеет конечные значения при ${\displaystyle m\rightarrow \infty }$ (предел, имеющий аналитическое значение для |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}}}$ считает р-комбинации выбран из м-элементный набор. Если взять те м элементы, чтобы быть разными позициями символов в слове длины м, то каждый р-комбинация соответствует длине слова м используя алфавит из двух букв, скажем {0,1}, с р копии буквы 1 (с указанием позиций в выбранной комбинации) и м − р буквы 0 (для остальных позиций).

В ${\displaystyle {4 \choose 2}=6}$ слова, использующие 0 и 1, будут 0011, 0101, 0110, 1001, 1010, 1100.

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

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

Шары в мусорные ведра (урны)

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

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

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

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

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

Название Биномиальный коэффициент Гаусса проистекает из факта^{[нужна цитата ]} что их оценка на q = 1 является

${\displaystyle \lim _{q\to 1}{m \choose r}_{q}={m \choose 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}.}$

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

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

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

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

Есть аналог биномиальная теорема за q-биномиальные коэффициенты:

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

Приложения

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

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

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

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

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

считает количество k-мерные векторные подпространства п-размерный векторное пространство над 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}}$

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

В соглашениях, распространенных в приложениях к квантовые группы, используется немного другое определение; квантовый биномиальный коэффициент есть

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

Этот вариант квантово-биномиального коэффициента симметричен относительно замены ${\displaystyle q}$ и ${\displaystyle 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

Рекомендации

• Экстон, Х. (1983), q-гипергеометрические функции и приложения, Нью-Йорк: Halstead Press, Чичестер: Эллис Хорвуд, 1983, ISBN  0853124914, ISBN  0470274530, ISBN  978-0470274538
• Мухин, Евгений. «Симметричные многочлены и разбиения» (PDF). Архивировано из оригинал (PDF) 4 марта 2016 г. (без даты, 2004 г. или ранее).
• Ратнадха Колхаткар, Дзета-функция многообразий Грассмана (от 26 января 2004 г.)
• Вайсштейн, Эрик В. «q-биномиальный коэффициент». MathWorld.
• Гулд, Генри (1969). «Скобочная функция и обобщенные биномиальные коэффициенты Фонтене-Уорда с применением к фибономиальным коэффициентам». Ежеквартальный отчет Фибоначчи. 7: 23–40. МИСТЕР  0242691.
• Александерсон, Г.Л. (1974). «Аналог Фибоначчи гауссовских биномиальных коэффициентов». Ежеквартальный отчет Фибоначчи. 12: 129–132. МИСТЕР  0354537.
• Эндрюс, Джордж Э. (1974). «Приложения основных гипергеометрических функций». SIAM Rev. 16 (4): 441–484. Дои:10.1137/1016081. JSTOR  2028690. МИСТЕР  0352557.
• Борвейн, Питер Б. (1988). «Аппроксимации Паде для q-элементарных функций». Построить. Приблизительно. 4 (1): 391–402. Дои:10.1007 / BF02075469. МИСТЕР  0956175.
• Конвалина, Джон (1998). «Обобщенные биномиальные коэффициенты и проблема подмножества-подпространства». Adv. Appl. Математика. 21 (2): 228–240. Дои:10.1006 / aama.1998.0598. МИСТЕР  1634713.
• Ди Буккианико, А. (1999). «Комбинаторика, компьютерная алгебра и тест Вилкоксона-Манна-Уитни». J. Stat. Plann. Inf. 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-Ньютона: от Эйлера до Гаусса». J. Нелинейная математика. Phys. 7 (2): 244–262. arXiv:математика / 0004187. Bibcode:2000JNMP .... 7..244K. Дои:10.2991 / jnmp.2000.7.2.11. МИСТЕР  1763640.
• Кон, Генри (2004). «Проективная геометрия над F₁ и гауссовские биномиальные коэффициенты ". Амер. Математика. Ежемесячно. 111 (6): 487–495. Дои:10.2307/4145067. JSTOR  4145067. МИСТЕР  2076581.
• Ким, Т. (2007). «q-расширение формулы Эйлера и тригонометрические функции». Русь. J. Math. Phys. 14 (3): –275–278. Bibcode:2007RJMP ... 14..275K. Дои:10.1134 / S1061920807030041. МИСТЕР  2341775.
• Ким, Т. (2008). «q-числа Бернулли и многочлены, связанные с гауссовскими биномиальными коэффициентами». Русь. J. Math. Phys. 15 (1): 51–57. Bibcode:2008RJMP ... 15 ... 51К. Дои:10.1134 / S1061920808010068. МИСТЕР  2390694.
• Корчино, Роберто Б. (2008). «По p, q-биномиальным коэффициентам». Целые числа. 8: # A29. МИСТЕР  2425627.
• Амаякян, Геворг. «Рекурсивная формула, связанная с функцией Мебиуса» (PDF). (2009).