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

Электромонтаж Ремонт и отделка Укладка напольных покрытий, теплые полы Тепловодоснабжение

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

13.12.2020

Гауссовы биномиальные коэффициенты (а также гауссовы коэффициенты, гауссовы многочлены или q-биномиальные коэффициенты) — это q-аналоги биномиальных коэффициентов. Гауссов биномиальный коэффициент ( n k ) q {displaystyle extstyle {inom {n}{k}}_{q}} — это многочлен от q с целыми коэффициентами, значение которого, если положить q равным степени простого числа, подсчитывает число подпространств размерности k в векторном пространстве размерности n над конечным полем с q элементами.

Определение

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

( m r ) q = { ( 1 − q m ) ( 1 − q m − 1 ) ⋯ ( 1 − q m − r + 1 ) ( 1 − q ) ( 1 − q 2 ) ⋯ ( 1 − q r ) r ⩽ m 0 r > m {displaystyle {m choose r}_{q}={egin{cases}{frac {(1-q^{m})(1-q^{m-1})cdots (1-q^{m-r+1})}{(1-q)(1-q^{2})cdots (1-q^{r})}}&rleqslant m&r>mend{cases}}} ,

где m и r — неотрицательные целые числа.

В статье Смирнова и книге Васильева вместо круглых скобок использованы квадратные:

[ m r ] q {displaystyle left[{egin{array}{c}mrend{array}} ight]_{q}}

Для r = 0 {displaystyle r=0} значение равно 1, поскольку числитель и знаменатель являются пустыми произведениями. Хотя формула в первом выражении представляет собой рациональную функцию, на самом деле она задаёт многочлен. Заметим, что формулу можно применить для r = m + 1 {displaystyle r=m+1} , что даёт 0 вследствие множителя 1 − q 0 = 0 {displaystyle 1-q^{0}=0} в числителе согласно второму выражению (для любого большего r множитель 0 присутствует в числителе, но дальнейшие множители будут с отрицательными степенями q, вследствие чего явное второе выражение предпочтительнее). Все множители в числителе и знаменателе делятся на 1 − q с частным в виде q-числа:

[ k ] q = 1 − q k 1 − q = ∑ 0 ⩽ i < k q i = 1 + q + q 2 + ⋯ + q k − 1 ; {displaystyle [k]_{q}={frac {1-q^{k}}{1-q}}=sum _{0leqslant i<k}q^{i}=1+q+q^{2}+cdots +q^{k-1};}

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

( m r ) q = [ m ] q [ m − 1 ] q ⋯ [ m − r + 1 ] q [ 1 ] q [ 2 ] q ⋯ [ r ] q ( r ⩽ m ) , {displaystyle {m choose r}_{q}={frac {[m]_{q}[m-1]_{q}cdots [m-r+1]_{q}}{[1]_{q}[2]_{q}cdots [r]_{q}}}quad (rleqslant m),}

которая делает очевидным факт, что подстановка q = 1 {displaystyle q=1} в ( m r ) q {displaystyle { binom {m}{r}}_{q}} даёт обыкновенный биномиальный коэффициент ( m r ) {displaystyle { binom {m}{r}}} . В терминах q-факториала [ n ] q ! = [ 1 ] q [ 2 ] q ⋯ [ n ] q {displaystyle [n]_{q}!=[1]_{q}[2]_{q}cdots [n]_{q}} формулу можно переписать как

( m r ) q = [ m ] q ! [ r ] q ! [ m − r ] q ! ( r ⩽ m ) {displaystyle {m choose r}_{q}={frac {[m]_{q}!}{[r]_{q}!,[m-r]_{q}!}}quad (rleqslant m)}

Эта компактная форма (часто дающаясяся в качестве определения), однако, прячет существование многих общих множителей в числителе и знаменателе. Этот вид делает очевидной симметрию ( m r ) q = ( m m − r ) q {displaystyle { binom {m}{r}}_{q}={ binom {m}{m-r}}_{q}} для r ⩽ m {displaystyle rleqslant m} .

В отличие от обычного биномиального коэффициента, гауссов биномиальный коэффициент имеет конечные значения для m → ∞ {displaystyle m ightarrow infty } (предел имеет аналитический смысл для | q | < 1 {displaystyle |q|<1} ):

( ∞ r ) q = lim m → ∞ ( m r ) q = 1 [ r ] q ! ( 1 − q ) r {displaystyle {infty choose r}_{q}=lim _{m ightarrow infty }{m choose r}_{q}={frac {1}{[r]_{q}!,(1-q)^{r}}}}

Примеры

( 0 0 ) q = ( 1 0 ) q = 1 {displaystyle {0 choose 0}_{q}={1 choose 0}_{q}=1} ( 1 1 ) q = 1 − q 1 − q = 1 {displaystyle {1 choose 1}_{q}={frac {1-q}{1-q}}=1} ( 2 1 ) q = 1 − q 2 1 − q = 1 + q {displaystyle {2 choose 1}_{q}={frac {1-q^{2}}{1-q}}=1+q} ( 3 1 ) q = 1 − q 3 1 − q = 1 + q + q 2 {displaystyle {3 choose 1}_{q}={frac {1-q^{3}}{1-q}}=1+q+q^{2}} ( 3 2 ) q = ( 1 − q 3 ) ( 1 − q 2 ) ( 1 − q ) ( 1 − q 2 ) = 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}} ( 4 2 ) q = ( 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 {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}}

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

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

Слова ( 4 2 ) = 6 {displaystyle {4 choose 2}=6} , использующие нули и единицы, это 0011, 0101, 0110, 1001, 1010, 1100.

