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

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

Визначення

Гауссові біноміальні коефіцієнти визначають так:

${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 — невід'ємні цілі числа.

У статті Смирнова і книзі Васильєва замість круглих дужок використано квадратні:

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

для $r=0$ значення дорівнює 1, оскільки чисельник і знаменник є порожніми добутками. Хоча формула в першому виразі є раціональною функцією, насправді вона задає многочлен. Зауважимо, що формулу можна застосувати для $r=m+1$, що дає 0 через наявність множника $1-q^{0}=0$ в чисельнику згідно з другим виразом (для будь-якого більшого r множник 0 присутній у чисельнику, але подальші прості множники будуть із негативними степенями q, тому явний другий вираз зручніший). Усі множники в чисельнику і знаменнику діляться на 1 − q з часткою у вигляді q-числа:

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

Це дає еквівалентну формулу

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

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

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

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

На відміну від звичайного біноміального коефіцієнта, гауссів біноміальний коефіцієнт має скінченні значення для $m\rightarrow \infty$ (границя має аналітичний сенс для $|q|<1$):

${\infty \choose r}_{q}=\lim _{m\rightarrow \infty }{m \choose r}_{q}={\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}$

Комбінаторний опис

Замість цих виразів алгебри, можна також дати комбінаторне визначення гауссових біноміальних коефіцієнтів. Звичайний біноміальний коефіцієнт ${\tbinom {m}{r}}$ підраховує r-сполуки, вибрані зі множини з m елементами. Якщо розподілити m елементів як різні символи в слові довжини m то кожна r-сполука відповідає слову довжини m складеному з алфавіту з двома буквами, скажімо, {0,1}, з r копіями букви 1 (яка вказує, що букву вибрано) і з m − r копіями букви 0 (для решти позицій).

Слова ${4 \choose 2}=6$, Що використовують нулі і одиниці, це 0011, 0101, 0110 1001, 1010, 1100.

Щоб отримати з цієї моделі гауссів біноміальний коефіцієнт ${\tbinom {m}{r}}_{q}$, достатньо порахувати кожне слово з множником q^d, де d дорівнює числу «інверсій» у слові — число пар позицій, для яких ліва позиція пари дорівнює 1, а права позиція містить 0 у слові. Наприклад, існує одне слово з 0 інверсіями, 0011. Є одне слово з однією інверсією, 0101. Є два слова з двома інверсіями, 0110 і 1001. Існує одне слово з трьома інверсіями, 1010, і, нарешті, одне слово з чотирма інверсіями, 1100. Це відповідає коефіцієнтам у ${4 \choose 2}_{q}=1+q+2q^{2}+q^{3}+q^{4}$.

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

Властивості

Подібно до звичайних біноміальних коефіцієнтів гауссові біноміальні коефіцієнти контрсиметричні, тобто інваріантні відносно відображення $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\geqslant 1\,.$

Назва гауссів біноміальний коефіцієнт пояснюється фактом, що його значення в точці $q=1$ дорівнює

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

для всіх m і r.

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

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

Є аналоги біноміальних формул і узагальнені ньютонові версії їх для від'ємних цілих степенів, хоча в першому випадку гауссові біноміальні коефіцієнти не з'являються як коефіцієнти:

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

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

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

І, між іншим, показує, що гауссові біноміальні коефіцієнти є реально многочленами (від q). Друга тотожність Паскаля випливає з першої за допомогою підстановки $r\rightarrow m-r$ і інваріантності гауссових біноміальних коефіцієнтів відносно відбиття $r\rightarrow m-r$. З тотожностей Паскаля випливає

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

що приводить (при ітераціях для m, m — 1, m — 2 ,….) до виразу для гауссових біноміальних коефіцієнтів, як у визначенні вище.

Застосування

Гауссові біноміальні коефіцієнти з'являються в підрахунку симетричних многочленів і в теорії розбиття чисел. Коефіцієнт q ^r в

${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 і цей трикутник для 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

Література

• Смирнов Е. Ю. Диаграммы Юнга и q-комбинаторика // Квант. — 2015. — № 1 (17 липня). — С. 7-12. — ISSN 0130-2221. Архівовано з джерела 22 квітня 2018. Процитовано 3 червня 2021.
• Кузьмин О.В. Обобщённые пирамиды Паскаля и их приложения. — Новосибирск : «Наука» Сибирская издательская фирма РАН, 2000. — ISBN 5-02-031578-8.
• Exton H. q-Hypergeometric Functions and Applications. — New York : Halstead Press, 1983. — ISBN 0853124914.
• Eugene Mukhin. Symmetric Polynomials and Partitions. Архівовано з джерела 10 грудня 2004.
• Ratnadha Kolhatkar. Zeta function of Grassmann Varieties. — 2004. — January. Архівовано з джерела 27 лютого 2021. Процитовано 3 червня 2021.
• Weisstein, Eric W. q-біноміальні коефіцієнти(англ.) на сайті Wolfram MathWorld.
• Henry Gould. The bracket function and Fontene-Ward generalized binomial coefficients with application to Fibonomial coefficients // Fibonacci Quarterly. — 1969. — Т. 7 (17 липня). — С. 23–40.
• Alexanderson G. L. A Fibonacci analogue of Gaussian binomial coefficients // Fibonacci Quarterly. — 1974. — Т. 12 (17 липня). — С. 129–132.
• George E. Andrews. Applications of basic hypergeometric functions // SIAM Rev.. — 1974. — Т. 16, вип. 4 (17 липня). — DOI:10.1137/1016081.
• Peter B. Borwein. Padé approximants for the q-elementary functions // Construct. Approx.. — 1988. — Т. 4, вип. 1 (17 липня). — С. 391–402. — DOI:10.1007/BF02075469.
• John Konvalina. Generalized binomial coefficients and the subset-subspace problem // Adv. Appl. Math.. — 1998. — Т. 21 (17 липня). — С. 228–240. — DOI:10.1006/aama.1998.0598.
• Di Bucchianico A. Combinatorics, computer algebra and the Wilcoxon-Mann-Whitney test // J. Stat. Plann. Inf.. — 1999. — Т. 79 (17 липня). — С. 349–364. — DOI:10.1016/S0378-3758(98)00261-4.
• John Konvalina. A unified interpretation of the Binomial Coefficients, the Stirling numbers, and the Gaussian coefficients // Amer. Math. Monthly. — 2000. — Т. 107, вип. 10 (17 липня). — С. 901–910.
• Boris A. Kupershmidt. q-Newton binomial: from Euler to Gauss // J. Nonlin. Math. Phys.. — 2000. — Т. 7, вип. 2 (17 липня). — С. 244–262. — arXiv:math/0004187. — Bibcode:2000JNMP....7..244K. — DOI:10.2991/jnmp.2000.7.2.11.
• Henry Cohn. Projective geometry over F₁ and the Gaussian Binomial Coefficients // Amer. Math. Monthly. — 2004. — Т. 111, вип. 6 (17 липня). — С. 487–495. Архівовано з джерела 15 травня 2021. Процитовано 3 червня 2021.
• Kim T. q-Extension of the Euler formula and trigonometric functions // Russ. J. Math. Phys.. — 2007. — Т. 14, вип. 3 (17 липня). — С. 275–278. — Bibcode:2007RJMP...14..275K. — DOI:10.1134/S1061920807030041.
• Kim T. q-Bernoulli numbers and polynomials associated with Gaussian binomial coefficients // Russ. J. Math. Phys.. — 2008. — Т. 15, вип. 1 (17 липня). — С. 51–57. — Bibcode:2008RJMP...15...51K. — DOI:10.1134/S1061920808010068.
• Roberto B. Corcino. On p,q-binomial coefficients // Integers. — 2008. — Т. 8 (17 липня). — С. #A29.
• Gevorg Hmayakyan. Recursive Formula Related To The Mobius Function. — 2009. — 17 липня. Архівовано з джерела 6 травня 2021. Процитовано 3 червня 2021.