EssayAI
Блог
Блог
Естественные науки

Тождество Вандермонда: формула и доказательство

8 ноября 2026Время чтения: 9 минут
#тождество Вандермонда#сочетания#комбинаторика#биномиальные коэффициенты#дискретная математика
Тождество Вандермонда: формула и доказательство

Тождество Вандермонда позволяет заменить сумму произведений сочетаний одним биномиальным коэффициентом. Его смысл проще формулы: выбрать несколько объектов из двух непересекающихся групп можно сразу из объединения или отдельно подсчитать каждый возможный состав выбора. Оба способа описывают одни и те же наборы. Калькулятор ниже показывает эти составы и проверяет равенство для ваших чисел.

Формула и условия

Для неотрицательных целых mm, nn и rr, где 0≤r≤m+n0 \le r \le m+n, тождество записывается так:

∑k=0r(mk)(nr−k)=(m+nr).\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}.

Здесь (mk)\binom{m}{k} - число способов выбрать kk различных объектов из mm без учёта порядка. Если k>mk>m или k<0k<0, соответствующий коэффициент считают равным нулю. Это соглашение позволяет оставить единые границы суммы: невозможные случаи просто ничего не добавляют. При допустимых kk формула сочетаний имеет вид (mk)=m!/(k!(m−k)!)\binom{m}{k}=m!/(k!(m-k)!). Подробнее о том, почему порядок при таком выборе не важен, рассказано в статье о сочетаниях и перестановках.

Параметр kk означает число выбранных объектов первой группы, а r−kr-k - второй. Справа же группы объединены, и состав выбора заранее не фиксируется. Тождество не требует, чтобы группы были одинакового размера: существенно лишь, чтобы они не пересекались и каждый объект был различим.

Почему два подсчёта дают один ответ

Пусть в первой группе mm человек, во второй nn, а комитет должен состоять из rr человек. Прямой подсчёт даёт (m+nr)\binom{m+n}{r} комитетов. Теперь разделим все комитеты на классы по числу kk представителей первой группы. Каждый комитет попадает ровно в один класс: количество его участников из первой группы определено однозначно.

В классе с данным kk первую часть можно выбрать (mk)\binom{m}{k} способами, а вторую - (nr−k)\binom{n}{r-k} способами. По правилу произведения их дают (mk)(nr−k)\binom{m}{k}\binom{n}{r-k} комитетов. Классы не пересекаются, поэтому их количества складываются. Это применение правила суммы и произведения доказывает тождество без преобразования факториалов.

Для выбора трёх объектов последовательно показаны четыре возможных состава двух групп и число способов для каждого состава; вместе они дают 84 способа.

Движение здесь перебирает именно классы выбора, а не отдельные комитеты: например, число 40 объединяет все выборы с одним объектом первой и двумя объектами второй группы. Поскольку ни один набор не может иметь одновременно один и два объекта из первой группы, двойного счёта нет.

Пример: выбрать три объекта из девяти

Возьмём m=4m=4, n=5n=5 и r=3r=3. Число объектов из первой группы может быть равно 0, 1, 2 или 3. Для каждого случая дополняем выбор до трёх объектами второй группы:

Из первойИз второйВычислениеСпособов
03(40)(53)\binom40\binom5310
12(41)(52)\binom41\binom5240
21(42)(51)\binom42\binom5130
30(43)(50)\binom43\binom504

Сумма равна 10+40+30+4=8410+40+30+4=84. Прямой выбор подтверждает результат: (93)=9⋅8⋅7/(3⋅2⋅1)=84\binom93=9\cdot8\cdot7/(3\cdot2\cdot1)=84. Например, в строке k=1k=1 есть четыре варианта первого объекта и десять вариантов пары из второй группы, всего 4⋅10=404\cdot10=40.

Столбцы числа способов выбрать три объекта: 10, 40, 30 и 4 для разных составов двух групп
Столбцы числа способов выбрать три объекта: 10, 40, 30 и 4 для разных составов двух групп

Высота столбца показывает размер класса, а не вероятность сама по себе. Чтобы получить вероятность при равновероятном выборе тройки, нужно разделить высоту на общее число 84. Первый и последний случаи не обязаны давать одинаковые значения: группы содержат разное число объектов.

Как выбрать границы суммирования

В записи от нуля до rr часть слагаемых может быть нулевой. Если хочется перечислить только возможные случаи, следует учесть сразу четыре ограничения: 0≤k≤m0\le k\le m и 0≤r−k≤n0\le r-k\le n. Отсюда

max⁡(0,r−n)≤k≤min⁡(m,r).\max(0,r-n)\le k\le\min(m,r).

