2014 dxdy logo

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

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




На страницу 1, 2, 3  След.
 
 Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 13:49 
Аватара пользователя
Если k и n - целые положительные числа, то доказать, что $\large{\frac{(kn)!}{(k!)^nn!}}$ тоже целое число.

Пробовал по индукции, но застрял на n = k.

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 14:43 
Аватара пользователя
Используйте комбинаторный смысл:
1. $\frac{(a_1+a_2+\dots+a_n)!}{a_1!a_2!\dots a_n!}$ - это число способов разложить $a_1+a_2+\dots+a_n$ шаров по $n$ ящикам, так чтобы в $i$-ом ящике было $a_i$ шаров ("мультиномиальный коэффициент", "разбиения").
2. $n!$ - число способов переставить $n$ ящиков между собой в некотором порядке ("перестановки").

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 15:08 
Аватара пользователя
Тогда что такое kn? Это получается в каждом ящике должно быть одинаковое количество n шаров? И таких ящиков k штук? Если у нас шары одинакоыве, то мы вообще можем это сделать единственным способом.

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 15:46 
Аватара пользователя
Dosaev
Ваше выражение есть число способов раскладки $kn$ различных шаров по $n$ неразличимым ящикам, чтобы в каждом ящике было по $k$ шаров. Надеюсь я понятно объяснил? Хотя AlexValk Вам уже всё подсказал.

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 20:30 
Аватара пользователя
Почему по неразличимым ящикам, ведь сказано что в i-том ящике должно находится $a_i$ шаров.

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 20:34 
Аватара пользователя
Давайте сначала решим такую задачку.
Сколькими способами можно разложить $kn$ различных шариков по $n$ ящикам, чтобы в каждом ящике было $k$ шариков?

-- Вс дек 04, 2011 20:35:54 --

Dosaev в сообщении #511441 писал(а):
Почему по неразличимым ящикам, ведь сказано что в i-том ящике должно находится $a_i$ шаров.

AlexValk здесь имел ввиду общий случай.

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 20:43 
Аватара пользователя
По-моему, можно забить на шары и тупо смотреть порядок вхождения каждого простого p сверху и снизу.

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 20:51 
Аватара пользователя
Ну если опираться на такую логику: первые k шариков мы можем разложить n способами, вторые (n-1) способами, третьи (n-2) способами, n-е k шариков 1 способом. Тогда получается n! способами?

-- Вс дек 04, 2011 21:01:18 --

ИСН в сообщении #511444 писал(а):
По-моему, можно забить на шары и тупо смотреть порядок вхождения каждого простого p сверху и снизу.

А поподробнее можно?

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 21:08 
Аватара пользователя
Dosaev в сообщении #511447 писал(а):
Ну если опираться на такую логику: первые k шариков мы можем разложить n способами, вторые (n-1) способами, третьи (n-2) способами, n-е k шариков 1 способом. Тогда получается n! способами?

Нет! Что Вы?!
Сколькими способами можно выбрать $k$ предметов из $n$?

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 21:09 
Аватара пользователя
$ C_n^k$ Я не могу установитьт связь между "разложить по ящикам" и "выбрать из чего что-то". :-(

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 21:11 
Аватара пользователя
После того как Вы выбрали $k$ предметов из $nk$.
Cколько предметов теперь осталось? И сколькими способами можно выбрать $k$ предметов из числа оставшихся?

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 21:12 
Аватара пользователя
$C_{nk-k}^k$

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 21:14 
Аватара пользователя
Теперь сколько способов будет после $k$ шагов?

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 21:18 
Аватара пользователя
$C_{nk-k^2}^k?$

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 21:22 
Аватара пользователя
Нет.
После первого шага $C_{nk}^{k}$, после второго шага $C_{nk-k}^{k}$, после третьего шага $C_{nk-2k}^{k}$,......,после $n$-го шага $C_{nk-(n-1)k}^{k}$

По принципу произведения: $C_{nk}^{k}C_{nk-k}^{k}C_{nk-2k}^{k}....C_{nk-(n-1)k}^{k}$

 
 
 [ Сообщений: 41 ]  На страницу 1, 2, 3  След.


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