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

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

Визначення

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

,

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

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

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

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

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

Ця компактна форма (яку часто дають як визначення), однак, приховує існування багатьох спільних множників в чисельнику і знаменнику. Цей вигляд робить очевидною симетрію для .

На відміну від звичайного біноміального коефіцієнта, гауссів біноміальний коефіцієнт має скінченні значення для (границя має аналітичний сенс для ):

Приклади

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

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

Слова , Що використовують нулі і одиниці, це 0011, 0101, 0110 1001, 1010, 1100.

Щоб отримати з цієї моделі гауссів біноміальний коефіцієнт , достатньо порахувати кожне слово з множником qd, де d дорівнює числу «інверсій» у слові — число пар позицій, для яких ліва позиція пари дорівнює 1, а права позиція містить 0 у слові. Наприклад, існує одне слово з 0 інверсіями, 0011. Є одне слово з однією інверсією, 0101. Є два слова з двома інверсіями, 0110 і 1001. Існує одне слово з трьома інверсіями, 1010, і, нарешті, одне слово з чотирма інверсіями, 1100. Це відповідає коефіцієнтам у .

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

Властивості

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

Зокрема,

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

для всіх m і r.

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

і

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

і

і при тотожності перетворюються на

і

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

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

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

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

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

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

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

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

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

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

.

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

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

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

.

Ця версія квантового біноміального коефіцієнта симетрична відносно і .

Трикутники

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

Якщо розміщувати рядки цих трикутників в один рядок, отримаємо такі послідовності OEIS:

Примітки

Література

  • Смирнов Е. Ю. Диаграммы Юнга и q-комбинаторика // Квант.  2015. № 1 (7 листопада). С. 7-12. ISSN 0130-2221.
  • Кузьмин О.В. Обобщённые пирамиды Паскаля и их приложения. — Новосибирск : «Наука» Сибирская издательская фирма РАН, 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.
  • 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 (7 листопада). С. 23–40.
  • Alexanderson G. L. A Fibonacci analogue of Gaussian binomial coefficients // Fibonacci Quarterly.  1974. Т. 12 (7 листопада). С. 129–132.
  • George E. Andrews. Applications of basic hypergeometric functions // SIAM Rev..  1974. Т. 16, вип. 4 (7 листопада). DOI:10.1137/1016081.
  • Peter B. Borwein. Padé approximants for the q-elementary functions // Construct. Approx..  1988. Т. 4, вип. 1 (7 листопада). С. 391–402. DOI:10.1007/BF02075469.
  • John Konvalina. Generalized binomial coefficients and the subset-subspace problem // Adv. Appl. Math..  1998. Т. 21 (7 листопада). С. 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 (7 листопада). С. 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 (7 листопада). С. 901–910.
  • Boris A. Kupershmidt. q-Newton binomial: from Euler to Gauss // J. Nonlin. Math. Phys..  2000. Т. 7, вип. 2 (7 листопада). С. 244–262. arXiv:math/0004187. Bibcode:2000JNMP....7..244K. DOI:10.2991/jnmp.2000.7.2.11.
  • Henry Cohn. Projective geometry over F1 and the Gaussian Binomial Coefficients // Amer. Math. Monthly.  2004. Т. 111, вип. 6 (7 листопада). С. 487–495.
  • Kim T. q-Extension of the Euler formula and trigonometric functions // Russ. J. Math. Phys..  2007. Т. 14, вип. 3 (7 листопада). С. 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 (7 листопада). С. 51–57. Bibcode:2008RJMP...15...51K. DOI:10.1134/S1061920808010068.
  • Roberto B. Corcino. On p,q-binomial coefficients // Integers.  2008. Т. 8 (7 листопада). С. #A29.
  • Gevorg Hmayakyan. Recursive Formula Related To The Mobius Function.  2009. — 7 листопада.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.