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

В общем случае для произведения двух многочленов степеней m и n имеет место формула

${\displaystyle {\biggl (}\sum _{i=0}^{m}a_{i}x^{i}{\biggr )}{\biggl (}\sum _{j=0}^{n}b_{j}x^{j}{\biggr )}=\sum _{r=0}^{m+n}{\biggl (}\sum _{k=0}^{r}a_{k}b_{r-k}{\biggr )}x^{r},}$

где используем соглашение, что a_i = 0 для всех целых чисел i > m и b_j = 0 для всех целых j > n. Согласно биному Ньютона,

${\displaystyle (1+x)^{m+n}=\sum _{r=0}^{m+n}{m+n \choose r}x^{r}.}$

Используем формулу бинома Ньютона также для степеней m и n, а затем вышеприведённую формулу для произведения многочленов, получаем

${\displaystyle {\begin{aligned}\sum _{r=0}^{m+n}{m+n \choose r}x^{r}&=(1+x)^{m+n}\\&=(1+x)^{m}(1+x)^{n}\\&={\biggl (}\sum _{i=0}^{m}{m \choose i}x^{i}{\biggr )}{\biggl (}\sum _{j=0}^{n}{n \choose j}x^{j}{\biggr )}\\&=\sum _{r=0}^{m+n}{\biggl (}\sum _{k=0}^{r}{m \choose k}{n \choose r-k}{\biggr )}x^{r},\end{aligned}}}$

где вышеупомянутые соглашения о коэффициентах многочленов согласуются с определением биномиальных коэффициентов, поскольку дают нуль для всех ${\displaystyle i>m}$ и ${\displaystyle j>n}$.

Сравнивая коэффициенты при x^r, получаем тождество Вандермонда для всех целых r с ${\displaystyle 0\leqslant r\leqslant m+n}$. Для больших значений r обе стороны тождества Вандермонда равны нулю согласно определению биномиальных коэффициентов.

Тождество Вандермонда допускает также комбинаторное доказательство при помощи двойного подсчёта. Предположим, что комитет состоит из m мужчин и n женщин. Сколькими способами можно сформировать подкомитет из r членов? Ответом является

${\displaystyle {m+n \choose r}.}$

Это число является суммой по всем возможным значениям k числа комитетов, состоящим из k мужчин и ${\displaystyle r-k}$ женщин:

${\displaystyle \sum _{k=0}^{r}{m \choose k}{n \choose r-k}.}$

Возьмём прямоугольную решётку из r x (m+n-r) квадратов. Существует

${\displaystyle {\binom {r+(m+n-r)}{r}}={\binom {m+n}{r}}}$

путей, начинающихся с нижнего левого угла и кончающихся в верхнем правом углу, двигаясь только вправо и вверх (в результате имеем r переходов вправо и m+n-r переходов вверх (или наоборот) в любом порядке, а всего переходов будет m+n). Обозначим нижний левый угол через (0,0).

Существует ${\displaystyle {\binom {m}{k}}}$ путей, начинающихся в (0,0) и кончающихся в (k,m-k), поскольку должно быть сделано k правых переходов и m-k переходов вверх (длина пути будет равна m). Аналогично, имеется ${\displaystyle {\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. Таким образом, имеется

${\displaystyle {\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).

Можно обобщить тождество Вандермонда следующим образом:

${\displaystyle \sum _{k_{1}+\cdots +k_{p}=m}{n_{1} \choose k_{1}}{n_{2} \choose k_{2}}\cdots {n_{p} \choose k_{p}}={n_{1}+\dots +n_{p} \choose m}}$.

Это тождество можно получить с помощью алгебраического вывода (как выше) при использовании более двух многочленов, или через обычный двойной подсчёт.

С другой стороны, можно выбрать ${\displaystyle \textstyle k_{1}}$ элементов из первого множества из ${\displaystyle \textstyle n_{1}}$ элементов, затем выбрать ${\displaystyle \textstyle k_{2}}$ элементов из другого множества, и так далее, для всех ${\displaystyle \textstyle p}$ таких множеств, пока не будет выбрано ${\displaystyle \textstyle m}$ элементов из ${\displaystyle \textstyle p}$ множеств. Таким образом, выбирается ${\displaystyle \textstyle m}$ элементов из ${\displaystyle \textstyle n_{1}+\dots +n_{p}}$ в левой части тождества, что в точности совпадает с тем, что делается в правой части.

Тождество обобщается на нецелочисленные аргументы. В этом случае тождество известно как Тождество Чжу — Вандермонда (см. статью Аскея[1]) и принимает вид

${\displaystyle {s+t \choose n}=\sum _{k=0}^{n}{s \choose k}{t \choose n-k}}$

для комплексных чисел s и t общего вида и неотрицательных целых n. Тождество можно доказать по аналогии с доказательством выше с помощью умножения биномиальных рядов для ${\displaystyle (1+x)^{s}}$ и ${\displaystyle (1+x)^{t}}$ и сравнения членов с биномиальными рядами для ${\displaystyle (1+x)^{s+t}}$.

Это тождество можно переписать в терминах убывающих символов Похгаммера

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

В этом виде тождество ясно распознаётся как теневой вариант бинома Ньютона (о других теневых вариантах бинома Ньютона см. Последовательность многочленов биномиального типа). Тождество Чжу — Вандермонда можно рассматривать также как частный случай гипергеометрической теоремы Гаусса, которая утверждает, что

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

где ${\displaystyle \;_{2}F_{1}}$ — гипергеометрическая функция, а ${\displaystyle \Gamma (n+1)=n!}$ — гамма-функция. Если взять в тождестве Чжу — Вандермонда a = −n, получим

${\displaystyle {n \choose k}=(-1)^{k}{k-n-1 \choose k}}$.

Тождество Роте — Хагена является дальнейшим обобщением данного тождества.