Глория

[wpoms.]

Семеро друзей собираются играть в игру "Глория". Для этого им нужно сформировать четыре команды, которые, очевидно, не могут иметь равное число игроков. Сколькими способами они могут образовать эти команды? (Порядок игроков внутри команды неважен, но каждый человек может принадлежать только одной команде).

@темы: Комбинаторика

Comments

[Груша Вильямс]

Если не ошибаюсь, то `C^4_7+3C^3_7+C^2_3C^2_7`

[Груша Вильямс]

А нет, не правильно подсчитал, так вышло `C^4_7+C^3_7+(9C^2_7)/2`.
Добавим в каждую команду по одному человеку, получим 1,2,3,4. Затем считаем сколько способов образовать команды, чтоб в одной из них было 4 человека. Из 1,2,3,4 видно, что если добавить в какую-нибудь из команд 3 человека, то всё однозначно определится, значит `C^4_7`. Теперь добавим в какую-то команду двух человек, например, в первую
1,2,3,4
5
6
тогда седьмой человек, будет входить во вторую, третью или четвертую, таким образом `(3C^3_7)/3=C^3_7`.
Затем одного добавляем, например, в первую
1,2,3,4
5
тогда раскидать двух оставшихся можно девятью способами: оба входят во вторую, третью или четвертую (3), один во вторую, другой в третью и наоборот (2), один в третью, другой в четвертую и наоборот (2), один во вторую, другой в четвертую и наоборот (2), таким образом `(9C^2_7)/2`.

p.s. мне кажется, что в `(9C^2_7)/2` входит что-то из `C^3_7`, как отобрать не знаю.

[Trotil]

Груша Вильямс, не учтена, например, такая разбивка: (1,2) (3,5)(4,7)(6)

[Trotil]

У меня получилось ровно 350 способов...

[Trotil]

350 - правильный ответ.
Стыдно, сразу не вспомнил формулу и структуру, которую проходил в вузе и ночью заново её вывел )))

p.s. школьникам давать задачу - жестоко.

[All_ex]

Разбиение на команды возможно вида 1-1-1-4, 1-1-2-3 или 1-2-2-2... поскольку команды не упорядочены (не пронумерованы), то одинаковые по числу участников считаются с точностью до перестановки...

1) 1-1-1-4 ... выбираем `C_7^4`вариантов для последней команды... остальные три участника однозначно делятся на три команды...

2) 1-1-2-3 ... выбираем `C_7^3`вариантов для последней команды И `C_4^2`вариантов для третьей команды... остальные два участника однозначно делятся на две команды...

3) 1-2-2-2 ... выбираем `C_7^2`вариантов для последней команды И `C_5^2`вариантов для третьей команды И `C_3^2`вариантов для второй команды... оставшийся участник образует первую команду...
И не забываем учесть перестановки последних трёх команд...

Итого, `N = C_7^3 + C_7^3 * C_4^2 + {C_7^2 * C_5^2 * C_3^2}/{3!} = 350`

[Trotil]

Моё решение:
Нужно найти функцию f(команд, человек)=f(m,n) - число способов разместить n человек по m командам, точнее f(4,7).
Очевидно, что f(x,x)=1 и f(1,x)=1

Пусть мы имеем m команд и (n-1) человек и известно f(m,n-1). Можно добавить n-того человека в любую команду любого такого разбиения, при это все новые комбинации будут различными. Также в f(m,n) входит случай, когда мы к (m-1) командам из (n-1) человек добавляем новую команду из нового человека.

Мы получили соотношение f(m,n)=m*f(m,n-1)+f(m-1,n-1) с начальными условиями f(x,x)=1 и f(1,x)=1.

Нужно вычислить f(4,7). Напишем небольшую программу и вычислим это значение в онлайн-компиляторе (а кому интересно, может вручную подсчитать). Удобнее всего написать программу на Хаскелле (обратите внимание, я туда записал только наше условие, для Хаскелла в данном случае этого достаточно):

func 1 n             = 1
func m n | m==n      = 1
         | otherwise = (func (m) (n-1))*m + (func (m-1) (n-1))

main = print (func 4 7)

Компилятор: www.compileonline.com/compile_haskell_online.ph...

Получили:
Executing the program....
350

Про Хаскелл я писал здесь: trotil.diary.ru/p179587552.htm?oam

Функция f(n,m) это не что иное, как числа Стирлинга второго рода: en.wikipedia.org/wiki/Stirling_numbers_of_the_s...
(в русскоязычной вики мало материала)

[All_ex]

