Каково количество всех перестановок в наборе питания?

Question

Для набора размеров n размер его электропитания 2^n. Создайте все перестановки для каждого элемента набора мощности. Комплект электропитания для набора {a, b} - {{}, {a}, {b}, {a,b}}. Создайте все перестановки на каждом наборе, мы получим {(),(a),(b),(a,b),(b,a)}. Таким образом, число всех подстановочных перестановок для набора мощности, генерируемого из 2-элементного набора, равно 5. И такое число для набора из 3 элементов равно 16. Существует ли формула для этого числа, определяемая в терминах n?

Answer 1

Прежде всего, рассмотрите комплект мощности. Количество наборов размера k (для некоторого 0 <= k <= n) в наборе мощности является

n choose k = n!/(k! * (n - k)!) 

Действительно, если суммировать количество наборов для всех k, мы получаем 2^n см Wolfram Alpha.

Сколько перестановок имеет набор размеров k есть? Хорошо, k!. Таким образом, если мы подключить что мы освободи k! из знаменателя и суммы n!/(n-k)! для всех k, что

n! * Sum(1/k!, 0 <= k <= n) 

Опять же, увидеть результат на Wolfram Alpha.