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

Эта статья включает в себя список литературы , связанной литературы или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Март 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

Определение [ править ]

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

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

${\ displaystyle [k] _ {q} = \ sum _ {0 \ leq i <k} q ^ {i} = 1 + q + q ^ {2} + \ cdots + q ^ {k-1} = { \ begin {case} {\ frac {1-q ^ {k}} {1-q}} & {\ text {for}} & q \ neq 1 \\ k & {\ text {for}} & q = 1 \ end {случаи}},}$

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

${\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- факториала формулу можно записать как${\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).}$

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

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

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

Примеры [ править ]

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

Комбинаторные описания [ править ]

Инверсии [ править ]

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

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

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

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

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

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

Другой способ увидеть это - связать каждое слово с путем через прямоугольную сетку высотой r и шириной m - r , идущую от нижнего левого угла к верхнему правому углу. Путь делает шаг вправо для каждого 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\,.}$

Название биномиального коэффициента гауссова проистекает из того факта ^{[ править ]} , что их оценка при ц = 1 является

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

для всех m и r .

Аналоги личности Паскаля [ править ]

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

${\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 q=1}$${\displaystyle m\to \infty }$

Первое тождество Паскаля позволяет вычислять гауссовские биномиальные коэффициенты рекурсивно (относительно 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}[1]}$

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

Сейчас,

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

и напрямую приравнивая [1] и [2], получаем:

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

Аналогично для [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}}}}$.

Настройка дает производящие функции для отдельных и любых частей соответственно.${\displaystyle t=q}$

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

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

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

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

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

Приложения [ править ]

Гауссовские биномиальные коэффициенты встречаются при подсчете симметричных многочленов и в теории разбиений . Коэффициент при 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}}$

Ссылки [ править ]

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