2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: Доказать комбинаторное тождество
Сообщение10.07.2009, 18:59 
jetyb в сообщении #227808 писал(а):
При $n=2$ выражения не сходятся.
Попробуйте получить $C_{2n-1}^{n-1}$, рассматривая перегородки между построенными в линию шарами.

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

 
 
 
 Re: Доказать комбинаторное тождество
Сообщение10.07.2009, 19:08 
Цитата:
$\sum\limits_{k=0}^{n-1}(-1)^kC_n^kC_{3n-k-1}^{2n}$

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

 
 
 
 Re: Доказать комбинаторное тождество
Сообщение10.07.2009, 19:32 
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}$

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

 
 
 
 Re: Доказать комбинаторное тождество
Сообщение10.07.2009, 19:55 
Ну да, все просто оказалось, расставить n-1 перегородку по 2n-1 местам, надо решать головой, а не руками :cry: , но все равно очень интересно как доказать указанное выше комбинаторное тождество, не связывая его уже с данной задачей

 
 
 
 Re: Доказать комбинаторное тождество
Сообщение11.07.2009, 00:20 
Аватара пользователя
IE
По-моему, в качестве метода доказательства тождества надо использовать саму задачу, т.к. именно она ведет к двум таким неожиданным результатам и по сути, устанавливает тождество.
Задача очень интересная!

 
 
 
 Re: Доказать комбинаторное тождество
Сообщение11.07.2009, 12:52 
Стандартный способ - попробовать производящие функции

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

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

 
 
 
 Re: Доказать комбинаторное тождество
Сообщение17.07.2009, 09:14 
Аватара пользователя
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$.

 
 
 
 Re: Доказать комбинаторное тождество
Сообщение17.07.2009, 10:58 
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\}$ , так? Может заодно подскажете что почитать по производящим функциям?

 
 
 
 Re: Доказать комбинаторное тождество
Сообщение17.07.2009, 11:28 
Можно посмотреть - Дж.Риордан, КОМБИНАТОРНЫЕ ТОЖДЕСТВА.

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group