Помогите решить задачку по комбинаторике....

[C0rWin]

Требуется разделить - n человек на какое-то количество кругов. Сколько способов есть это сделать. Теперь дано, что есть рекурсивное решение этой задачи вида

\[ {\rm{G}}\left( {\rm{n}} \right){\rm{ = n}} * {\rm{G}}\left( {{\rm{n - 1}}} \right) \]

Окуда понятно, что решением будет

\[ n! \]

Теперь требуется придти к решению этой задачи аналитическим путем, попутно объясняя почему ответ именно такой... Есть у кого-нибудь какие идеи? Буду очень благодарен...

[bot]

C0rWin писал(а):

Требуется разделить - n человек на какое-то количество кругов.

Как это разделить на какое-то число? В том числе и на $n+1$?

Числу $n!$ соответствует число различных инъективных (или сюръективных - для конечных множеств это одно и то же) отображений n-элементного множества на себя.
В применении к человекам это означает число способов расположить их в очередь, во времена дефицита писали номера на ладошках. Указанная рекуррентность возникает очень просто: первый номер отдаём любому из претендентов, а после этого остаётся раздать n-1 номеров n-1 человекам.

[C0rWin]

Ну я бы хотел посмотреть как Вы будете разделять n людей на n+1 кругов... Кол-во кругов заранее не известно их может быть сколько угодно. Людей в круге тоже не понятно сколько. Отличительная черта круга от длинной очереди это то, что нужно после растановки убирать ротации которые повторяются... Тут я не знаю какое кол-во ротации убирать плюс меня соверншенно не интересует каким образом эти круги сами расставлены.
Не смотря на тривиальный ответ придти к нему не так то и просто. По крайней мере я так и не увидел как это сделать... Скажем если бы это были не круги, а так кучки людей то это выглядело бы совсем по другому, даже попроще, но вот проблема я не вижу как после того как я разбиваю людей на кучки убрать повторяющиеся ротации...
Буду благодарен за конструктивную помощь...

[bot]

C0rWin писал(а):

Ну я бы хотел посмотреть как Вы будете разделять n людей на n+1 кругов...

Дык я и пробовать не стану. Вопрос был задан из-за неясности формулировки - для уточнения.
Вы задачу-то сформулируйте. Что это за круги у Вас? Из того, что Вы написали, совершенно непонятно о чём идёт речь. Какие такие ротации происходят? Каждый мен по кругу ходит?

Может быть Вы имеете в виду число всех разбиений n-элементного множества или (равносильно) число эквивалентностей на этом множестве? Но там другая рекуррентность и ответ не так прост. К примеру, для n=3 легко выписать все разбиения:
1|2|3
12|3
13|2
23|1
123
Итого 5 различных разбиений, а не 6=3!

[Руст]

n! перестановок можно разделить на циклы (по видимому это и есть круги). Число перестановок n! и каждый из них определяет однозначно разбиение на циклы. В этом смысле количество способов разделения на "круги" равно n!.

[bot]

Похоже так. Требуется n человек рассадить на карусели с общим числом мест, равным n. Одноместные карусели не исключаются и карусели с одинаковым числом мест неразличимы.
Руст - телепат.