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

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

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

,

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

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

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

{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$ обидві сторони тотожності Вандермонда дорівнюють нулю згідно з означенням біноміальних коефіцієнтів.

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

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

Припустимо, комітет складається з $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}.

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

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

Тотожність Вандермонда також виводиться з наступної тотожності^[2] підстановкою $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$ . Це можна довести аналогічно наведеному вище алгебраїчному доказу, перемноживши^[en] біноміальні ряди для $(1+x)^{s}$ та $(1+x)^{t}$ й порівнявши члени з біноміальним рядом для $(1+x)^{s+t}$ .

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

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

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

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

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

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

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

Див. також ред.

Література ред.

↑ Див. Askey, Richard (1975), Orthogonal polynomials and special functions, Regional Conference Series in Applied Mathematics, т. 21, Philadelphia, PA: SIAM, с. 59—60 для історичної довідки.
↑ Arciniega-Nevárez, José Antonio; Bergoff, Marko; Dolores-Cuenca, Eric Rubiel (2023). An algebra over the operad of posets and structural binomial identities. Boletín de la Sociedad Matemática Mexicana. 29. arXiv:2105.06633. doi:10.1007/s40590-022-00478-9. S2CID 246705792.

[1] Див. Askey, Richard (1975), Orthogonal polynomials and special functions, Regional Conference Series in Applied Mathematics, т. 21, Philadelphia, PA: SIAM, с. 59—60 для історичної довідки.

[ANBDC-2] Arciniega-Nevárez, José Antonio; Bergoff, Marko; Dolores-Cuenca, Eric Rubiel (2023). An algebra over the operad of posets and structural binomial identities. Boletín de la Sociedad Matemática Mexicana. 29. arXiv:2105.06633. doi:10.1007/s40590-022-00478-9. S2CID 246705792.

[1]

[2]