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

У комбінаториці тотожність Вандермонда (або згортка Вандермонда) — це наступна тотожність для біноміальних коефіцієнтів:

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

де $r$, $m$, $n$ — довільні невід'ємні цілі числа. Тотожність названа на честь Александра-Теофіла Вандермонда (1772), хоча вона була відома ще в 1303 році китайському математику Чжу Шицзе.

Існує $q$-аналог цієї теореми, що називається $q$-тотожністю Вандермонда.

Тотожність Вандермонда можна узагальнити багатьма способами, в тому числі до тотожності

${n_{1}+\dots +n_{p} \choose m}=\sum _{k_{1}+\dots +k_{p}=m}{n_{1} \choose k_{1}}{n_{2} \choose k_{2}}\dots {n_{p} \choose k_{p}}.$

Доведення

Алгебраїчне доведення

У загальному випадку, добуток двох многочленів степенів $m$ та $n$ відповідно визначається як

$\left(\sum _{i=0}^{m}{a_{i}x^{i}}\right)\left(\sum _{j=0}^{n}{b_{j}x^{j}}\right)=\sum _{r=0}^{m+n}{\left(\sum _{k=0}^{r}{a_{k}b_{r-k}}\right){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}=\\&=\left(\sum _{i=0}^{m}{m \choose i}{x^{i}}\right)\left(\sum _{j=0}^{n}{n \choose j}{x^{j}}\right)=\\&=\sum _{r=0}^{m+n}\left(\sum _{k=0}^{r}{m \choose k}{n \choose r-k}\right)x^{r},\end{aligned}}$

де наведена вище домовленість для коефіцієнтів многочленів узгоджується з визначенням біноміальних коефіцієнтів, оскільки і те, і те дає нуль для всіх $i>m$ і $j>n$ відповідно.

Порівнюючи коефіцієнти при $x^{r}$, отримуємо, що тотожність Вандермонда виконується для всіх цілих цісел $r$ таких, що $0\leq r\leq 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\times (m+n-r)$ квадратів. Існує

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

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

Існує ${m \choose k}$ шляхів, що починаються в $(0,0)$ та закінчуються в $(k,m-k)$, оскільки для цього має бути здійнено $k$ рухів вправо та $m-k$ рухів вгору (при цьому довжина шляху рівна $m$). Аналогічно, існує $\displaystyle {n \choose r-k}$ шляхів, що починаються в $(k,m-k)$ та закінчуються в $(r,m+n-r)$, оскільки треба зробити $r-k$ рухів вправо та $(m+n-r)-(m-k)$ рухів вгору, а довжина шляху при цьому рівна $r-k+(m+n-r)-(m-k)=n$. Отже, є

${m \choose k}{n \choose 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}{n_{1} \choose k_{1}}{n_{2} \choose k_{2}}\dots {n_{p} \choose k_{p}}={n_{1}+\dots +n_{p} \choose m}.$

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

З одного боку, обираються $k_{1}$ елементів з першої множини з $n_{1}$ елементів; потім обираються $k_{2}$ елементів з іншої множини, і так далі, для $p$ таких множин, поки не буде вибрано загалом $m$ елементів з $p$ множин. Таким чином, обираються $m$ елементів з $n_{1}+\dots +n_{p}$ в лівій частині тотожності, що в точності відповідає виразу в правій частині.

Тотожність Вандермонда також виводиться з наступної тотожності підстановкою $t=0$. Нехай $p,q,s\leq p+q$. Тоді для $t\leq s$:

${p+q+t \choose s}{s \choose t}=\sum _{a+c=s,n\leq a,r\leq c,n+r=t}{p+n \choose a}{a \choose n}{q+r \choose c}{c \choose r}-\sum _{a+c=s-1,n\leq a,r\leq c,n+r=t-1}{p+n \choose a}{a \choose n}{q+r \choose c}{c \choose r}.$

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

Тотожність можна узагальнити на нецілі аргументи. У цьому випадку вона відома як тотожність Чу–Вандермонда (див. Askey 1975, pp. 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$ блакитних кульок.

Див. також

• Правило Паскаля
• Тотожність хокейної ключки
• Тотожність Роте–Хагена
• Визначник Вандермонда