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

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

Визначення

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

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

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

${\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-числа^[3]:

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

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

${\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 збігається з трикутником Паскаля^[2].

Якщо розміщувати рядки цих трикутників в один рядок, отримаємо такі послідовності 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