Число группировок

[Aks1]

Как найти число группировок из n при условии, что размер группы ограничен c обоих сторон.
Есть ли простая формула?

[bot]

Что Вы называете группировкой?
Упорядоченную, неупорядоченную выборку или что-то иное?

[Aks1]

bot
Неупорядоченную. По сути, набор сочетаний, исчерпывающий множество.
То есть у нас 10 элементов,к примеру. А размер группы ограничен от 2х до 3х. Значит пойдет группировка с числом элементов: 3,3,2,2.
В принципе, последняя группа может нарушать ограничение на размер - иначе, я чувствую, там придется очень сильно заморочиться, чтобы это посчитать.
То есть тогда 3,3,3,1 тоже подходит.

Для 4х элементов: 1,2,3,4 с ограничением на размер группы = 2
Получим:
+ 1,2; 3,4
+ 1,3; 2,4
+ 1,4; 2,3
Итого: 3 группировки.

Если вы мне еще подскажете, как моя "группировка" правильно (ну или скажем, оффициально) называется в комбинаторике, то я скажу вам двойное спасибо)

[bot]

Aks1 в сообщении #290345 писал(а):

Неупорядоченную. По сути, набор сочетаний, исчерпывающий множество.

Чуть было не пошёл по ложному следу, однако примеры остановили. Из них похоже, что Вас интересуют разбиния конечных множеств с ограничениями на мощность классов разбиений. Вопрос не слишком прост даже в случае отсутствия ограничений.

[Aks1]

bot
Да, именно это.
А если ограничение - равенство?
Тогда вид групп в разбиении нам уже известен и надо только найти их возможные элементы. А это можно как-то посчитать через сочетания.

[bot]

Верно ли я пронимаю, что "огарничение=равенство" означает фиксирование одного и того числа элементов в каждом классе разбиения, за исключением одного возможного остаточного хвостика?

Если да, то всё совсем просто. Пусть n - число элементов, k - мощность класса разбиения, $n=ks+r,\ 0\leqslant r <k$. Тогда число всех требуемых разбиений - это

$\frac{1}{s!}\cdot C_n^k\cdot C_{n-k}^k \dots C_{r+k}^k $

Это просто принцип умножения и делим на число перестанок s "полных классов разбиения".

[kahey]

Aks1 в сообщении #290345 писал(а):

bot
Неупорядоченную. По сути, набор сочетаний, исчерпывающий множество.
То есть у нас 10 элементов,к примеру. А размер группы ограничен от 2х до 3х. Значит пойдет группировка с числом элементов: 3,3,2,2.
В принципе, последняя группа может нарушать ограничение на размер - иначе, я чувствую, там придется очень сильно заморочиться, чтобы это посчитать.
То есть тогда 3,3,3,1 тоже подходит.

Для 4х элементов: 1,2,3,4 с ограничением на размер группы = 2
Получим:
+ 1,2; 3,4
+ 1,3; 2,4
+ 1,4; 2,3
Итого: 3 группировки.

Если вы мне еще подскажете, как моя "группировка" правильно (ну или скажем, оффициально) называется в комбинаторике, то я скажу вам двойное спасибо)

Для варианта 3,3,3,1 я думаю так:

(8*7*5*4*2)*10

Только не спрашивайте как я это получил.

-- Пт фев 19, 2010 21:25:40 --

Для случая 3,3,3,1 можно подойти следующим образом.
Число расстановок 10 цифр равно 10!.
Число перестановок внутри тройки равно 3!
Поэтому 10! надо разделить на 3! три раза (у нас три тройки).
Комбинация 3,3,3,1 состоит из 4-ёх различных элементов. Число их перестановок равно 4!

Поэтому окончательно: $\frac {10!}{3!*3!*3!*4!}$

[Профессор Снэйп]

(Оффтоп)

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

[bot]

Здесь ошибка

kahey в сообщении #290448 писал(а):

Комбинация 3,3,3,1 состоит из 4-ёх различных элементов. Число их перестановок равно 4!

Поэтому окончательно: $\frac {10!}{3!*3!*3!*4!}$

Переставлять надо равномощные классы, поэтому окончательно вчетверо больше: $\frac {10!}{(3!)^4}$.

Число разбиений фиксированного типа считается без труда.
Пусть $n=k_1\cdot n_1+ \ldots + k_s\cdot n_s$, где $n_1, \ldots , n_s - $ все различные мощности классов разбиения, а $k_i - $ число классов мощности $n_i$. Тогда число разбиений данного типа будет

$$\dfrac{n!}{(n_1!)^{k_1} \ldots (n_s!)^{k_s}\cdot k_1! \ldots k_s! }$$

[kahey]

В задании не сказано, что можно переставлять только равномощные классы.
Но если можно переставлять только рывномощные классы, то последняя формула верна.

[bot]

