Каково решение задачи по комбинаторике?

Question

[Gagatyn]

У Остапа Бендера в мешке 100 слонов, из которых k разноцветных, и он раздает их m детям по слону в руки. k < m < 100

Сколькими способами может состояться раздача слонов?

Comments

[AlikDex]

решать при помощи формул братан =)

[Gagatyn]

AlikDex: сложная задача, еще не решал такие, не видел даже подобные. У вас отображается весь текст?

[Сергей Соколов]

Gagatyn: текст вопроса обрывается на «в руки (k»

[Сергей Соколов]

не понятно условие про разноцветность слонов.

Answer 1

[Сергей Соколов]

У Остапа Бендера в мешке 100 слонов, из которых k разноцветных, и он раздает их m детям по слону в руки (k < m < 100). Сколькими способами может состояться раздача слонов?

Первого слона можно выбрать 100 способами и отдать m способами.
Второго выбрать 99 и отдать m – 1 способом.

N = 100 * m * 99 * (m-1) * ... * (100 - m) * 1
N = 100! / m! * m! = 100!

Итого, ответ 100! (100 факториал)

Но, похоже, я что-то не понял в условии задачи – к чему там разноцветность некоторых слонов?

Comments

[Gagatyn]

Сергей Соколов тоже не понятно, но скорее всего это можно опустить.

[Сергей Соколов]

Gagatyn: может, там имеется в виду что-то типа, «серые слоны все одинаковые, и поэтому не считаются за разных»?

[Gagatyn]

Сергей Соколов: узнаю решение, вы будете знать первым

[jcmvbkbc]

Сергей Соколов: это решение не учитывает, что результаты разных раздач могут получиться одинаковыми.
Например, последовательность "выбрать первым первого слона и отдать его первому ребёнку, вторым -- второго слона и отдать его второму ребёнку, X" и последовательность "выбрать первым второго слона и отдать его второму ребёнку, вторым -- первого слона и отдать его первому ребёнку, X" приведут к одинаковому распределению слонов. Чтобы этого избежать нужно либо гарантировать уникальность раздачи, либо учесть количество разных раздач. Можно, например, слона выбранного i-м всегда отдавать i-му ребёнку, результат будет 100!/m!.
Но это решение в любом случае никак не учитывает разноцветность слонов.

Answer 2

[Владимир Олохтонов]

У нас есть k разноцветных слонов и 100-k одинаковых слонов. Дети разные, одноцветные слоны - одинаковые.

Решение в лоб:
Возможны 2 варианта задачи:
1) m <= 100-k (одинаковых слонов хватает на всех детей)
2) m > 100-k (одинаковых слонов не хватает на всех)

В первом случае нужно понять сколькими разными способами можно раздать разноцветных слонов, поскольку одинаковых слонов в первом случае хватает на всех, то число способов может быть следующим:
Число способов вытащить k_i разноцветных слонов:
C_{k}^{k_i}
Число способов вытащить из мешка k_i разноцветных слонов и раздать их детям:
C_{k}^{k_i} A_{m}^{k_i}

Вытащенных из мешка разноцветных слонов может быть от 0 до k, а значит в итоге получаем:
\sum_{i=0}^{i=k} C_{k}^{i} A_{m}^{i}

Во втором случае в соответствии с правилом Дерихле будет выбрано минимум (m + k - 100) цветных слонов, остальное так же:
\sum_{i=m+k-100}^{i=k} C_{k}^{i} A_{m}^{i}

Итого, в общем случае:
\sum_{i=max(m+k-100, 0)}^{i=k} C_{k}^{i} A_{m}^{i}