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

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

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

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

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

${\ displaystyle {m \ choose r} _ {q} = {\ begin {case} {\ 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 { случаи}}}$

где m и r - целые неотрицательные числа. Для r = 0 значение равно 1, поскольку числитель и знаменатель - пустые произведения . Хотя кажется, что формула в первом предложении включает рациональную функцию , на самом деле она обозначает многочлен, потому что деление является точным в Z [ q ]. Обратите внимание, что формула может применяться для r = m + 1 и дает 0 из-за множителя 1 - q ⁰ = 0 в числителе в соответствии со вторым предложением (для еще большего rмножитель 0 остается в числителе, но его дальнейшие множители будут включать отрицательные степени 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 = 1 в дает обычный биномиальный коэффициент. В терминах факториала q формулу можно записать как${\displaystyle {\tbinom {m}{r}}_{q}}$${\displaystyle {\tbinom {m}{r}}.}$ ${\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),}$

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

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

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

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

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

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

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

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

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

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

Существует аналог биномиальной теоремы для 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 ^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.
Прочтите построчно, эти треугольники образуют следующие последовательности в 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 .
• Александерсон, 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).