У комбінаториці тотожність Вандермонда (або згортка Вандермонда) — це наступна тотожність для біноміальних коефіцієнтів:
,
де , , — довільні невід'ємні цілі числа. Тотожність названа на честь Александра-Теофіла Вандермонда (1772), хоча вона була відома ще в 1303 році китайському математику Чжу Шицзе.Див. для історичної довідки.
Існує -аналог цієї теореми, що називається .
Тотожність Вандермонда можна узагальнити багатьма способами, в тому числі до тотожності
Доведення Алгебраїчне доведення У загальному випадку, добуток двох многочленів степенів та відповідно визначається як
за домовленості, що для будь-яких цілих та для будь-яких цілих .
Згідно з біномом Ньютона,
Застосовуючи формулу бінома Ньютона також для степенів та , а потім вищезгадану формулу для добутку многочленів, отримуємо
де наведена вище домовленість для коефіцієнтів многочленів узгоджується з визначенням біноміальних коефіцієнтів, оскільки і те, і те дає нуль для всіх і відповідно.
Порівнюючи коефіцієнти при , отримуємо, що тотожність Вандермонда виконується для всіх цілих цісел таких, що . Для більших цілих обидві сторони тотожності Вандермонда дорівнюють нулю згідно з означенням біноміальних коефіцієнтів.
Комбінаторне доведення Тотожність Вандермонда також допускає комбінаторне доведення , як показано нижче.
Припустимо, комітет складається з чоловіків і жінок. Скількома способами можна сформувати підкомітет із членів? Відповідь наступна
Відповіддю також є сума по всіх можливих значеннях кількості підкомітетів, що складаються з чоловіків і жінок:
Геометричне доведення Розглянемо прямокутну решітку з квадратів. Існує
шляхів, що починаються з нижньої лівої вершини та, рухаючись лише вгору або вправо, закінчуються у верхній правій вершині (оскільки має бути здійснено рухів праворуч та рухів вгору (або навпаки) в будь-якому порядку, а загальна довжина шляху становить ). Позначимо нижню ліву вершину через .
Існує шляхів, що починаються в та закінчуються в , оскільки для цього має бути здійнено рухів вправо та рухів вгору (при цьому довжина шляху рівна ). Аналогічно, існує шляхів, що починаються в та закінчуються в , оскільки треба зробити рухів вправо та рухів вгору, а довжина шляху при цьому рівна . Отже, є
шляхів, що починаються в вершині , закінчуюються в та проходять через . Це підмножина всіх шляхів, які починаються в і закінчуються в , тому залишається просумувати від до (оскільки точка має належати прямокутнику), щоб отримати загальну кількість шляхів, які починаються в і закінчуються в .
Узагальнення Узагальнена тотожність Вандермонда Можна узагальнити тотожність Вандермонда наступним чином:
Цю тотожність можна отримати за допомогою наведеного вище алгебраїчного виведення з використанням більше двох многочленів, або за допомогою простого .
З одного боку, обираються елементів з першої множини з елементів; потім обираються елементів з іншої множини, і так далі, для таких множин, поки не буде вибрано загалом елементів з множин. Таким чином, обираються елементів з в лівій частині тотожності, що в точності відповідає виразу в правій частині.
Тотожність Вандермонда також виводиться з наступної тотожності підстановкою . Нехай . Тоді для :
Тотожність Чу–Вандермонда Тотожність можна узагальнити на нецілі аргументи. У цьому випадку вона відома як тотожність Чу–Вандермонда (див. Askey 1975, pp. 59–60) і приймає вигляд
для будь-яких загальних комплексних чисел і та невід'ємних цілих . Це можна довести аналогічно наведеному вище алгебраїчному доказу, перемноживши біноміальні ряди для та й порівнявши члени з біноміальним рядом для .
Цю тотожність можна переписати в термінах спадаючих наступним чином:
У такому вигляді вона впізнається як варіант бінома Ньютона (детальніше про тіньові варіанти бінома Ньютона див. ). Тотожність Чу–Вандермонда також можна розглядати як частковий випадок гіпергеометричної теореми Гауса, згідно з якою
де — гіпергеометрична функція, а — гамма-функція. Тотожність Чу–Вандермонда отримується, якщо взяти та застосувати тотожність
є подальшим узагальненням цієї тотожності.
Гіпергеометричний розподіл імовірностей Якщо обидві частини тотожності поділити на вираз зліва, то отримуємо суму, рівну 1, доданки якої можна інтерпретувати як імовірності. Отриманий розподіл імовірностей є гіпергеометричним розподілом. Це ймовірнісний розподіл числа червоних кульок при виборі кульок без повернення з урни, що містить червоних та блакитних кульок.
Див. також Правило Паскаля
Визначник Вандермонда Література