Гауссовы биномиальные коэффициенты: различия между версиями
Jumpow (обсуждение | вклад) Перевод с английского статьи "Gaussian binomial coefficient" |
(нет различий)
|
Версия от 16:14, 21 апреля 2018
Гауссовы биномиальные коэффициенты (а также гауссовы коэффициенты, гауссовы многочлены или q-биномиальные коэффициенты) — это q-аналоги?! биномиальных коэффициентов. Гауссов биномиальный коэффициент — это многочлен от q с целыми коэффициентами, значение которого, если положить q равным степени простого числа, подсчитывает число подпространств размерности k в векторном пространстве размерности n над конечным полем с q элементами.
Определение
Гауссовы биномиальные коэффициенты определяются следующим образом
где m и r — неотрицательные целые числа. Для значение равно 1, поскольку числитель и знаменатель являются пустыми произведениями[англ.]. Хотя формула в первом выражении представляет собой рациональную функцию, на самом деле она задаёт многочлен. Заметим, что формулу можно применить для , что даёт 0 вследствие множителя в числителе согласно второму выражению (для любого бо́льшего r множитель 0 присутствует в числителе, но дальнейшие множители будут с отрицательными степенями q, вследствие чего явное второе выражение предпочтительнее). Все множители в числителе и знаменателе делятся на 1 − q с частным в виде q-числа?!:
Это даёт эквивалентную формулу
которая делает очевидным факт, что подстановка в даёт обыкновенный биномиальный коэффициент . В терминах q-факториала?! формулу можно переписать как
Эта компактная форма (часто дающаясяся в качестве определения), однако, прячет существование многих общих множителей в числителе и знаменателе. Этот вид делает очевидной симметрию для .
В отличие от обычного биномиального коэффициента, гауссов биномиальный коэффициент имеет конечные значения для (предел имеет аналитический смысл для ):
Примеры
Комбинаторное описание
Вместо этих алгебраических выражений, можно также дать комбинаторное определение гауссовых биномиальных коэффициентов. Обычный биномиальный коэффициент подсчитывает r-сочетания выбранные из множества с m элементами. Если распределить m элементов как различные символы в слове длины m, то каждое r-сочетание соответствует слову длины m, составленое из алфавита с двумя буквами, скажем, {0,1}, с r копиями буквы 1 (указывающей, что буква выбрана) и с m − r копиями буквы 0 (для оставшихся позиций).
Слова , использующие нули и единицы, это 0011, 0101, 0110, 1001, 1010, 1100.
Чтобы получить из этой модели гауссов биномиальный коэффициент , достаточно посчитать каждое слово с множителем qd, где d равно числу «инверсий» в слове — число пар позиций, для которых левая позиция пары равна 1 а правая позиция содержит 0 в слове. Например, существует одно слово с 0 инверсиями, 0011. Есть одно слово с одной инверсией, 0101. Есть два слова с двумя инверсиями, 0110 и 1001. Существует одно слово с тремя инверсиями, 1010, и, наконец, одно слово с четырьмя инверсиями, 1100. Это соответствует коэффициентам в .
Можно показать, что так определённые многочлены удовлетворяют тождествам Паскаля, данным ниже, а потому совпадаю с многочленами, определёнными алгебраически. Визуальный способ видеть это определение — сопоставить каждому слову путь через прямоугольную решётку с высотой r и шириной m − r с нижнего левого угла в правый верхний угол, при этом шаг вправо делается для буквы 0 и шаг вверх для буквы 1. Тогда число инверсий в слове равно площади части прямоугольника снизу под путём.
Свойства
Подобно обычным биномиальным коэффициентам гауссовы биномиальные коэффициенты контрсимметричны, т.е. инвариантны относительно отражения :
В частности,
Название гауссов биномиальный коэффициент объясняется фактом, что его значение в точке равно
Для всех m и r.
Аналоги тождеств Паскаля для гауссовых биномиальных коэффициентов
и
Есть аналоги биномиальных формул и обобщённые ньютоновы версии их для отрицательных целых степеней, хотя в первом случае гауссовы биномиальные коэффициенты не появляются как коэффициенты:
и
и при тождества превращаются в
и
Первое тождество Паскаля позволяет вычислить гауссовы биномиальные коэффициенты рекурсивно (относительно m ) используя начальные «граничные» значения
И, между прочим, показывает, что гауссовы биномиальные коэффициенты являются реально многочленами (от q). Второе тождество Паскаля следует из первого с помощью подстановки и инвариантности гауссовых биномиальных коэффициентов по отношению к отражению . Из тождеств Паскаля следует
что ведёт (при итерациях для m, m − 1, m − 2,....) к выражению для гауссовых биномиальных коэффициентов как в определении выше.
Приложения
Гауссовы биномиальные коэффициенты появляются в подсчёте симметрических многочленов и в теории разбиений чисел. Коэффициент qr в
является числом разбиений числа 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 совпадает с треугольником Паскаля.
Если размещать строки этих треугольников одну линию, получим следующие последовательности 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
Примечания
Литература
- Exton H. q-Hypergeometric Functions and Applications. — New York: Halstead Press, 1983. — ISBN 0853124914.
- Eugene Mukhin. Symmetric Polynomials and Partitions.
- Ratnadha Kolhatkar. Zeta function of Grassmann Varieties. — 2004. — Январь.
- Weisstein, Eric W. q-Binomial Coefficient (англ.) на сайте Wolfram MathWorld.
- Henry Gould. The bracket function and Fontene-Ward generalized binomial coefficients with application to Fibonomial coefficients // Fibonacci Quarterly. — 1969. — Т. 7. — С. 23–40.
- Alexanderson G. L. A Fibonacci analogue of Gaussian binomial coefficients // Fibonacci Quarterly. — 1974. — Т. 12. — С. 129–132.
- George E. Andrews. Applications of basic hypergeometric functions // SIAM Rev.. — 1974. — Т. 16, вып. 4. — doi:10.1137/1016081. — .
- Peter B. Borwein. Padé approximants for the q-elementary functions // Construct. Approx.. — 1988. — Т. 4, вып. 1. — С. 391–402. — doi:10.1007/BF02075469.
- John Konvalina. Generalized binomial coefficients and the subset-subspace problem // Adv. Appl. Math.. — 1998. — Т. 21. — С. 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. — С. 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. — С. 901–910. — .
- Boris A. Kupershmidt. q-Newton binomial: from Euler to Gauss // J. Nonlin. Math. Phys.. — 2000. — Т. 7, вып. 2. — С. 244–262. — doi:10.2991/jnmp.2000.7.2.11. — . — arXiv:math/0004187.
- Henry Cohn. Projective geometry over F1 and the Gaussian Binomial Coefficients // Amer. Math. Monthly. — 2004. — Т. 111, вып. 6. — С. 487–495. — .
- Kim T. q-Extension of the Euler formula and trigonometric functions // Russ. J. Math. Phys.. — 2007. — Т. 14, вып. 3. — С. 275–278. — doi:10.1134/S1061920807030041. — .
- Kim T. q-Bernoulli numbers and polynomials associated with Gaussian binomial coefficients // Russ. J. Math. Phys.. — 2008. — Т. 15, вып. 1. — С. 51–57. — doi:10.1134/S1061920808010068. — .
- Roberto B. Corcino. On p,q-binomial coefficients // Integers. — 2008. — Т. 8. — С. #A29.
- Gevorg Hmayakyan. Recursive Formula Related To The Mobius Function. — 2009.
Для улучшения этой статьи желательно:
|