Русская Википедия:Тождество Вандермонда
Тождество Вандермонда (или свёртка Вандермонда) — это следующее тождество для биномиальных коэффициентов:
- <math>{m+n \choose r}=\sum_{k=0}^r{m \choose k}{n \choose r-k}</math>
для любых неотрицательных целых чисел r, m, n. Тождество названо именем Александра Теофила Вандермонда (1772), хотя оно было известно ещё в 1303 китайскому математику Чжу Шицзе. См. статью Аскея по истории тождестваШаблон:Sfn.
Существует q-аналог этой теоремы, называющийся Шаблон:Не переведено 5.
Тождество Вандермонда можно обобщить множеством способов, включая тождество
- <math>
{ 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>\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>
где используем соглашение, что ai = 0 для всех целых чисел i > m и bj = 0 для всех целых j > n. Согласно биному Ньютона,
- <math>(1+x)^{m+n} = \sum_{r=0}^{m+n} {m+n \choose r}x^r. </math>
Используем формулу бинома Ньютона также для степеней m и n, а затем вышеприведённую формулу для произведения многочленов, получаем
- <math>\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>i > m</math> и <math>j > n</math>.
Сравнивая коэффициенты при xr, получаем тождество Вандермонда для всех целых r с <math>0 \leqslant r \leqslant m + n</math>. Для больших значений r обе стороны тождества Вандермонда равны нулю согласно определению биномиальных коэффициентов.
Комбинаторное доказательство
Тождество Вандермонда допускает также комбинаторное доказательство при помощи Шаблон:Не переведено 5. Предположим, что комитет состоит из m мужчин и n женщин. Сколькими способами можно сформировать подкомитет из r членов? Ответом является
- <math>{m+n \choose r}.</math>
Это число является суммой по всем возможным значениям k числа комитетов, состоящим из k мужчин и <math>r - k</math> женщин:
- <math>\sum_{k=0}^r{m \choose k}{n \choose r-k}.</math>
Геометрическое доказательство
Возьмём прямоугольную решётку из r x (m+n-r) квадратов. Существует
- <math>\binom{r+(m+n-r)}{r}=\binom{m+n}{r}</math>
путей, начинающихся с нижнего левого угла и кончающихся в верхнем правом углу, двигаясь только вправо и вверх (в результате имеем r переходов вправо и m+n-r переходов вверх (или наоборот) в любом порядке, а всего переходов будет m+n). Обозначим нижний левый угол через (0,0).
Существует <math> \binom{m}{k} </math> путей, начинающихся в (0,0) и кончающихся в (k,m-k), поскольку должно быть сделано k правых переходов и m-k переходов вверх (длина пути будет равна m). Аналогично, имеется <math> \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> \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>
\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>.
Это тождество можно получить с помощью алгебраического вывода (как выше) при использовании более двух многочленов, или через обычный Шаблон:Не переведено 5.
С другой стороны, можно выбрать <math>\textstyle k_1</math> элементов из первого множества из <math>\textstyle n_1</math> элементов, затем выбрать <math>\textstyle k_2</math> элементов из другого множества, и так далее, для всех <math>\textstyle p</math> таких множеств, пока не будет выбрано <math>\textstyle m</math> элементов из <math>\textstyle p</math> множеств. Таким образом, выбирается <math>\textstyle m</math> элементов из <math>\textstyle n_1+\dots +n_p</math> в левой части тождества, что в точности совпадает с тем, что делается в правой части.
Тождество Чжу — Вандермонда
Тождество обобщается на нецелочисленные аргументы. В этом случае тождество известно как Тождество Чжу — Вандермонда (см. статью АскеяШаблон:Sfn) и принимает вид
- <math>{s+t \choose n}=\sum_{k=0}^n {s \choose k}{t \choose n-k}</math>
для комплексных чисел s и t общего вида и неотрицательных целых n. Тождество можно доказать по аналогии с доказательством выше с помощью умножения биномиальных рядов для <math>(1+x)^s</math> и <math>(1+x)^t</math> и сравнения членов с биномиальными рядами для <math>(1+x)^{s+t}</math>.
Это тождество можно переписать в терминах убывающих символов Похгаммера
- <math>(s+t)_n = \sum_{k=0}^n {n \choose k} (s)_k (t)_{n-k}</math>
В этом виде тождество ясно распознаётся как теневой вариант бинома Ньютона (о других теневых вариантах бинома Ньютона см. Шаблон:Не переведено 5). Тождество Чжу — Вандермонда можно рассматривать также как частный случай гипергеометрической теоремы Гаусса, которая утверждает, что
- <math>\;_2F_1(a,b;c;1) = \frac{\Gamma(c)\Gamma(c-a-b)}{\Gamma(c-a)\Gamma(c-b)}</math>
где <math>\;_2F_1</math> — гипергеометрическая функция, а <math>\Gamma(n+1)=n!</math> — гамма-функция. Если взять в тождестве Чжу — Вандермонда a = −n, получим
- <math>{n\choose k} = (-1)^k {k-n-1 \choose k}</math>.
Шаблон:Не переведено 5 является дальнейшим обобщением данного тождества.
Гипергеометрическое распределение вероятности
Если обе части тождества разделить на выражение слева, то сумма станет равной 1 и члены можно интерпретировать как вероятности. Получающееся распределение вероятностей называется гипергеометрическим распределением. Это распределение соответствует распределению вероятности числа красных шаров при выборке (без возвращения) r шаров из урны, содержащей n красных и m синих шаров.
См. также
Примечания
Литература
