Комбинаторное тождество

[Asker Tasker]

Требуется доказать равенство: $\sum_{k = 0}^{n}\left ( C_{n}^{k} \right )^{2}=C_{2n}^{~n} $

Верно ли следующее доказательство?

Пусть $X$ - конечное множество: $X=\left \{ x_{i} \right \}_{i=1}^{2n}$. Положим $X_{1} = \left \{ x_{1}, ..., x_{n} \right \}$, $X_{2} = \left \{ x_{n+1}, ..., x_{2n} \right \}$.
Если $A \subseteq X$ состоит из n элементов, то $A = \left ( X \bigcap X_{1} \right ) \bigcup \left ( X \bigcap X_{2} \right )$. Обозначим мощность множества $\left ( X \bigcap X_{1} \right )$ через $k$: $\left |X \bigcap X_{1} \right | = k$, тогда, очевидно, $\left |X \bigcap X_{2} \right | = n - k$, то есть каждому n-элементному подмножеству множества $X$ ставится в однозначое соответствие $k$ элементов множества $X_{1}$ и $n-k$ элементов множества $X_{2}$.

С другой стороны, пусть задано $k$ элементов множества $X_{1}$ и $n-k$ элементов множества $X_{2}$. Тогда им в однозначное соответствие ставится некоторое множество $A$, являющееся объединением этих элементов и, очевидно, являющееся n-элементным подмножеством множества $X$. Из выше сказанного имеем отображение пар множеств $\left( X_{1}^{k}, X_{2}^{n-k} \right)$ (которые образуются как указано выше) на множество всех n-элементных подмножеств множества $X$, причём любым двум различным парам $\left( X_{1}^{k}, X_{2}^{n-k} \right)$ соответствуют разные множества $A$ (если изменить k или при фиксированном k выбрать элементы во множестве $X_{1}$ и/или во множестве $X_{2}$ разными способами, то объединение этих наборов будет отличаться от исходного), то есть отображение взаимно однозначное. Значит, общее количество таких пар совпадает с общим количеством n-элементных подмножеств множества $X$, то есть равно $C_{2n}^{n}$.

Посчитаем общее число пар указанного вида: при фиксированном k множество $X_{1}^{k}$ можно выбрать $C_{n}^{k}$ способами, а множество $X_{2}^{n-k}$ - $C_{n}^{n-k}$ способами. Соответственно пару $\left( X_{1}^{k}, X_{2}^{n-k} \right)$ можно выбрать $N\left ( k \right ) = C_{n}^{k}\cdot C_{n}^{n-k} = C_{n}^{k}\cdot C_{n}^{k} = \left ( C_{n}^{k} \right )^{2}$способами, причём, очевидно, $0\leq k\leq n$. Из выше сказанного следует, что мощность множества пар указанного вида равна $\sum_{k=0}^{n}N\left ( k \right ) = \sum_{k = 0}^{n}\left ( C_{n}^{k} \right )^{2}$.

Окончательно имеем: $\sum_{k = 0}^{n}\left ( C_{n}^{k} \right )^{2}=C_{2n}^{~n} $.

[--mS--]

А зачем такие сложности? Не проще взять урну, в ней $n$ белых и $n$ чёрных шаров, и двумя путями посчитать число способов вынуть из неё без возвращения и без учёта порядка $n$ шаров? С одной стороны, это $|\Omega|=C_{2n}^n$, с другой, если всё $\Omega$ разбить на попарно несовместные события $\Omega=\bigcup_{k=0}^n A_k$, где $A_k$ состоит в том, что появилось $k$ белых шаров и $n-k$ чёрных, - сумма $|\Omega|=\sum_{k=0}^n C_{n}^kC_n^{n-k}$.

[Asker Tasker]

Я хочу попробовать ещё раз Вашим методом: пусть нужно доказать, что $C_{n}^{m} = \sum_{j=0}^{m}C_{k}^{j}C_{n-k}^{m-j}$, причём $C_{s}^{t} = 0$, если $s < t$
Правильно ли я доказываю?
Пусть есть урна с n шариками: k чёрных, n-k белых. И нужно выбрать набор из m шариков (по условию m от нуля до n, то есть дополнительно ничего оговаривать не нужно).
С одной стороны, количество способов выбрать этот набор равно $C_{n}^{m}$.
С другой стороны, событие "вынуто m шариков" состоит из несовместных событий $A_{j}$ $=$ "появилось j чёрных шаров и соответственно $m - j$ белых" $\left( j = 0, ..., m \right)$.
j чёрных шаров из k чёрных шаров можно выбрать $C_{k}^{j}$ способами, аналогично - с белыми шарами (а именно - $C_{n-k}^{m-j}$). Тогда $\left| A_{j} \right| = C_{k}^{j} C_{n-k}^{m-j}$ и окончательно:
$C_{n}^{m} = \left| \bigcup_{j=0}^{m} \right| = \sum_{j=0}^{m} C_{k}^{j} C_{n-k}^{m-j}$

[--mS--]

Да, а что-то смущает?

[Zealint]

Давайте ещё проще. Мы знаем, что есть производящая функция

$$ (1+z)^n = \sum_{k=0}^{\infty}\binom{n}{k}z^k. $$

Произведение производящих функций даёт свёртку:

$$ (1+z)^n\cdot(1+z)^n = \sum_{k=0}^{\infty} \left(\sum_{j=0}^{k}\binom{n}{k-j}\binom{n}{j}\right)z^k. $$

С другой стороны

$$(1+z)^{2n}=\sum_{k=0}^{\infty}\binom{2n}{k}z^k.$$

Коэффициенты рядов равны, в частности при $k=n$, поэтому

$$ \binom{2n}{n}=\sum_{j=0}^{n}\binom{n}{n-j}\binom{n}{j}=\sum_{j=0}^{n}\binom{n}{j}^2. $$

[Asker Tasker]

--mS-- в сообщении #615343 писал(а):

Да, а что-то смущает?

Нет, просто хотел попрактиковаться :)

Zealint в сообщении #615362 писал(а):

Давайте ещё проще.

Наверное, этот вариант проще для тех, кто знаком со свёрткой и производящими функциями. Не подскажете, где про эту парочку можно почитать в доступном изложении?

[arseniiv]

О производящих функциях (и о свёртке последовательностей) есть в Грэхеме, Кнуте, Паташнике «Конкретная математика» и (!) на одноимённом сайте Zealint (увы, у него, похоже, мало на этот проект времени — там ещё не весь материал).

Производящие функции бывают разных видов, но используемые здесь «обычные» — это формальные ряды вида $\sum_{i = 0}^{\infty} a_i x^i$, где $(a_i)$ — последовательность. Они удобны тем, что простым операциям над ними соответствуют относительно простые над последовательностями.

[Asker Tasker]

Спасибо за информацию :)

[Zealint]

arseniiv в сообщении #616804 писал(а):

(увы, у него, похоже, мало на этот проект времени — там ещё не весь материал).

Да, не весь. Но все, что входит в учебный курс, кроме упражнений, уже есть.