2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Число группировок
Сообщение18.02.2010, 23:15 
Как найти число группировок из n при условии, что размер группы ограничен c обоих сторон.
Есть ли простая формула?

 
 
 
 Re: Число группировок
Сообщение19.02.2010, 07:45 
Аватара пользователя
Что Вы называете группировкой?
Упорядоченную, неупорядоченную выборку или что-то иное?

 
 
 
 Re: Число группировок
Сообщение19.02.2010, 12:29 
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 группировки.

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

 
 
 
 Re: Число группировок
Сообщение19.02.2010, 13:31 
Аватара пользователя
Aks1 в сообщении #290345 писал(а):
Неупорядоченную. По сути, набор сочетаний, исчерпывающий множество.

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

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

 
 
 
 Re: Число группировок
Сообщение19.02.2010, 17:33 
Аватара пользователя
Верно ли я пронимаю, что "огарничение=равенство" означает фиксирование одного и того числа элементов в каждом классе разбиения, за исключением одного возможного остаточного хвостика?

Если да, то всё совсем просто. Пусть 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 "полных классов разбиения".

 
 
 
 Re: Число группировок
Сообщение19.02.2010, 20:00 
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!}$

 
 
 
 Re: Число группировок
Сообщение19.02.2010, 22:26 
Аватара пользователя

(Оффтоп)

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

 
 
 
 Re: Число группировок
Сообщение20.02.2010, 18:27 
Аватара пользователя
Здесь ошибка
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! }$$

 
 
 
 Re: Число группировок
Сообщение20.02.2010, 18:36 
В задании не сказано, что можно переставлять только равномощные классы.
Но если можно переставлять только рывномощные классы, то последняя формула верна.

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

 
 
 
 Re: Число группировок
Сообщение21.02.2010, 11:15 
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 --

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

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

 
 
 
 Re: Число группировок
Сообщение22.02.2010, 15:04 
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! }$$

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

 
 
 
 Re: Число группировок
Сообщение22.02.2010, 15:26 
Аватара пользователя
Вот в переборе всех допустимых типов разбиения сложность и заключается - их может и много ведь оказаться.

 
 
 
 Re: Число группировок
Сообщение24.02.2010, 09:32 
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! }$$

 
 
 [ Сообщений: 22 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group