Сколько существует разбиений на классы эквивалентности?

[Dims]

Пусть имеется набор элементов 1, 2, ... Н. Мы имеем возможность разбить эти элементы на классы эквивалентности, то есть, на группы, внутри которых считать элементы "равными" друг другу, а между группами -- "не равными".

Например, мы можем постановить, что все Н элементов равны. Тогда у нас будет один класс эквивалентности, в котором будут находиться все элементы.

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

Ещё пример: мы можем постановить, что элементы 1, 2, ..., Н-1 равны друг другу, а элемент Н не равен им. Тогда у нас будет два класса эквивалентности.

Каждый из трёх примеров показывает одно из возможных "разбиений" на классы эквивалентности. Сколько всего возможных разбиений множества из Н различных элементов существует?

Не могу сообразить.

[незваный гость]

$P(0)=P(1)=1$,
$P(n) = \sum\limits_{k=1}^{n} C_{n-1}^{k-1} P(n-k)$

OEIS: A000110

[Dims]

Спасибо. А нерекурсивной формулы нет?

[незваный гость]

Некоторый обзор в комментариях по ссылке.

[maxal]

Кстати, если зафиксировать $k$ - число классов, то число разбиений $n$ элементов равно числу Стирлинга 2-го рода $S(n,k)$. Соответственно, общее число всех разбиений, оно же число Белла, равно

$$B(n) = \sum_{k=0}^n S(n,k).$$

[Dims]

Нифига себе какая сложность лезет!

[Dims]

А рассмотрим такую вариацию.

Есть две группы объектов, в первой M штук, во второй N штук. Внутри каждой группы объекты различны. А вот различие/равенство объектов между группами -- неизвестны.

Сколькими способами можно провести эти отношения?

Ясно, что объект из первой группы может быть равен только одному объекту из второй группы, либо не равен никому.

Допустим M<N.

Рассмотрим сперва случаи, когда каждый из M равен кому-то из N.

Тогда равенство из первого объекта можно будет провести N способоами, из второго N-1 и так далее. Равенство из последнего объекта получится провести N-M+1 = N-(M-1) способами.

Получится N!/(N-M)! так?

А как учесть случаи, когда равенства не проводятся?

[maxal]

Dims писал(а):

Есть две группы объектов, в первой M штук, во второй N штук. Внутри каждой группы объекты различны. А вот различие/равенство объектов между группами -- неизвестны.

Сколькими способами можно провести эти отношения?

$$\sum_{k=0}^{\min\{M,N\}} \binom{N}{k} \binom{M}{k} k! = \sum_{k=0}^{\min\{M,N\}}\frac{M!N!}{(M-k)!(N-k)!k!}$$

Здесь $k$ соответствует числу равенств между элементами классов.