Задача на доказательство. Комбинаторика.

[Dosaev]

Если k и n - целые положительные числа, то доказать, что $\large{\frac{(kn)!}{(k!)^nn!}}$ тоже целое число.

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

[AlexValk]

Используйте комбинаторный смысл:
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$ ящиков между собой в некотором порядке ("перестановки").

[Dosaev]

Тогда что такое kn? Это получается в каждом ящике должно быть одинаковое количество n шаров? И таких ящиков k штук? Если у нас шары одинакоыве, то мы вообще можем это сделать единственным способом.

[Whitaker]

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

[Dosaev]

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

[Whitaker]

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

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

Dosaev в сообщении #511441 писал(а):

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

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

[ИСН]

По-моему, можно забить на шары и тупо смотреть порядок вхождения каждого простого p сверху и снизу.

[Dosaev]

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

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

ИСН в сообщении #511444 писал(а):

По-моему, можно забить на шары и тупо смотреть порядок вхождения каждого простого p сверху и снизу.

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

[Whitaker]

Dosaev в сообщении #511447 писал(а):

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

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

[Dosaev]

$ C_n^k$ Я не могу установитьт связь между "разложить по ящикам" и "выбрать из чего что-то".

[Whitaker]

После того как Вы выбрали $k$ предметов из $nk$.
Cколько предметов теперь осталось? И сколькими способами можно выбрать $k$ предметов из числа оставшихся?

[Dosaev]

$C_{nk-k}^k$

[Whitaker]

Теперь сколько способов будет после $k$ шагов?

[Dosaev]

$C_{nk-k^2}^k?$

[Whitaker]

Нет.
После первого шага $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}$