WikiDer > Биномиальный коэффициент Гаусса

Gaussian binomial coefficient

В математика, то Гауссовы биномиальные коэффициенты (также называемый Коэффициенты Гаусса, Многочлены Гаусса, или же q-биномиальные коэффициенты) находятся q-аналоги из биномиальные коэффициенты. Биномиальный коэффициент Гаусса, записанный как или же , является полиномом от q с целыми коэффициентами, значение которых при q устанавливается в степень простого числа, подсчитывает количество подпространств размерности k в векторном пространстве размерности п над конечным полем с q элементы.

Определение

Гауссовы биномиальные коэффициенты определяются как

куда м и р неотрицательные целые числа. За р = 0 значение равно 1, поскольку числитель и знаменатель равны пустые продукты. Хотя формула в первом предложении, похоже, включает рациональная функция, он фактически обозначает многочлен, потому что деление точное в Z[q]. Обратите внимание, что формула может применяться для р = м + 1, и дает 0 из-за множителя 1 − q0 = 0 в числителе в соответствии со вторым предложением (для еще большего р множитель 0 остается в числителе, но его дальнейшие множители будут включать отрицательные степени q, поэтому явное указание второго предложения предпочтительнее). Все множители в числителе и знаменателе делятся на 1 − q, с частным a q номер:

разделение этих факторов дает эквивалентную формулу

что делает очевидным тот факт, что подстановка q = 1 в дает обычный биномиальный коэффициент Что касается q факториал , формулу можно записать как

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

В отличие от обычного биномиального коэффициента, биномиальный коэффициент Гаусса имеет конечные значения при (предел, имеющий аналитическое значение для |q|<1):

Примеры

Комбинаторное описание

Вместо этих алгебраических выражений можно также дать комбинаторное определение гауссовских биномиальных коэффициентов. Обычный биномиальный коэффициент считает р-комбинации выбран из м-элементный набор. Если взять те м элементы, чтобы быть разными позициями символов в слове длины м, то каждый р-комбинация соответствует длине слова м используя алфавит из двух букв, скажем {0,1}, с р копии буквы 1 (с указанием позиций в выбранной комбинации) и мр буквы 0 (для остальных позиций).

В слова, использующие 0 и 1, будут 0011, 0101, 0110, 1001, 1010, 1100.

Чтобы получить из этой модели гауссовский биномиальный коэффициент , достаточно посчитать каждое слово с множителем qd, куда d - это количество «инверсий» слова: количество пар позиций, для которых крайняя левая позиция пары содержит букву 1, а крайняя правая позиция содержит букву 0 в слове. Например, есть одно слово с 0 инверсиями, 0011. Есть 1 только с одной инверсией, 0101. Есть два слова с двумя инверсиями, 0110 и 1001. Есть одно с 3, 1010 и, наконец, одно слово с 4 инверсии, 1100. Это соответствует коэффициентам в . Обратите внимание, когда q = 1, биномиальный коэффициент Гаусса дает тот же ответ, что и обычный биномиальный коэффициент.

Можно показать, что определенные таким образом многочлены удовлетворяют тождествам Паскаля, приведенным ниже, и поэтому совпадают с многочленами, заданными алгебраическими определениями. Визуальный способ увидеть это определение - связать с каждым словом путь через прямоугольную сетку со сторонами высоты. р и ширина мр, из нижнего левого угла в верхний правый угол, делая шаг вправо для каждой буквы 0 и шаг вверх для каждой буквы 1. Тогда количество инверсий слова равно площади той части прямоугольника, которая соответствует в правом нижнем углу пути.

Шары в мусорные ведра (урны)

Позволять быть количеством способов броска неразличимые шары в неразличимые бункеры (урны), каждый из которых может содержать до мячи. Биномиальный коэффициент Гаусса можно использовать для характеристики . В самом деле,

куда обозначает коэффициент при в полиноме (см. также раздел «Приложения» ниже).

Характеристики

Как и обычные биномиальные коэффициенты, гауссовские биномиальные коэффициенты центрально-симметричны, т. Е. Инвариантны относительно отражения :

Особенно,

Название Биномиальный коэффициент Гаусса проистекает из факта[нужна цитата] что их оценка на q = 1 является

для всех м и р.

Аналоги Личность Паскаля для гауссовских биномиальных коэффициентов равны

и

Первое тождество Паскаля позволяет вычислять гауссовские биномиальные коэффициенты рекурсивно (относительно м ) с использованием начальных значений

а также случайно показывает, что гауссовы биномиальные коэффициенты действительно являются полиномами (в q). Второе тождество Паскаля следует из первого с помощью замены и инвариантность гауссовских биномиальных коэффициентов относительно отражения . Обе тождества Паскаля вместе подразумевают

что приводит (при итеративном применении к м, м − 1, м - 2, ....) в выражение для биномиального коэффициента Гаусса, как указано в определении выше.

q-биномиальная теорема

Есть аналог биномиальная теорема за q-биномиальные коэффициенты:

Как и обычная биномиальная теорема, эта формула имеет множество обобщений и расширений; один из них, соответствующий обобщенной биномиальной теореме Ньютона для отрицательных степеней, -

В пределе эти формулы дают

и

Приложения

Гауссовские биномиальные коэффициенты возникают при подсчете симметричные многочлены и в теории перегородки. Коэффициент qр в

это количество разделов р с м или меньшее количество частей, каждая из которых меньше или равна п. Эквивалентно, это также количество разделов р с п или меньшее количество частей, каждая из которых меньше или равна м.

Гауссовские биномиальные коэффициенты также играют важную роль в перечислительной теории проективные пространства определен над конечным полем. В частности, для каждого конечное поле Fq с q элементов, гауссов биномиальный коэффициент

считает количество k-мерные векторные подпространства п-размерный векторное пространство над FqГрассманиан). При разложении как полином от q, это дает известное разложение грассманиана на клетки Шуберта. Например, биномиальный коэффициент Гаусса

- количество одномерных подпространств в (Fq)п (эквивалентно, количество точек в ассоциированном проективное пространство). Кроме того, когда q равен 1 (соответственно -1), биномиальный коэффициент Гаусса дает Эйлерова характеристика соответствующего комплексного (соответственно действительного) грассманиана.

Количество k-мерные аффинные подпространства Fqп равно

.

Это позволяет по-другому интерпретировать идентичность

считая (р - 1) -мерные подпространства в (м - 1) -мерное проективное пространство путем фиксации гиперплоскости, подсчета таких подпространств, содержащихся в этой гиперплоскости, а затем подсчета подпространств, не содержащихся в гиперплоскости; эти последние подпространства находятся в биективном соответствии с (р - 1) -мерные аффинные подпространства пространства, полученные при рассмотрении этой фиксированной гиперплоскости как гиперплоскости на бесконечности.

В соглашениях, распространенных в приложениях к квантовые группы, используется немного другое определение; квантовый биномиальный коэффициент есть

.

Этот вариант квантово-биномиального коэффициента симметричен относительно замены и .

Треугольники

Биномиальные коэффициенты Гаусса могут быть расположены в треугольнике для каждого q, который Треугольник Паскаля за q=1.
Прочтите строку за строкой, эти треугольники образуют следующие последовательности в OEIS:

Рекомендации