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

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

(\binom{m + n}{r}) = \sum_{k = 0}^{r} (\binom{m}{k}) (\binom{n}{r - k})

,

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

Існує $q$ -аналог цієї теореми, що називається Шаблон:Нп.

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

(\binom{n_{1} + \dots + n_{p}}{m}) = \sum_{k_{1} + \dots + k_{p} = m} (\binom{n_{1}}{k_{1}}) (\binom{n_{2}}{k_{2}}) \dots (\binom{n_{p}}{k_{p}}) .

Доведення

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

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

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

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

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

(1 + x)^{m + n} = \sum_{r = 0}^{m + n} (\binom{m + n}{r}) x^{r} .

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

\begin{matrix} \sum_{r = 0}^{m + n} (\binom{m + n}{r}) x^{r} & = (1 + x)^{m + n} = \\ = (1 + x)^{m} (1 + x)^{n} = \\ = (\sum_{i = 0}^{m} (\binom{m}{i}) x^{i}) (\sum_{j = 0}^{n} (\binom{n}{j}) x^{j}) = \\ = \sum_{r = 0}^{m + n} (\sum_{k = 0}^{r} (\binom{m}{k}) (\binom{n}{r - k})) x^{r}, \end{matrix}

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

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

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

Тотожність Вандермонда також допускає комбінаторне доведення Шаблон:Нп, як показано нижче.

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

(\binom{m + n}{r}) .

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

\sum_{k = 0}^{r} (\binom{m}{k}) (\binom{n}{r - k}) .

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

Розглянемо прямокутну решітку з $r \times (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} + \dots + k_{p} = m} (\binom{n_{1}}{k_{1}}) (\binom{n_{2}}{k_{2}}) \dots (\binom{n_{p}}{k_{p}}) = (\binom{n_{1} + \dots + n_{p}}{m}) .

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

З одного боку, обираються $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$ :

(\binom{p + q + t}{s}) (\binom{s}{t}) = \sum_{a + c = s, n \leq a, r \leq c, n + r = t} (\binom{p + n}{a}) (\binom{a}{n}) (\binom{q + r}{c}) (\binom{c}{r}) - \sum_{a + c = s - 1, n \leq a, r \leq c, n + r = t - 1} (\binom{p + n}{a}) (\binom{a}{n}) (\binom{q + r}{c}) (\binom{c}{r}) .

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

Тотожність можна узагальнити на нецілі аргументи. У цьому випадку вона відома як тотожність Чу–Вандермонда (див. Askey 1975, pp. 59–60) і приймає вигляд

(\binom{s + t}{n}) = \sum_{k = 0}^{n} (\binom{s}{k}) (\binom{t}{n - k})

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

Цю тотожність можна переписати в термінах спадаючих Шаблон:Нп наступним чином:

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

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

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

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

(\binom{n}{k}) = (- 1)^{k} (\binom{k - n - 1}{k}) .

Шаблон:Нп є подальшим узагальненням цієї тотожності.

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

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

Див. також

Література

Шаблон:Reflist

↑ Див. Шаблон:Citation для історичної довідки.
↑ Шаблон:Cite journal

[1] Див. Шаблон:Citation для історичної довідки.

[ANBDC-2] Шаблон:Cite journal

[1]

[2]

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

Зміст

Доведення

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

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

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

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

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

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

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

Див. також

Література

Навігаційне меню

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

Доведення

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

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

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

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

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

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

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

Див. також

Література

Навігаційне меню

Пошук