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

Гауссові біноміальні коефіцієнти (а також гауссові коефіцієнти, гауссові многочлени або q-біноміальні коефіцієнти) — це q-аналог біноміальних коефіцієнтів. Гауссів біноміальний коефіцієнт ${\displaystyle \textstyle {\binom {n}{k}}_{q}}$ — це многочлен від q з цілими коефіцієнтами, значення якого, якщо покласти q рівним степеню простого числа, підраховує число підпросторів розмірності k у векторному просторі многовиду n над скінченним полем з 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\leqslant m\\0&r>m\end{cases}}}$ ,

де m і r — невід'ємні цілі числа.

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

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

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

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

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

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

яка робить очевидним факт, що підстановка ${\displaystyle 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\leqslant m)}$

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

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

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

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

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

Властивості

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

Назва гауссів біноміальний коефіцієнт пояснюється фактом, що його значення в точці ${\displaystyle q=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}.}$

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

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

Перша тотожність Паскаля дозволяє обчислити гауссові біноміальні коефіцієнти рекурсивно (відносно 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 ^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

Примітки

1. Кузьмин, 2000, с. 19.
2. Смирнов, 2015, с. 8.
3. Смирнов, 2015, с. 9.
4. Смирнов, 2015, с. 10.

Література

• Смирнов Е. Ю. Диаграммы Юнга и q-комбинаторика // Квант. — 2015. — № 1 (17 липня). — С. 7-12. — ISSN 0130-2221. з джерела 22 квітня 2018. Процитовано 3 червня 2021.
• Кузьмин О.В. Обобщённые пирамиды Паскаля и их приложения. — Новосибирск : «Наука» Сибирская издательская фирма РАН, 2000. — .
• Exton H. q-Hypergeometric Functions and Applications. — New York : Halstead Press, 1983. — .
• 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 // . — 1969. — Т. 7 (17 липня). — С. 23–40.
• Alexanderson G. L. A Fibonacci analogue of Gaussian binomial coefficients // . — 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.