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

Тождество Вандермонда (или свёртка Вандермонда ) — это следующее тождество для биномиальных коэффициентов :

{m+n \choose r}=\sum _{k=0}^{r}{m \choose k}{n \choose r-k}

{m+n \choose r}=\sum _{k=0}^{r}{m \choose k}{n \choose r-k}

для любых неотрицательных целых чисел r , m , n . Тождество названо именем Александра Теофила Вандермонда (1772), хотя оно было известно ещё в 1303 китайскому математику Чжу Шицзе . См. статью Аскея по истории тождества .

Существует q -аналог этой теоремы, называющийся .

Тождество Вандермонда можно обобщить множеством способов, включая тождество

{n_{1}+\dots +n_{p} \choose m}=\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}=\sum _{k_{1}+\cdots +k_{p}=m}{n_{1} \choose k_{1}}{n_{2} \choose k_{2}}\cdots {n_{p} \choose k_{p}}

.

Доказательства

Алгебраическое доказательство

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

{\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},

{\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 . Согласно биному Ньютона ,

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

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

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

{\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}}

{\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}}

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

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

Комбинаторное доказательство

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

{m+n \choose r}.

{m+n \choose r}.

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

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

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

Геометрическое доказательство

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

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

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

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

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

{\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}+\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}

\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}

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

Гипергеометрическое распределение вероятности

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

См. также

Правило Паскаля

Примечания

↑ , с. 59-60.

Литература

Richard Askey . Orthogonal polynomials and special functions. — Philadelphia, PA: SIAM, 1975. — Т. 21. — С. viii+110. — (Regional Conference Series in Applied Mathematics).