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

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

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

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

Існує ${\displaystyle q}$-аналог цієї теореми, що називається ${\displaystyle q}$-тотожністю Вандермонда^[en].

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

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

Доведення

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

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

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

за домовленості, що ${\displaystyle a_{i}=0}$ для будь-яких цілих ${\displaystyle i>m}$ та ${\displaystyle b_{j}=0}$ для будь-яких цілих ${\displaystyle j>n}$.

Згідно з біномом Ньютона,

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

Застосовуючи формулу бінома Ньютона також для степенів ${\displaystyle m}$ та ${\displaystyle n}$, а потім вищезгадану формулу для добутку многочленів, отримуємо

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

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

Порівнюючи коефіцієнти при ${\displaystyle x^{r}}$, отримуємо, що тотожність Вандермонда виконується для всіх цілих цісел ${\displaystyle r}$ таких, що ${\displaystyle 0\leq r\leq m+n}$. Для більших цілих ${\displaystyle r}$ обидві сторони тотожності Вандермонда дорівнюють нулю згідно з означенням біноміальних коефіцієнтів.

Комбінаторне доведення

Тотожність Вандермонда також допускає комбінаторне доведення підрахунком двома способами^[en], як показано нижче.

Припустимо, комітет складається з ${\displaystyle m}$ чоловіків і ${\displaystyle n}$ жінок. Скількома способами можна сформувати підкомітет із ${\displaystyle r}$ членів? Відповідь наступна

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

Відповіддю також є сума по всіх можливих значеннях ${\displaystyle k}$ кількості підкомітетів, що складаються з ${\displaystyle k}$ чоловіків і ${\displaystyle r-k}$ жінок:

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

Геометричне доведення

Розглянемо прямокутну решітку з ${\displaystyle r\times (m+n-r)}$ квадратів. Існує

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

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

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

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

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

Узагальнення

Узагальнена тотожність Вандермонда

Можна узагальнити тотожність Вандермонда наступним чином:

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

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

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

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

${\displaystyle {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) і приймає вигляд

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

для будь-яких загальних комплесних чисел ${\displaystyle s}$ і ${\displaystyle t}$ та невід'ємних цілих ${\displaystyle n}$. Це можна довести аналогічно наведеному вище алгебраїчному доказу, перемноживши біноміальні ряди для ${\displaystyle (1+x)^{s}}$ та ${\displaystyle (1+x)^{t}}$ й порівнявши члени з біноміальним рядом для ${\displaystyle (1+x)^{s+t}}$.

Цю тотожність можна переписати в термінах спадаючих символів Похгамера^[en] наступним чином:

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

У такому вигляді вона впізнається як тіньовий^[en] варіант бінома Ньютона (детальніше про тіньові варіанти бінома Ньютона див. біноміальний тип^[en]). Тотожність Чу–Вандермонда також можна розглядати як частковий випадок гіпергеометричної теореми Гауса, згідно з якою

${\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 a=-n}$ та застосувати тотожність

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

Тотожність Роте–Хагена^[en] є подальшим узагальненням цієї тотожності.

Гіпергеометричний розподіл імовірностей

Якщо обидві частини тотожності поділити на вираз зліва, то отримуємо суму, рівну 1, доданки якої можна інтерпретувати як імовірності. Отриманий розподіл імовірностей є гіпергеометричним розподілом. Це ймовірнісний розподіл числа червоних кульок при виборі ${\displaystyle r}$ кульок без повернення з урни, що містить ${\displaystyle n}$ червоних та ${\displaystyle m}$ блакитних кульок.

Див. також

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