4
1

Несколько раз натыкалась на задачу подсчета числа всех возможных разбиений множества. Похоже, простой формулы там нет. Но, может, хотя бы асимптотика известна?

Точная формулировка такая. Множество из n элементов можно разбить на подмножества, причем произвольным образом. Возможны разбиения из любого числа подмножеств:как n (все одноэлементные), так и 1 (множество берется целиком). Порядок самих подмножеств не важен.
Например, в множестве (1, 2, 3, 4} имеется 12 вариантов разбиения:
{1}, {2}, {3}, {4};
{1, 2}, {3}, {4};
{1, 3}, {2}, {4};
{1, 4}, {2}, {3};
{2, 3}, {1}, {4};
{2, 4}, {1}, {3};
{3, 4}, {1}, {2};
{1, 2, 3}, {4};
{1, 2, 4}, {3};
{1, 3, 4}, {2};
{2, 3, 4}, {1};
{1, 2, 3, 4}.

задан 23 Ноя '12 0:44

элементы множества всегда разные?

(23 Ноя '12 1:06) chameleon

Ну да! На то оно и множество. Эта задача возникла у меня, когда я рассказывала студентам о своей работе в КБ, где мы рассчитывали маршруты развозки молока и хлеба. Надо было разбить все заказы на подмножества (с учетом грузоподъемности машин), а потом еще указать оптимальный объезд в каждом. Вот я и хотела показать, что просто перебрать все разбиения на подмножества - нереально за короткое время.

(23 Ноя '12 1:41) DocentI

Кстати, в приведенном примере имеется 15 вариантов разбиения. Кроме уже написанных, такие:
{1, 2}, {3, 4};
{1, 3}, {2, 4};
{1, 4}, {2, 3}.

(23 Ноя '12 2:03) chameleon

Точно, 15! Я чувствую, что чего-то не хватает, потому что со студентами вроде получили больше!

(23 Ноя '12 12:18) DocentI
10|600 символов нужно символов осталось
2
ссылка

отвечен 24 Ноя '12 20:02

Большое спасибо! Очень ценная информация! Я чувствовала, что там что-то порядка факториала или $%(n/a)^n$%. В общем, достаточно, чтобы исключить полный перебор.

(24 Ноя '12 20:13) DocentI
10|600 символов нужно символов осталось
2

Простую формулу вывести пока не смог, за то могу предложить рекурсивную.
Пусть $%K_m^n$% - число разбиений множества из n элементов на m подмножеств, а $%Q_n$% - число разбиений множества из n элементов на любое количество подмножеств (т.е. то, что нужно по условию). При увеличении n на 1 мы можем разместить "новый" элемент двумя способами: или сформировать из него отдельное подмножество, или добавить его к одному из подмножеств с "предыдущего шага". То есть, $%K_m^{n+1}=K_{m-1}^n+mK_m^n$%. Добавив начальные условия, получим рекурсивную формулу: $$\begin{cases} K_0^n=0\\ K_{n+1}^n=0\\ K_1^1=1\\ K_m^{n+1}=K_{m-1}^n+mK_m^n\\ Q_n=\sum_{m=1}^n{K_m^n} \end{cases}$$ Что же касается асимптотики, то начиная с n=61 число разбиений превышает $%10^n$%.
Первые 15 чисел данной последовательности: 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545.
График $%\log_{10}Q_n$%:
log 10 Qn

ссылка

отвечен 23 Ноя '12 2:46

изменен 23 Ноя '12 3:14

подозреваю, что там не степенная зависимость, а факториальная. Уж больно много случаев.
Может, хоть оценку кукаю-нибудь придумаете (оценку снизу, чтобы поразить грандиозностью величин).

(24 Ноя '12 1:48) DocentI

Там, насколько я знаю, асимптотика имеет порядок $$\left(\frac{Cn}{ln n}\right)^n,$$ то есть это меньше факториала, хотя и близко.

Верхнюю оценку $%B_n\le n!$%, как я сейчас осознал, легко вывести прямо из определения. Если есть разбиение, то выпишем в каждой группе числа в порядке возрастания, а группы упорядочим по их наименьшим элементам. Это приводит к перестановке, по которой прообраз однозначно восстанавливается.

А вот хорошую верхнюю оценку было бы интересно получить. Типа, скажем, $%n^{n/2}$%, начиная с некоторого номера.

(28 Янв '13 21:02) falcao
10|600 символов нужно символов осталось
0

Насчёт получения оценки снизу можно применить следующее соображение. Рассмотрим числа Белла с чётным номером $%2n$%. Ясно, что множество всех разбиений включает в себя множество разбиений на $%n$% пар. Для последней задачи ответ хорошо известен, и получается неравенство $$B_{2n}\ge(2n-1)(2n-3)\cdot\,\cdots\,\cdot3\cdot1.$$ Отсюда становится понятно, что числа Белла растут весьма быстро -- порядка корня из факториала, как минимум.

ссылка

отвечен 29 Янв '13 0:00

10|600 символов нужно символов осталось
0

N(n1,n2,n3,...,nk)=n!/(n1!n2!n3!...nk!)

ссылка

отвечен 28 Июн '14 19:12

@Yegor: это совсем другая формула (перестановки с повторениями). Она к заданному вопросу отношения не имеет.

(28 Июн '14 21:15) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×813

задан
23 Ноя '12 0:44

показан
4876 раз

обновлен
28 Июн '14 21:15

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru