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

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

[math]\displaystyle{ {m+n \choose r}=\sum_{k=0}^r{m \choose k}{n \choose r-k} }[/math]

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

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

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

[math]\displaystyle{ { n_1+\dots +n_p \choose m }= \sum_{k_1+\cdots +k_p = m} {n_1\choose k_1} {n_2\choose k_2} \cdots {n_p\choose k_p} }[/math].

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

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

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

[math]\displaystyle{ \biggl(\sum_{i=0}^m a_ix^i\biggr) \biggl(\sum_{j=0}^n b_jx^j\biggr) = \sum_{r=0}^{m+n}\biggl(\sum_{k=0}^r a_k b_{r-k}\biggr) x^r, }[/math]

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

[math]\displaystyle{ (1+x)^{m+n} = \sum_{r=0}^{m+n} {m+n \choose r}x^r. }[/math]

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

[math]\displaystyle{ \begin{align} \sum_{r=0}^{m+n} {m+n \choose r}x^r &= (1+x)^{m+n}\\ &= (1+x)^m (1+x)^n \\ &= \biggl(\sum_{i=0}^m {m\choose i}x^i\biggr) \biggl(\sum_{j=0}^n {n\choose j}x^j\biggr)\\ &=\sum_{r=0}^{m+n}\biggl(\sum_{k=0}^r {m\choose k} {n\choose r-k}\biggr) x^r, \end{align} }[/math]

где вышеупомянутые соглашения о коэффициентах многочленов согласуются с определением биномиальных коэффициентов, поскольку дают нуль для всех [math]\displaystyle{ i \gt m }[/math] и [math]\displaystyle{ j \gt n }[/math].

Сравнивая коэффициенты при x^r, получаем тождество Вандермонда для всех целых r с [math]\displaystyle{ 0 \leqslant r \leqslant m + n }[/math]. Для больших значений r обе стороны тождества Вандермонда равны нулю согласно определению биномиальных коэффициентов.

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

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

[math]\displaystyle{ {m+n \choose r}. }[/math]

Это число является суммой по всем возможным значениям k числа комитетов, состоящим из k мужчин и [math]\displaystyle{ r - k }[/math] женщин:

[math]\displaystyle{ \sum_{k=0}^r{m \choose k}{n \choose r-k}. }[/math]

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

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

[math]\displaystyle{ \binom{r+(m+n-r)}{r}=\binom{m+n}{r} }[/math]

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

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

[math]\displaystyle{ \binom{m}{k}\binom{n}{r-k} }[/math]

Путей, начинающихся в (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).

Обобщения

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

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

[math]\displaystyle{ \sum_{k_1+\cdots +k_p = m} {n_1\choose k_1} {n_2\choose k_2} \cdots {n_p\choose k_p} = { n_1+\dots +n_p \choose m } }[/math].

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

С другой стороны, можно выбрать [math]\displaystyle{ \textstyle k_1 }[/math] элементов из первого множества из [math]\displaystyle{ \textstyle n_1 }[/math] элементов, затем выбрать [math]\displaystyle{ \textstyle k_2 }[/math] элементов из другого множества, и так далее, для всех [math]\displaystyle{ \textstyle p }[/math] таких множеств, пока не будет выбрано [math]\displaystyle{ \textstyle m }[/math] элементов из [math]\displaystyle{ \textstyle p }[/math] множеств. Таким образом, выбирается [math]\displaystyle{ \textstyle m }[/math] элементов из [math]\displaystyle{ \textstyle n_1+\dots +n_p }[/math] в левой части тождества, что в точности совпадает с тем, что делается в правой части.

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

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

[math]\displaystyle{ {s+t \choose n}=\sum_{k=0}^n {s \choose k}{t \choose n-k} }[/math]

для комплексных чисел s и t общего вида и неотрицательных целых n. Тождество можно доказать по аналогии с доказательством выше с помощью умножения биномиальных рядов для [math]\displaystyle{ (1+x)^s }[/math] и [math]\displaystyle{ (1+x)^t }[/math] и сравнения членов с биномиальными рядами для [math]\displaystyle{ (1+x)^{s+t} }[/math].

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

[math]\displaystyle{ (s+t)_n = \sum_{k=0}^n {n \choose k} (s)_k (t)_{n-k} }[/math]

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

[math]\displaystyle{ \;_2F_1(a,b;c;1) = \frac{\Gamma(c)\Gamma(c-a-b)}{\Gamma(c-a)\Gamma(c-b)} }[/math]

где [math]\displaystyle{ \;_2F_1 }[/math] — гипергеометрическая функция, а [math]\displaystyle{ \Gamma(n+1)=n! }[/math] — гамма-функция. Если взять в тождестве Чжу — Вандермонда a = −n, получим

[math]\displaystyle{ {n\choose k} = (-1)^k {k-n-1 \choose k} }[/math].

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

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

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

См. также

• Правило Паскаля
• Тождество клюшки
• Тождество Роте — Хагена