Доказать комбинаторное тождество

[IE]

В процессе решения задачки по теории вероятностей получил в числителе ответа вот такое выражение $\sum\limits_{k=0}^{n-1}{(-1)^kC^k_nC_{3n-k-1}^{2n}}$ , в задачнике числитель ответа выглядит значительно изящнее $C^{n-1}_{2n-1}$, оказалось, что эти величины равны, как это доказать? Полистал книжку Риордана "комбинаторные тождества", но подходящей для тупой подстановки формулы не нашел,жду совета в каком направлении двигаться.
Кстати, сама задачка: Найти вероятность того, что при размещении 2n неразличимых шаров по n ящикам не окажется пустых ящиков.

[jetyb]

При $n=2$ выражения не сходятся.
Попробуйте получить $C_{2n-1}^{n-1}$, рассматривая перегородки между построенными в линию шарами.

[IE]

jetyb в сообщении #227808 писал(а):

При $n=2$ выражения не сходятся.
Попробуйте получить $C_{2n-1}^{n-1}$, рассматривая перегородки между построенными в линию шарами.

виноват((, забыл коэффициент

[jetyb]

Цитата:

$\sum\limits_{k=0}^{n-1}(-1)^kC_n^kC_{3n-k-1}^{2n}$

Интересно, как такой числитель получился? Для доказательства достаточно получить ответ с $C_{2n-1}^{n-1}$ в числителе. Просто рассмотрите вероятность как (число нужных нам исходов)/(общее число исходов). Это должно быть проще.

[IE]

jetyb в сообщении #227811 писал(а):

Интересно, как такой числитель получился? Для доказательства достаточно получить ответ с $C_{2n-1}^{n-1}$ в числителе. Просто рассмотрите вероятность как (число нужных нам исходов)/(общее число исходов). Это должно быть проще.

Ну так и делаем, рассмотрим последовательность событий $A_1..A_n$, где i-е событие заключается в том, что соответствующий ящик пуст, тогда искомое событие есть $\overline{A_1}\cap\dots \cap \overline{ A_n}}=\overline{A_1 \cup \dots \cup A_n}$ , далее

$$\mathrm{P}(A_1 \cup \dots \cup A_n)=\sum\limits_{k=1}^{n-1}(-1)^{k-1} \sum\limits_{1\leqslant i_1 < \dots <i_k\leqslant n}{P(A_{i_1}\dots A_{i_k})}$$

,а $\sum\limits_{1\leqslant i_1 < \dots <i_k\leqslant n}{P(A_{i_1}\dots A_{i_k})}=C_n^kC^{2n}_{3n-k-1}$

[jetyb]

Можно сделать проще. Пусть это 2n шаров:
o o o o o o o o o o
Учитывая, что в каждом ящике содержится хоть один шар, разделим 2n шаров
по ящикам:
o | o o o | o | o o | o o o
Сколько раз можно так расставить перегородки?

[IE]

Ну да, все просто оказалось, расставить n-1 перегородку по 2n-1 местам, надо решать головой, а не руками , но все равно очень интересно как доказать указанное выше комбинаторное тождество, не связывая его уже с данной задачей

[age]

IE
По-моему, в качестве метода доказательства тождества надо использовать саму задачу, т.к. именно она ведет к двум таким неожиданным результатам и по сути, устанавливает тождество.
Задача очень интересная!

[Gafield]

Стандартный способ - попробовать производящие функции

[Sonic86]

Еще есть Грэхем, Кнут, Паташник Конкретная математика - там тоже есть много комбинаторных тождеств.
Хотя я поковырялся, что-то у меня ничего не получилось.
Кстати, если шары считать разными, то тоже прикольные формулы получаются.

Вообще формула включения-исключения - стандартное средство, ее использовать только в том случае, если нельзя больше ничего сделать

[maxal]

IE в сообщении #227802 писал(а):

В процессе решения задачки по теории вероятностей получил в числителе ответа вот такое выражение $\sum\limits_{k=0}^{n-1}{(-1)^kC^k_nC_{3n-k-1}^{2n}}$ , в задачнике числитель ответа выглядит значительно изящнее $C^{n-1}_{2n-1}$, оказалось, что эти величины равны, как это доказать?

Через производящие функции:

$$\sum_{k=0}^{n-1}(-1)^k\binom{n}{k}\binom{3n-k-1}{2n} = \sum_{k=0}^{n-1} [x^k] (1-x)^n \cdot [x^{3n-k-1}] \frac{x^{2n}}{(1-x)^{2n+1}} = [x^{n-1}] \frac{1}{(1-x)^{n+1}} = (-1)^{n-1} \binom{-(n+1)}{n-1} = \binom{2n-1}{n-1}.$$

Здесь $[x^t]$ обозначает оператор взятия коэффициента при $x^t$.

[IE]

maxal
Большое спасибо! Насколько я понимаю, второй переход получается с помощью формулы свертки, что-то вроде $[x^{3n-k-1+k}]\left\{\frac{(1-x)^n x^{2n}}{(1-x)^{2n+1}}\right\}=[x^{3n-1}]\left\{\frac{x^{2n}}{(1-x)^{n+1}}\right\}=[x^{n-1}]\left\{\frac{1}{(1-x)^{n+1}}\right\}$ , так? Может заодно подскажете что почитать по производящим функциям?

[vvvv]

Можно посмотреть - Дж.Риордан, КОМБИНАТОРНЫЕ ТОЖДЕСТВА.