Чтобы получить из этой модели гауссов биномиальный коэффициент ( m r ) q {displaystyle { binom {m}{r}}_{q}} , достаточно посчитать каждое слово с множителем qd, где d равно числу «инверсий» в слове — число пар позиций, для которых левая позиция пары равна 1 а правая позиция содержит 0 в слове. Например, существует одно слово с 0 инверсиями, 0011. Есть одно слово с одной инверсией, 0101. Есть два слова с двумя инверсиями, 0110 и 1001. Существует одно слово с тремя инверсиями, 1010, и, наконец, одно слово с четырьмя инверсиями, 1100. Это соответствует коэффициентам в ( 4 2 ) q = 1 + q + 2 q 2 + q 3 + q 4 {displaystyle {4 choose 2}_{q}=1+q+2q^{2}+q^{3}+q^{4}} .

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

Свойства

Подобно обычным биномиальным коэффициентам гауссовы биномиальные коэффициенты контрсимметричны, т.е. инвариантны относительно отражения r → m − r {displaystyle r ightarrow m-r} :

( m r ) q = ( m m − r ) q . {displaystyle {m choose r}_{q}={m choose m-r}_{q}.}

В частности,

( m 0 ) q = ( m m ) q = 1 , {displaystyle {m choose 0}_{q}={m choose m}_{q}=1,,} ( m 1 ) q = ( m m − 1 ) q = 1 − q m 1 − q = 1 + q + ⋯ + q m − 1 m ⩾ 1 . {displaystyle {m choose 1}_{q}={m choose m-1}_{q}={frac {1-q^{m}}{1-q}}=1+q+cdots +q^{m-1}quad mgeqslant 1,.}

Название гауссов биномиальный коэффициент объясняется фактом, что его значение в точке q = 1 {displaystyle q=1} равно

lim q → 1 ( m r ) q = ( m r ) {displaystyle lim _{q o 1}{m choose r}_{q}={m choose r}}

Для всех m и r.

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

( m r ) q = q r ( m − 1 r ) q + ( m − 1 r − 1 ) q {displaystyle {m choose r}_{q}=q^{r}{m-1 choose r}_{q}+{m-1 choose r-1}_{q}}

и

( m r ) q = ( m − 1 r ) q + q m − r ( m − 1 r − 1 ) q . {displaystyle {m choose r}_{q}={m-1 choose r}_{q}+q^{m-r}{m-1 choose r-1}_{q}.}

Есть аналоги биномиальных формул и обобщённые ньютоновы версии их для отрицательных целых степеней, хотя в первом случае гауссовы биномиальные коэффициенты не появляются как коэффициенты:

∏ k = 0 n − 1 ( 1 + q k t ) = ∑ k = 0 n q k ( k − 1 ) / 2 ( n k ) q t k {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}}

и

∏ k = 0 n − 1 1 ( 1 − q k t ) = ∑ k = 0 ∞ ( n + k − 1 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}.}

и при n → ∞ {displaystyle n ightarrow infty } тождества превращаются в

∏ k = 0 ∞ ( 1 + q k t ) = ∑ k = 0 ∞ q k ( k − 1 ) / 2 t k [ k ] q ! ( 1 − q ) k {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}}}}

и

∏ k = 0 ∞ 1 ( 1 − q k t ) = ∑ k = 0 ∞ 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), используя начальные «граничные» значения

( m m ) q = ( m 0 ) q = 1 {displaystyle {m choose m}_{q}={m choose 0}_{q}=1}

И, между прочим, показывает, что гауссовы биномиальные коэффициенты являются реально многочленами (от q). Второе тождество Паскаля следует из первого с помощью подстановки r → m − r {displaystyle r ightarrow m-r} и инвариантности гауссовых биномиальных коэффициентов по отношению к отражению r → m − r {displaystyle r ightarrow m-r} . Из тождеств Паскаля следует

( m r ) q = 1 − q m 1 − q m − r ( m − 1 r ) q {displaystyle {m choose r}_{q}={{1-q^{m}} over {1-q^{m-r}}}{m-1 choose r}_{q}}

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

Приложения

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

( n + m m ) q {displaystyle {n+m choose m}_{q}}

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

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

( n k ) q {displaystyle {n choose k}_{q}}

подсчитывает число k-мерных векторных подпространств n-размерного векторного пространства над Fq (грассманиан). Если разложить в виде многочлена от q, это даёт хорошо известное разложение грассманиана на ячейки Шуберта. Например, гауссов биномиальный коэффициент

( n 1 ) q = 1 + q + q 2 + ⋯ + q n − 1 {displaystyle {n choose 1}_{q}=1+q+q^{2}+cdots +q^{n-1}}

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

Число k-мерных аффинных подпространств Fqn равно

q n − k ( n k ) q {displaystyle q^{n-k}{n choose k}_{q}} .

Это позволяет другую интерпретацию тождества

( m r ) q = ( m − 1 r ) q + q m − r ( m − 1 r − 1 ) 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)-мерными аффинными подпространствами пространства, полученного истолкованием этой фиксированной гиперплоскости как гиперплоскости на бесконечности.

В теории квантовых групп приняты слегка отличные соглашения в определении. Квантовые биномиальные коэффициенты равны

q k 2 − n k ( n k ) q 2 {displaystyle q^{k^{2}-nk}{n choose k}_{q^{2}}} .

Эта версия квантового биномиального коэффициента симметрична относительно q {displaystyle q} и q − 1 {displaystyle q^{-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

Имя:*
E-Mail:
Комментарий: