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

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

Визначення

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

{(\binom{m}{r})}_{q} = {\begin{matrix} \frac{(1 - q^{m}) (1 - q^{m - 1}) \dots (1 - q^{m - r + 1})}{(1 - q) (1 - q^{2}) \dots (1 - q^{r})} & r ⩽ m \\ 0 & r > m \end{matrix}

,

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

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

{[\begin{matrix} m \\ r \end{matrix}]}_{q}

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

[k]_{q} = \frac{1 - q^{k}}{1 - q} = \sum_{0 ⩽ i < k} q^{i} = 1 + q + q^{2} + \dots + q^{k - 1};

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

{(\binom{m}{r})}_{q} = \frac{[m]_{q} [m - 1]_{q} \dots [m - r + 1]_{q}}{[1]_{q} [2]_{q} \dots [r]_{q}} (r ⩽ m),

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

{(\binom{m}{r})}_{q} = \frac{[m]_{q}!}{[r]_{q}! [m - r]_{q}!} (r ⩽ m)

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

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

{(\binom{\infty}{r})}_{q} = \lim_{m \to \infty} {(\binom{m}{r})}_{q} = \frac{1}{[r]_{q}! (1 - q)^{r}}

Приклади

{(\binom{0}{0})}_{q} = {(\binom{1}{0})}_{q} = 1

{(\binom{1}{1})}_{q} = \frac{1 - q}{1 - q} = 1

{(\binom{2}{1})}_{q} = \frac{1 - q^{2}}{1 - q} = 1 + q

{(\binom{3}{1})}_{q} = \frac{1 - q^{3}}{1 - q} = 1 + q + q^{2}

{(\binom{3}{2})}_{q} = \frac{(1 - q^{3}) (1 - q^{2})}{(1 - q) (1 - q^{2})} = 1 + q + q^{2}

{(\binom{4}{2})}_{q} = \frac{(1 - q^{4}) (1 - q^{3})}{(1 - q) (1 - q^{2})} = (1 + q^{2}) (1 + q + q^{2}) = 1 + q + 2 q^{2} + q^{3} + q^{4}

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

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

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

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

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

Властивості

Подібно до звичайних біноміальних коефіцієнтів гауссові біноміальні коефіцієнти контрсиметричні, тобто інваріантні відносно відображення $r \to m - r$ :

{(\binom{m}{r})}_{q} = {(\binom{m}{m - r})}_{q} .

Зокрема,

{(\binom{m}{0})}_{q} = {(\binom{m}{m})}_{q} = 1,

{(\binom{m}{1})}_{q} = {(\binom{m}{m - 1})}_{q} = \frac{1 - q^{m}}{1 - q} = 1 + q + \dots + q^{m - 1} m ⩾ 1 .

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

\lim_{q \to 1} {(\binom{m}{r})}_{q} = (\binom{m}{r})

для всіх m і r.

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

{(\binom{m}{r})}_{q} = q^{r} {(\binom{m - 1}{r})}_{q} + {(\binom{m - 1}{r - 1})}_{q}

і

{(\binom{m}{r})}_{q} = {(\binom{m - 1}{r})}_{q} + q^{m - r} {(\binom{m - 1}{r - 1})}_{q} .

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

\prod_{k = 0}^{n - 1} (1 + q^{k} t) = \sum_{k = 0}^{n} q^{k (k - 1) / 2} {(\binom{n}{k})}_{q} t^{k}

і

\prod_{k = 0}^{n - 1} \frac{1}{(1 - q^{k} t)} = \sum_{k = 0}^{\infty} {(\binom{n + k - 1}{k})}_{q} t^{k} .

і при $n \to \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), використовуючи початкові «граничні» значення

{(\binom{m}{m})}_{q} = {(\binom{m}{0})}_{q} = 1

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

{(\binom{m}{r})}_{q} = \frac{1 - q^{m}}{1 - q^{m - r}} {(\binom{m - 1}{r})}_{q}

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

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

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

{(\binom{n + m}{m})}_{q}

є числом розбиттів числа r на m або менше частин, кожна з яких не більша від n. Еквівалентно, це також число розбиттів числа r на n або менше частин, кожна з яких не більша від m.

Гауссові біноміальні коефіцієнти відіграють також важливу роль у перерахуванні проєктивних просторів, визначених над скінченним полем. Зокрема, для будь-якого скінченного поля F_q з q елементами, гауссів біноміальний коефіцієнт

{(\binom{n}{k})}_{q}

підраховує число k-вимірних векторних підпросторів n-вимірного векторного простору над F_q (грассманіан). Якщо розкласти у вигляді многочлена від q, це дає добре відомий розклад грассманіана на комірки Шуберта. Наприклад, гауссів біноміальний коефіцієнт

{(\binom{n}{1})}_{q} = 1 + q + q^{2} + \dots + q^{n - 1}

є числом одновимірних підпросторів у (F_q)ⁿ (еквівалентно, число точок у асоційованому проєктивному просторі). Більш того, якщо q дорівнює 1 (відповідно, −1), гауссів біноміальний коефіцієнт дає ейлерову характеристику відповідного комплексного (відповідно, дійсного) грассманіана.

Число k-вимірних афінних підпросторів F_qⁿ дорівнює

q^{n - k} {(\binom{n}{k})}_{q}

.

Це дозволяє іншу інтерпретацію тотожності

{(\binom{m}{r})}_{q} = {(\binom{m - 1}{r})}_{q} + q^{m - r} {(\binom{m - 1}{r - 1})}_{q}

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

У теорії квантових груп прийнято дещо відмінні угоди у визначенні. Квантові біноміальні коефіцієнти рівні

q^{k^{2} - n k} {(\binom{n}{k})}_{q^{2}}

.

Ця версія квантового біноміального коефіцієнта симетрична відносно $q$ і $q^{- 1}$ .

Трикутники

Гауссові біноміальні коефіцієнти можна розташувати у вигляді трикутника для кожного q і цей трикутник для q = 1 збігається з трикутником Паскаля Шаблон:Sfn.

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

Примітки

Шаблон:Reflist

Література

Шаблон:Refbegin

Шаблон:Refend

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

Зміст

Визначення

Приклади

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

Властивості

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

Трикутники

Примітки

Література

Навігаційне меню

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

Визначення

Приклади

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

Властивості

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

Трикутники

Примітки

Література

Навігаційне меню

Пошук