Например, при m=2m=2, n=3n=3 и r=4r=4 в первой группе обязательно выбирают хотя бы один объект, потому что во второй всего три. С другой стороны, взять из первой более двух нельзя. Поэтому остаются k=1k=1 и k=2k=2: (21)(33)+(22)(32)=2+3=5=(54)\binom21\binom33+\binom22\binom32=2+3=5=\binom54.

Крайние случаи тоже работают. При r=0r=0 существует ровно один выбор - пустой набор, и обе стороны равны единице. При r=m+nr=m+n выбираются все объекты, снова одним способом. Если одна группа пуста, ненулевым остаётся лишь тот состав, который целиком помещается в другую группу. Смысл пустого выбора обсуждается также при подсчёте всех подмножеств множества.

Как применять формулу к готовой сумме

Начинайте не с вычисления факториалов, а с чтения индексов. Найдите два верхних числа: они задают размеры групп. Затем сложите нижние индексы внутри произвольного слагаемого. Если результат постоянен при изменении индекса суммирования, он может играть роль общего размера выбора. После этого проверьте границы: каждый возможный состав должен встретиться ровно один раз.

Рассмотрим сумму произведений сочетаний из шести и четырёх объектов, когда всего выбирают пять. В первой группе можно выбрать от одного до пяти объектов: ноль невозможен, потому что во второй группе только четыре. Слагаемое для одного объекта первой группы равно шести, для двух - шестидесяти, для трёх - ста двадцати, для четырёх - шестидесяти, а для пяти - шести. Их сумма равна двумстам пятидесяти двум. По тождеству тот же результат получается сразу как число способов выбрать пять объектов из десяти.

Проверка границ особенно важна для сокращённых сумм. Допустим, в предыдущем примере требуется хотя бы два объекта из первой группы. Тогда первый случай исключён, и ответ получают вычитанием шести из полного числа. Само тождество считает все составы, поэтому дополнительное условие нельзя незаметно отбросить. Аналогично условие «ровно два» оставляет только одно слагаемое, а не всю сумму.

Для программной реализации удобно вычислять сочетания по последовательному произведению, сокращая число множителей с помощью симметрии. При больших размерах целые значения быстро растут: обычного числа с плавающей точкой может не хватить для точного целого ответа. Тогда используют целочисленную арифметику произвольной точности или считают по заданному модулю, учитывая его свойства. Калькулятор выше ограничивает размеры групп двенадцатью объектами, поэтому его результаты остаются точными целыми числами.

Доказательство через коэффициенты многочленов

Есть и алгебраический путь. По биному Ньютона коэффициент при xkx^k в (1+x)m(1+x)^m равен (mk)\binom{m}{k}. Чтобы получить xrx^r при умножении (1+x)m(1+x)n(1+x)^m(1+x)^n, нужно взять xkx^k из первого множителя и xr−kx^{r-k} из второго, а затем сложить вклады всех подходящих kk. Получается левая часть тождества.

Но произведение равно (1+x)m+n(1+x)^{m+n}, где коэффициент при xrx^r равен (m+nr)\binom{m+n}{r}. Коэффициенты одного и того же многочлена совпадают. Этот вывод показывает, что сумма слева - свёртка двух последовательностей биномиальных коэффициентов. Такой язык полезен в алгоритмах работы с производящими функциями: коэффициент произведения собирается из всех пар степеней с нужной суммой.

Сумма квадратов сочетаний

Полезный частный случай получается при m=n=rm=n=r. Тогда (nn−k)=(nk)\binom{n}{n-k}=\binom{n}{k}, поскольку выбор n−kn-k объектов равнозначен выбору kk оставленных. Поэтому

∑k=0n(nk)2=(2nn).\sum_{k=0}^{n}\binom{n}{k}^{2}=\binom{2n}{n}.

Например, при n=3n=3 левая часть равна 1+9+9+1=201+9+9+1=20, как и (63)\binom63. В комбинаторном доказательстве здесь по-прежнему есть две отдельные группы по три объекта. Квадрат возникает благодаря симметрии коэффициентов, а не потому, что один и тот же выбор делают дважды. При вычислении длинной суммы этот частный случай позволяет сразу получить один коэффициент вместо нескольких произведений.

Чтобы распознать формулу в задаче, сначала найдите величину, постоянную во всех слагаемых: сумма нижних индексов двух сочетаний должна быть равна одному и тому же rr. Затем проверьте, что верхние индексы не зависят от kk и что в сумме учтены все допустимые значения. Если эти условия не выполнены, сокращение напрямую может дать неверный ответ. При необходимости сначала используйте симметрию (nj)=(nn−j)\binom{n}{j}=\binom{n}{n-j} и только после этого сравните выражение с формулой.

