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

Выражение для специального определителя см. Матрица Вандермонда.

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

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

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

Существует q-аналог к этой теореме, названной q-Vandermonde личность.

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

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

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

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

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

${\displaystyle {\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},}$

где мы используем соглашение, что а_я = 0 для всех целых чисел я > м и б_j = 0 для всех целых чисел j > п. Посредством биномиальная теорема,

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

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

${\displaystyle {\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}}}$

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

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

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

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

${\displaystyle {m+n \choose r}.}$

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

${\displaystyle \sum _{k=0}^{r}{m \choose k}{n \choose r-k}.}$

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

Возьмите прямоугольную сетку из р Икс (м+п−р) квадраты. Есть

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

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

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

${\displaystyle {\binom {m}{k}}{\binom {n}{r-k}}}$

пути, которые начинаются в (0, 0), заканчиваются в (р, м+п−р) и пройти через (k, м−k). Это подмножество всех путей, которые начинаются в (0, 0) и заканчиваются в (р, м+п−р), поэтому сумма от k = От 0 до k = р (как точка (k, м−k) ограничен квадратом), чтобы получить общее количество путей, которые начинаются в (0, 0) и заканчиваются в (р, м+п−р).

Обобщения

Обобщенная личность Вандермонда

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

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

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

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

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

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

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

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

Эта идентичность может быть переписана в терминах падения Символы Почхаммера в качестве

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

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

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

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

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

щедро.

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

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

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

Смотрите также

• Личность Паскаля
• Хоккейная клюшка
• Идентичность Рот-Хагена

Рекомендации

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