Trotil, я опираюсь на простые комбинаторные принципы (поскольку не изучал комбинаторные алгоритмы ...) ... и удовлетворён, когда это работает... Причём, такое рассуждение, по-моему, подъёмно для школьников...
Кроме того, трудно предположить, что у школьника на олимпиаде будет доступ к компьютеру... хотя малые числа позволяют провести ручной счёт по указанным Вами формулам ...

[Trotil]

All_ex, не могу согласиться, что моё решение сложнее вашего.
Индуктивное соотношение получилось не очень сложным.
Подсчитать f(4,7) можно и вручную (я только дополнительно показал, как это изящно можно запрограммировать), у меня это заняло 5 минут с проверкой.
Общую формулу находить тоже необязательно.

Самое сложное - догадаться попробовать решать через индукцию.
Однако если школьник знаком с доказательством утверждения C(n.m)=C(n.m-1)+C(n-1,m-1), где применяется похожий приёмчик, будет проще.

[Груша Вильямс]

Trotil, Нужно найти функцию f(команд, человек)=f(m,n) - число способов разместить n человек по m командам, точнее f(4,7).
Очевидно, что f(x,x)=1
Пусть x есть два, тогда число способов разместить двух человек в две команды равно двум: первый в первую, второй во вторую, и наоборот.

[All_ex]

Груша Вильямс, первый в первую, второй во вторую, и наоборот. - Нет... перестановки команд с одинаковым числом участников здесь не интересуют... это считается одним вариантом разбиения на команды...

[Груша Вильямс]

All_ex, аа, то есть f(x,1) мы определить не можем, так как одного человека по x командам не раскидаешь при x>1, а x человек вполне возможно, то есть это разбиение, где в каждой команде по одному человеку ?

[All_ex]

Груша Вильямс, ну, как-то так...

[Груша Вильямс]

All_ex, не знаю что вчера случилось со мной, но как-то не заметил перестановок команд с одинаковым числом участников. Теперь понял всё)
Вечером надо попробовать будет через f(m,n)

[Trotil]

Вечером надо попробовать будет через f(m,n)

Получилось?
Этот приём полезен для некоторых комбинаторных задач.

[Груша Вильямс]

Trotil, так и не садился ещё. В 2014ом попробую

[Груша Вильямс]

Trotil, вот сел сейчас, прочитал Ваше сообщение, но вот одну вещь не понял:
Мы получили соотношение f(m,n)=m*f(m,n-1)+f(m-1,n-1) вот как углядеть, что f(m-1,n-1) не будет входить в m*f(m,n-1) ? У нас есть число способов размещения (n-1) человек по m командам f(m,n-1), в каждом таком способе можно получить ещё m команд добавляя одного человека в любую из m команд, итого вроде как однозначно определяется f(m,n)=m*f(m,n-1)

[Trotil]

>

вот как углядеть, что f(m-1,n-1) не будет входить в m*f(m,n-1)

m*f(m,n-1) не покрывает некоторые комбинации f(m,n) и это можно понять, только имея наглядное изображение комбинаций f(m,n) на листочке, включая их всякие предельные случаи. Да, можно что-то пропустить, если действовать невнимательно.

Способ, который мне всегда помогал - проверить формулу прямым пересчётом комбинаций для небольших чисел. Тогда сразу становится видно, что что-то в формуле не учтено.

Алгоритм такой:
- выводишь формулу для частного случая (например, для f(2,4), получаешь значение для f(2,4)
- рисуешь на листочке все комбинации f(2,4) - сравниваешь.
- сошлось? Обобщаешь метод на f(m,n).
- не сошлось? Смотришь, какие комбинации не подсчитал / подсчитал несколько раз, переходишь к (1).

[Груша Вильямс]

Trotil,
например f(2,3)
тире разделяет команды
1-2,3
2-1,3
3-1,2
больше нет способов
f(2,2)=1, f(1,4)=1, тогда f(2,3)=3*1+1=4 не сходится...
С другой стороны f(2,4)
1-2,3,4
1,2-3,4
1,3-2,4
1,4-2,3
2-1,3,4
3-1,2,4
4-1,2,3
7 способов то есть, больше вроде бы нет уже.
Но уже f(2,4)=4f(2,3)=12 даёт, что не порядок.
Не пойму, что не учел.

[Груша Вильямс]

Trotil, всё разобрался) n-1 вместо m умножал
f(2,3)=2f(2,2)+f(1,2)=2*1+1=3 сходится)
f(2,4)=2f(2,3)+f(1,3)=2*3+1=7 сходится)
всё, норм)

p.s. просто без выходных из-за этих праздников работали, туплю жутко