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

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

(\binom{m + n}{r}) = \sum_{k = 0}^{r} (\binom{m}{k}) (\binom{n}{r - k})

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

Существует q-аналог этой теоремы, называющийся Шаблон:Не переведено 5.

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

(\binom{n_{1} + \dots + n_{p}}{m}) = \sum_{k_{1} + \dots + k_{p} = m} (\binom{n_{1}}{k_{1}}) (\binom{n_{2}}{k_{2}}) \dots (\binom{n_{p}}{k_{p}})

.

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

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

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

(\sum_{i = 0}^{m} a_{i} x^{i}) (\sum_{j = 0}^{n} b_{j} x^{j}) = \sum_{r = 0}^{m + n} (\sum_{k = 0}^{r} a_{k} b_{r - k}) x^{r},

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

(1 + x)^{m + n} = \sum_{r = 0}^{m + n} (\binom{m + n}{r}) x^{r} .

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

\begin{matrix} \sum_{r = 0}^{m + n} (\binom{m + n}{r}) x^{r} & = (1 + x)^{m + n} \\ = (1 + x)^{m} (1 + x)^{n} \\ = (\sum_{i = 0}^{m} (\binom{m}{i}) x^{i}) (\sum_{j = 0}^{n} (\binom{n}{j}) x^{j}) \\ = \sum_{r = 0}^{m + n} (\sum_{k = 0}^{r} (\binom{m}{k}) (\binom{n}{r - k})) x^{r}, \end{matrix}

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

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

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

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

(\binom{m + n}{r}) .

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

\sum_{k = 0}^{r} (\binom{m}{k}) (\binom{n}{r - k}) .

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

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

(\binom{r + (m + n - r)}{r}) = (\binom{m + n}{r})

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

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

(\binom{m}{k}) (\binom{n}{r - k})

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

Обобщения

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

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

\sum_{k_{1} + \dots + k_{p} = m} (\binom{n_{1}}{k_{1}}) (\binom{n_{2}}{k_{2}}) \dots (\binom{n_{p}}{k_{p}}) = (\binom{n_{1} + \dots + n_{p}}{m})

.

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

С другой стороны, можно выбрать $k_{1}$ элементов из первого множества из $n_{1}$ элементов, затем выбрать $k_{2}$ элементов из другого множества, и так далее, для всех $p$ таких множеств, пока не будет выбрано $m$ элементов из $p$ множеств. Таким образом, выбирается $m$ элементов из $n_{1} + \dots + n_{p}$ в левой части тождества, что в точности совпадает с тем, что делается в правой части.

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

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

(\binom{s + t}{n}) = \sum_{k = 0}^{n} (\binom{s}{k}) (\binom{t}{n - k})

для комплексных чисел s и t общего вида и неотрицательных целых n. Тождество можно доказать по аналогии с доказательством выше с помощью Шаблон:Iw биномиальных рядов для $(1 + x)^{s}$ и $(1 + x)^{t}$ и сравнения членов с биномиальными рядами для $(1 + x)^{s + t}$ .

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

(s + t)_{n} = \sum_{k = 0}^{n} (\binom{n}{k}) (s)_{k} (t)_{n - k}

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

_{2} F_{1} (a, b; c; 1) = \frac{Γ (c) Γ (c - a - b)}{Γ (c - a) Γ (c - b)}

где $_{2} F_{1}$ — гипергеометрическая функция, а $Γ (n + 1) = n!$ — гамма-функция. Если взять в тождестве Чжу — Вандермонда a = −n, получим

(\binom{n}{k}) = (- 1)^{k} (\binom{k - n - 1}{k})

.

Шаблон:Не переведено 5 является дальнейшим обобщением данного тождества.

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

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

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Книга

Шаблон:Refend Шаблон:Rq

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

Содержание

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

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

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

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

Обобщения

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

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

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

См. также

Примечания

Литература

Навигация

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

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

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

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

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

Обобщения

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

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

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

См. также

Примечания

Литература

Навигация

Поиск