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