Тождество [Комбинаторика]

[Whitaker]

Здравствуйте!
Надо доказать следующее тождество:
$C_{n+r-1}^{r}-C_{n}^{1}C_{n+r-3}^{r-2}+C_{n}^{2}C_{n+r-5}^{r-4}-....=C_{n}^{r}$.
Есть такая идея у меня, но хотелось бы кое-что спросить.
Есть $n$ различных элементов $a_1, a_2, ....a_n$.
Воспользуемся формулой включений и исключений.
$N(\bar{a}_1\bar{a}_2....\bar{a}_n)=N-N(a_1)-...N(a_n)+N(a_1a_2)+...+N(a_{n-1}a_n)+...+(-1)^nN(a_1a_2...a_n)$,
где:$N(\bar{a}_1\bar{a}_2....\bar{a}_n)$-количество сочетаний длины $r$, где элементы $a_1, a_2, ....a_n$ встречаются только по одному разу. Очевидно, что $N(\bar{a}_1\bar{a}_2....\bar{a}_n)=C_{n}^{r}$.
$N$-общее количество таких сочетаний с повторениями длины $r$. Очевидно, что $N=\bar{C}_{n}^{r}=C_{n+r-1}^{r}$.
У меня такой вопрос:
$N(a_1)$-это количество сочетаний длины $r$ где элемент $a_1$ встречается больше одного раза и вообще не встречается?? Я правильно написал?

-- Вс авг 21, 2011 11:21:38 --

Если $N(a_1)$-количество сочетаний длины $r$, где элемент $a_1$ встречается строго больше одно раза. То величина $N(a_1)=\bar{C}_{n}^{r-2}=C_{n+r-3}^{r-2}$. Тогда:
$\sum_{i=1}^{n}N(a_i)=nC_{n+r-3}^{r-2}$. Если так, то ответ получается.
Но ведь $N(a_1)$-количество сочетаний, обладающие свойством $a_1$, т.е. сочетания в которых $a_1$ входит больше одно раза или вообще не встречается. Объясните пожалуйста.

[Whitaker]

P.S.$\bar{C}_{n}^{r}$ - это количество сочетаний c повторениями из $n$ элементов по $r$ и по определению он равен $C_{n+r-1}^{r}$

[nnosipov]

Whitaker в сообщении #476796 писал(а):

P.S.$\bar{C}_{n}^{r}$ - это количество сочетаний c повторениями из $n$ элементов по $r$ и по определению он равен $C_{n+r-1}^{r}$

Это не по определению, это так получается, если подсчитать.

[Whitaker]

nnosipov в сообщении #476802 писал(а):

Whitaker в сообщении #476796 писал(а):

P.S.$\bar{C}_{n}^{r}$ - это количество сочетаний c повторениями из $n$ элементов по $r$ и по определению он равен $C_{n+r-1}^{r}$

Это не по определению, это так получается, если подсчитать.

Вы правы. Перепутал. Извините.


Если $N(a_1)$-количество сочетаний длины $r$, где элемент $a_1$ встречается строго больше одно раза. То величина $N(a_1)=\bar{C}_{n}^{r-2}=C_{n+r-3}^{r-2}$. Тогда:
$\sum_{i=1}^{n}N(a_i)=nC_{n+r-3}^{r-2}$. Если так, то ответ получается.
Но ведь $N(a_1)$-количество сочетаний, обладающие свойством $a_1$, т.е. сочетания в которых $a_1$ входит больше одно раза или вообще не встречается. Объясните пожалуйста.