Сколько разных разделов с ровно n частями можно сделать из набора с k-элементами?

Question

Сколько разных разделов, состоящих ровно из двух частей, можно сделать из набора {1,2,3,4}?В этом списке 4 элемента, которые нужно разбить на 2 части.Я написал их и получил в общей сложности 7 разных возможностей:

1. {{1}, {2,3,4}}
2. {{2}, {1,3, 4}}
3. {{3}, {1,2,4}}
4. {{4}, {1,2,3}}
5. {{1,2}, {3,4}}
6. {{1,3}, {2,4}}
7. {{1,4}, {2,3}}

Теперь я должен ответить на тот же вопрос для множества {1,2,3, ..., 100}.В этом списке 100 элементов, которые нужно разбить на 2 части.Я знаю, что наибольший размер части раздела может быть 50 (это 100/2), а наименьший - 1 (поэтому одна часть имеет 1 номер, а другая - 99).Как я могу определить, сколько существует различных возможностей для разделов двух частей, не выписывая посторонние списки всех возможных комбинаций?Можно ли упростить ответ до факториала (например, 12!)?
Существует ли общая формула, которую можно использовать, чтобы найти, сколько разных разбиений с ровно n частями можно сделать из набора с k-элементами?

Answer 1

1) stackoverflow - это программирование. Ваш вопрос принадлежит https://math.stackexchange.com/ царству.

2) Существует 2 ⁿ подмножеств набора из n элементов (поскольку каждый из n элементов может быть или не содержаться в конкретном подмножестве). Это дает нам 2 ^n-1 различных разбиений набора n-элементов на два подмножества. Один из этих разделов является тривиальным (одна часть является пустым подмножеством, а другая часть - всем исходным набором), и из вашего примера кажется, что вы не хотите считать тривиальный раздел. Таким образом, ответ 2 ^n-1 -1 (что дает 2 ³ -1 = 7 для n = 4).

Answer 2

Общий ответ для n частей и k элементов будет следующим: число Стирлинга второго рода S (k, n) .

Пожалуйста, имейте в виду, что обычное соглашение с nобщее количество элементов, таким образом S (n, k)

Вычисление общей формулы довольно некрасиво, но выполнимо для k = 2 (с общими обозначениями):

Таким образом, S (n, 2) = 1/2 ((+1) * 1 * 0 ⁿ + (- 1) * 2 * 1 ⁿ + (+1) * 1 * 2 ⁿ ) = (0-2 + ​​2 ⁿ ) / 2 = 2 ^n-1 -1