Тождество Вандермонда (Mk';yvmfk Fgu;yjbku;g)

Перейти к навигации Перейти к поиску

Тождество Вандермонда (или свёртка Вандермонда) — это следующее тождество для биномиальных коэффициентов:

для любых неотрицательных целых чисел r, m, n. Тождество названо именем Александра Теофила Вандермонда (1772), хотя оно было известно ещё в 1303 китайскому математику Чжу Шицзе. См. статью Аскея по истории тождества[1].

Существует q-аналог этой теоремы, называющийся q-тождеством Вандермонда[англ.].

Тождество Вандермонда можно обобщить множеством способов, включая тождество

.

Доказательства

[править | править код]

Алгебраическое доказательство

[править | править код]

В общем случае для произведения двух многочленов степеней m и n имеет место формула

где используем соглашение, что ai = 0 для всех целых чисел i > m и bj = 0 для всех целых j > n. Согласно биному Ньютона,

Используем формулу бинома Ньютона также для степеней m и n, а затем вышеприведённую формулу для произведения многочленов, получаем

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

Сравнивая коэффициенты при xr, получаем тождество Вандермонда для всех целых r с . Для больших значений r обе стороны тождества Вандермонда равны нулю согласно определению биномиальных коэффициентов.

Комбинаторное доказательство

[править | править код]

Тождество Вандермонда допускает также комбинаторное доказательство при помощи двойного подсчёта. Предположим, что комитет состоит из m мужчин и n женщин. Сколькими способами можно сформировать подкомитет из r членов? Ответом является

Это число является суммой по всем возможным значениям k числа комитетов, состоящим из k мужчин и женщин:

Геометрическое доказательство

[править | править код]

Возьмём прямоугольную решётку из r x (m+n-r) квадратов. Существует

путей, начинающихся с нижнего левого угла и кончающихся в верхнем правом углу, двигаясь только вправо и вверх (в результате имеем r переходов вправо и m+n-r переходов вверх (или наоборот) в любом порядке, а всего переходов будет m+n). Обозначим нижний левый угол через (0,0).

Существует путей, начинающихся в (0,0) и кончающихся в (k,m-k), поскольку должно быть сделано k правых переходов и m-k переходов вверх (длина пути будет равна m). Аналогично, имеется путей, начинающихся в (k,m-k) и кончающихся в (r,m+n-r), как результат r-k переходов вправо и (m+n-r)-(m-k) движений вверх, длина пути будет равна r-k + (m+n-r)-(m-k) = n. Таким образом, имеется

Путей, начинающихся в (0,0), кончающихся в (r, m+n-r) и проходящих через (k, m-k). Этот набор путей является подмножеством всех путей, начинающихся в (0,0) и заканчивающихся в (r, m+n-r), так что сумма от k=0 до k=r (поскольку точка (k, m-k) должна лежать внутри прямоугольника) даст полное число путей, начинающихся в (0,0) и завершающихся в (r, m+n-r).

Обобщённое тождество Вандермонда

[править | править код]

Можно обобщить тождество Вандермонда следующим образом:

.

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

С другой стороны, можно выбрать элементов из первого множества из элементов, затем выбрать элементов из другого множества, и так далее, для всех таких множеств, пока не будет выбрано элементов из множеств. Таким образом, выбирается элементов из в левой части тождества, что в точности совпадает с тем, что делается в правой части.

Тождество Чжу — Вандермонда

[править | править код]

Тождество обобщается на нецелочисленные аргументы. В этом случае тождество известно как Тождество Чжу — Вандермонда (см. статью Аскея[1]) и принимает вид

для комплексных чисел s и t общего вида и неотрицательных целых n. Тождество можно доказать по аналогии с доказательством выше с помощью умножения[англ.] биномиальных рядов для и и сравнения членов с биномиальными рядами для .

Это тождество можно переписать в терминах убывающих символов Похгаммера

В этом виде тождество ясно распознаётся как теневой вариант бинома Ньютона (о других теневых вариантах бинома Ньютона см. Последовательность многочленов биномиального типа[англ.]). Тождество Чжу — Вандермонда можно рассматривать также как частный случай гипергеометрической теоремы Гаусса, которая утверждает, что

где гипергеометрическая функция, а гамма-функция. Если взять в тождестве Чжу — Вандермонда a = −n, получим

.

Тождество Роте — Хагена[англ.] является дальнейшим обобщением данного тождества.

Гипергеометрическое распределение вероятности

[править | править код]

Если обе части тождества разделить на выражение слева, то сумма станет равной 1 и члены можно интерпретировать как вероятности. Получающееся распределение вероятностей называется гипергеометрическим распределением. Это распределение соответствует распределению вероятности числа красных шаров при выборке (без возвращения) r шаров из урны, содержащей n красных и m синих шаров.

Примечания

[править | править код]
  1. 1 2 Askey, 1975, с. 59-60.

Литература

[править | править код]
  • Richard Askey. Orthogonal polynomials and special functions. — Philadelphia, PA: SIAM, 1975. — Т. 21. — С. viii+110. — (Regional Conference Series in Applied Mathematics).