Вероятность и выбор без возвращения

Пусть четыре шара красные и пять синие, все девять различимы, а тройку выбирают равновероятно без возвращения. Вероятность получить ровно два красных равна

P(K=2)=(42)(51)(93)=3084=514.P(K=2)=\frac{\binom42\binom51}{\binom93}=\frac{30}{84}=\frac5{14}.

Знаменатель считает все тройки, числитель - только подходящие. Значения K=0,1,2,3K=0,1,2,3 исчерпывают возможные исходы, поэтому сумма их вероятностей равна (10+40+30+4)/84=1(10+40+30+4)/84=1. Именно тождество Вандермонда гарантирует такую нормировку для любых допустимых размеров групп. Общий приём подсчёта благоприятных и всех равновозможных исходов разобран в статье о вероятности через сочетания.

Здесь важно условие равновероятности наборов. Если шары выбираются с неодинаковыми весами, сами сочетания по-прежнему считают наборы, но отношение их количества уже не обязательно равно вероятности. Аналогично выбор с возвращением создаёт другую модель: один объект может встретиться более одного раза.

Частые ошибки

  • Складывать числа внутри произведения. Для фиксированного kk независимые выборы из двух групп перемножаются; складываются результаты разных составов.
  • Использовать kk в обоих коэффициентах. Для общей величины rr во второй группе нужно выбрать именно r−kr-k объектов.
  • Считать невозможный выбор отрицательным числом способов. Коэффициент вне допустимого диапазона равен нулю, а факториальная формула в таком виде к нему не применяется.
  • Учитывать порядок комитета. Сочетания считают наборы; если важны роли или последовательность, задача требует другого подсчёта.
  • Путать тождество с определителем Вандермонда. Это разные результаты: определитель встречается, например, при интерполяции Лагранжа.

FAQ

Можно ли применять формулу к группам разных размеров?
Да. mm и nn - любые неотрицательные целые; равенство размеров не требуется.

Почему сумма начинается с нуля?
В выборке может не оказаться объектов первой группы. Если такой состав невозможен, соответствующее слагаемое равно нулю.

Что изменится для трёх групп?
Нужно суммировать произведения трёх сочетаний по всем тройкам чисел выбранных объектов с суммой rr. Результат равен сочетанию из общего размера трёх групп: аргумент о разбиении наборов остаётся прежним.

Коротко

Тождество Вандермонда приравнивает выбор rr объектов из объединения двух групп сумме выборов по всем возможным составам. Оно помогает сокращать комбинаторные суммы, находить коэффициенты произведений и проверять вероятности выборки без возвращения. Границы и нулевые слагаемые обеспечивают учёт только осуществимых вариантов.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Метод шаров и перегородок: формулы и примеры

Метод шаров и перегородок: формулы и примеры

Метод шаров и перегородок помогает считать распределения одинаковых предметов и решения целочисленных уравнений. Разбираем формулы, ограничения и примеры.

8 ноября 20268 минут
Число булевых функций от n переменных: формула

Число булевых функций от n переменных: формула

Сколько существует булевых функций от n переменных и почему ответ равен 2 в степени 2ⁿ? Вывод по таблице истинности, примеры и задачи с ограничениями.

8 ноября 20269 минут
Вероятность через сочетания: формула и разбор

Вероятность через сочетания: формула и разбор

Как считать вероятность через сочетания: классическая формула, число сочетаний в числителе и знаменателе, разбор задач про урну, лотерею и карты с пошаговым решением.

20 июня 20267 минут
Теорема Эрдёша-Ко-Радо: максимум пересекающихся множеств

Теорема Эрдёша-Ко-Радо: максимум пересекающихся множеств

Теорема Эрдёша-Ко-Радо: какое наибольшее семейство k-элементных подмножеств n-множества попарно пересекается, формула C(n-1, k-1), условие n больше или равно 2k и доказательство сдвигом.

19 июня 20266 минут
Декартово произведение множеств: примеры и формула

Декартово произведение множеств: примеры и формула

Декартово произведение множеств: что такое упорядоченная пара, как перечислить все элементы A x B, найти мощность и применить к координатной плоскости - с разбором типовых задач.

11 июня 20268 минут
Правило суммы и произведения в комбинаторике

Правило суммы и произведения в комбинаторике

Правило суммы и произведения в комбинаторике: когда применять каждое правило, как отличить несовместные события от независимых выборов, разбор типовых задач с решением.

11 июня 20267 минут