При чём здесь сказано или не сказано? Речь идёт о числе разбиений данного типа. Что и как переставлять - это уже входит в способ решения, а не в условие. Описывать, какие перестановки здесь существенны для подсчёта, а какие нет - задача неблагодарная. Одним это очевидно по виду формулы, а для других слишком много писать придётся, вот я и предпочёл даже в облегчённом случае для начала более прозрачный вариант.
Вы однако как раз отвергнутый вариант и избрали, но ошиблись в конце.
На всякий случай, если сомневаетесь в ошибке:
Перенесите свои рассуждения со случая $3|3|3|1$ на случай $2|1$ и у Вас получится $\dfrac{3!}{2!\cdot 2!}=1,5$

[kahey]

kahey в сообщении #290448 писал(а):

Aks1 в сообщении #290345 писал(а):

bot
Неупорядоченную. По сути, набор сочетаний, исчерпывающий множество.
То есть у нас 10 элементов,к примеру. А размер группы ограничен от 2х до 3х. Значит пойдет группировка с числом элементов: 3,3,2,2.
В принципе, последняя группа может нарушать ограничение на размер - иначе, я чувствую, там придется очень сильно заморочиться, чтобы это посчитать.
То есть тогда 3,3,3,1 тоже подходит.

Для 4х элементов: 1,2,3,4 с ограничением на размер группы = 2
Получим:
+ 1,2; 3,4
+ 1,3; 2,4
+ 1,4; 2,3
Итого: 3 группировки.

Если вы мне еще подскажете, как моя "группировка" правильно (ну или скажем, оффициально) называется в комбинаторике, то я скажу вам двойное спасибо)

Для варианта 3,3,3,1 я думаю так:

(8*7*5*4*2)*10

Только не спрашивайте как я это получил.

-- Пт фев 19, 2010 21:25:40 --

Для случая 3,3,3,1 можно подойти следующим образом.
Число расстановок 10 цифр равно 10!.
Число перестановок внутри тройки равно 3!
Поэтому 10! надо разделить на 3! три раза (у нас три тройки).
Комбинация 3,3,3,1 состоит из 4-ёх различных элементов. Число их перестановок равно 4!

Поэтому окончательно: $\frac {10!}{3!*3!*3!*4!}$

Думаю последнюю перестановку не надо учитывать вовсе - она входит в 10!
Таким образом получаем:
$\frac {10!}{3!\cdot3!\cdot3!}$

Так, что ваша формула, получается, тоже не верна.
Надо ещё раз посмотреть.

-- Вс фев 21, 2010 13:04:57 --

Я не прав. Переставлять можно только равномощные классы.

Т.к. при фиксированном расположении классов, мы получаем при перестановки цифр все возможные классы, некоторые из которых повторяются, вот эти повторения и надо сократить.

[Aks1]

bot в сообщении #290413 писал(а):

Верно ли я пронимаю, что "огарничение=равенство" означает фиксирование одного и того числа элементов в каждом классе разбиения, за исключением одного возможного остаточного хвостика?

Именно! Спасибо за ответ)

bot в сообщении #290704 писал(а):

Число разбиений фиксированного типа считается без труда.
Пусть $n=k_1\cdot n_1+ \ldots + k_s\cdot n_s$, где $n_1, \ldots , n_s - $ все различные мощности классов разбиения, а $k_i - $ число классов мощности $n_i$. Тогда число разбиений данного типа будет

$$\dfrac{n!}{(n_1!)^{k_1} \ldots (n_s!)^{k_s}\cdot k_1! \ldots k_s! }$$

Но если так, то нужно просто перебрать все возможные размеры (а число каждого мы уже знаем). В чем же сложность определения числа разбиений?

[bot]

Вот в переборе всех допустимых типов разбиения сложность и заключается - их может и много ведь оказаться.

[kahey]

bot в сообщении #290413 писал(а):

Верно ли я пронимаю, что "огарничение=равенство" означает фиксирование одного и того числа элементов в каждом классе разбиения, за исключением одного возможного остаточного хвостика?

Если да, то всё совсем просто. Пусть n - число элементов, k - мощность класса разбиения, $n=ks+r,\ 0\leqslant r <k$. Тогда число всех требуемых разбиений - это

$\frac{1}{s!}\cdot C_n^k\cdot C_{n-k}^k \dots C_{r+k}^k $

Это просто принцип умножения и делим на число перестанок s "полных классов разбиения".

Надо бы проверить формулу.
Для случая 3,3,3,1, как мы выяснили, получаем $10 \cdot \frac{8 \cdot 7}{2} \cdot \frac{5 \cdot 4}{2}=2800$
$\frac{1}{3!}\cdot \frac {10!}{3!\cdot 7!}\cdot \frac {7!}{3!\cdot 4!} \dots \frac {4!}{3!\cdot 1!} $
Да, всё сошлось, правда формула не общая - вторая лучше.

-- Ср фев 24, 2010 10:38:00 --

Цитата:

Число разбиений фиксированного типа считается без труда.
Пусть $n=k_1\cdot n_1+ \ldots + k_s\cdot n_s$, где $n_1, \ldots , n_s - $ все различные мощности классов разбиения, а $k_i - $ число классов мощности $n_i$. Тогда число разбиений данного типа будет

$$\dfrac{n!}{(n_1!)^{k_1} \ldots (n_s!)^{k_s}\cdot k_1! \ldots k_s! }$$