Личность Вандермонда

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

{m+n \choose r}=\sum _{k=0}^{r}{m \choose k}{n \choose r-k}

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

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

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

{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}}.

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

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

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

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

где мы используем соглашение, согласно которому a _i = 0 для всех целых чисел i > m и b _j = 0 для всех целых чисел j > n . По теореме биномиальной

(1+x)^{m+n}=\sum _{r=0}^{m+n}{m+n \choose r}x^{r}.

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

{\begin{aligned}\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{aligned}}

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

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

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

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

{m+n \choose r}.

Ответ также представляет собой сумму по всем возможным значениям k числа подкомитетов, состоящих из k мужчин и r − k женщин:

\sum _{k=0}^{r}{m \choose k}{n \choose 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}+\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}.

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

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

Личность Чу-Вандермонда

Идентичность обобщается на нецелочисленные аргументы. В этом случае оно известно как тождество Чу–Вандермонда (см. Askey 1975, стр. 59–60 ) и принимает форму

{s+t \choose n}=\sum _{k=0}^{n}{s \choose k}{t \choose n-k}

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

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

(s+t)_{n}=\sum _{k=0}^{n}{n \choose k}(s)_{k}(t)_{n-k}

в какой форме он ясно распознается как теневой вариант биномиальной теоремы (подробнее о теневых вариантах биномиальной теоремы см. Биномиальный тип ). Тождество Чу-Вандермонда также можно рассматривать как частный случай гипергеометрической теоремы Гаусса , которая утверждает, что

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

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

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

либерально.

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

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

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

См. также

Ссылки

^ См. Аски, Ричард (1975), Ортогональные полиномы и специальные функции , Серия региональных конференций по прикладной математике, том. 21, Филадельфия, Пенсильвания: СИАМ, стр. 59–60 по истории.

[1] См. Аски, Ричард (1975), Ортогональные полиномы и специальные функции , Серия региональных конференций по прикладной математике, том. 21, Филадельфия, Пенсильвания: СИАМ, стр. 59–60 по истории.

[1]