Композиция (комбинаторика) - Википедия - Composition (combinatorics)

В математика, а сочинение из целое число п это способ письма п как сумма последовательности (строго) положительные целые числа. Две последовательности, которые различаются по порядку их членов, определяют разные композиции своей суммы, в то время как считается, что они определяют одно и то же. раздел из этого числа. Каждое целое число имеет конечное количество различных композиций. Отрицательные числа не имеют составов, но 0 имеют одну композицию, пустую последовательность. Каждое положительное целое число п имеет 2^п−1 отличные композиции.

Биекция между 3 битами двоичные числа и композиции из 4

А слабый состав целого числа п похож на состав п, но позволяя членам последовательности быть равными нулю: это способ записи п как сумму последовательности неотрицательные целые числа. Как следствие, любое натуральное число допускает бесконечно много слабых композиций (если их длина не ограничена). Добавление числа членов 0 к конец слабого состава обычно не считается определением другого слабого состава; другими словами, предполагается, что слабые композиции неограниченно неявно расширяются с помощью членов 0.

Для дальнейшего обобщения Аограниченный состав целого числа п, для подмножества А целых чисел (неотрицательных или положительных), представляет собой упорядоченный набор одного или нескольких элементов в А чья сумма п.^[1]

Примеры

32 композиции из 6

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 2 + 1 + 1 + 1
. . .
1 + 5
6

11 разделов из 6

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
3 + 1 + 1 + 1
. . .
3 + 3
6

Шестнадцать композиций из пяти:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 3
2 + 2 + 1
2 + 1 + 2
2 + 1 + 1 + 1
1 + 4
1 + 3 + 1
1 + 2 + 2
1 + 2 + 1 + 1
1 + 1 + 3
1 + 1 + 2 + 1
1 + 1 + 1 + 2
1 + 1 + 1 + 1 + 1.

Сравните это с семью разделами из 5:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1.

Можно накладывать ограничения на части композиций. Например, пять композиций из 5 отдельных терминов:

5
4 + 1
3 + 2
2 + 3
1 + 4.

Сравните это с тремя разделами 5 на отдельные термины:

5
4 + 1
3 + 2.

Количество композиций

Обычно пустая композиция рассматривается как единственная композиция из 0, и нет композиций из отрицательных целых чисел.^п−1 композиции из п ≥ 1; вот доказательство:

Помещая знак плюса или запятую в каждый из п - 1 коробка массива

{ Displaystyle { большой (} , overbrace {1 , квадрат , 1 , квадрат , ldots , квадрат , 1 , квадрат , 1} ^ {n} , {большой )}}

производит уникальный состав п. И наоборот, каждая композиция п определяет расстановку плюсов и запятых. Поскольку есть п - 1 бинарный выбор, результат следует. Тот же аргумент показывает, что количество композиций п точно в k части (а k-сочинение) дается биномиальный коэффициент ${ displaystyle {n-1 select k-1}}$ . Обратите внимание, что суммируя все возможное количество частей, мы получаем 2^п−1 как общее количество композиций п:

{ displaystyle sum _ {k = 1} ^ {n} {n-1 select k-1} = 2 ^ {n-1}.}

Для слабых составов это число ${ Displaystyle {п + к-1 выбрать к-1} = {п + к-1 выбрать п}}$ , поскольку каждый k-Состав п + k соответствует слабому изп по правилу

{ Displaystyle a_ {1} + a_ {2} + ldots + a_ {k} = n + k quad mapsto quad (a_ {1} -1) + (a_ {2} -1) + ldots + (a_ {k} -1) = n}

Из этой формулы следует, что количество слабых составов п точно в k частей равно количеству слабых составов k - 1 точно в п + 1 детали.

За А-ограниченные композиции, количество композиций п точно в k частей задается расширенным биномиальным (или полиномиальным) коэффициентом ${ displaystyle { binom {k} {n}} _ {(1) _ {a in A}} = [x ^ {n}] left ( sum _ {a in A} x ^ {a } right) ^ {k}}$ , где квадратные скобки указывают на извлечение коэффициент из ${ Displaystyle х ^ {п}}$ в следующий за ним многочлен.^[2]

Однородные многочлены

Размерность векторного пространства ${ Displaystyle К [x_ {1}, ldots, x_ {n}] _ {d}}$ из однородный многочлен степени d в п переменные над полем K количество слабых составов п. Фактически, основу пространства составляет множество одночленов ${ Displaystyle x_ {1} ^ {d_ {1}} cdots x_ {n} ^ {d_ {n}}}$ такой, что ${ displaystyle d_ {1} + ldots + d_ {n} = d}$ . Поскольку показатели ${ displaystyle d_ {i}}$ равны нулю, то количество таких одночленов равно количеству слабых композиций п.