Число эквивалентностей на конечном множестве

[0n0]

Доказать что $p_{n+1}=\sum \limits_{i=0}^nC_n^ip_i $
где $p_n$-число эквивалентностей на множестве из $n$ элементов.

Как вообще найти число эквивалентностей на конечном множестве?

[patzer2097]

А попробуйте так. Выберите какой-то элемент (например $n+1$) из множества $\{1,\ldots,n+1\}$ и разберите все возможности, чему он может быть эквивалентен. Если ничему, то получаем $p_n$, т. е., $C^n_np_n$ разных эквивалентностей, если чему-то одному, то $C^{n-1}_np_{n-1}$ различных, и так далее. И получите как раз требуемую формулу

[VAL]

0n0 в сообщении #463569 писал(а):

Как вообще найти число эквивалентностей на конечном множестве?

Например, так:

$$ \sum_{k=1}^n\frac{1}{k!}\sum_{i=0}^k (-1)^i C_k^i(k-i)^n$$

[_hum_]

Извиняюсь, а разве соответствие между возможными отношениями эквивалентности на множестве и всеми возможными разбиениями этого множества не взаимнооднозначное?

[VAL]

_hum_ в сообщении #463849 писал(а):

Извиняюсь, а разве соответствие между возможными отношениями эквивалентности на множестве и всеми возможными разбиениями этого множества не взаимнооднозначное?

Разумеется, взаимно однозначное. Я бы даже сказал, биективное.

[_hum_]

Ну, тогда как вариант ответа на вопрос

Цитата:

Как вообще найти число эквивалентностей на конечном множестве?

- достаточно найти общее число разбиений этого множества.

[VAL]

_hum_ в сообщении #463867 писал(а):

Ну, тогда как вариант ответа на вопрос

Цитата:

Как вообще найти число эквивалентностей на конечном множестве?

- достаточно найти общее число разбиений этого множества.

Приведенная выше формула именно так и получена.

[alex1910]

А зачем это?

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