Композиция (комбинаторика)

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

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

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

Для дальнейшего обобщения, A- ограниченная композиция целого числа n для подмножества A (неотрицательных или положительных) целых чисел является упорядоченным набором одного или нескольких элементов в A , сумма которых равна n . ^[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.

Количество сочинений [ править ]

Использование последовательности Фибоначчи для подсчета {1,2} -ограниченных композиций n , например, количества путей, которыми можно подняться по лестнице длиной n , делая один или два шага за раз.

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

Размещение знака плюса или запятой в каждом из n  - 1 полей массива

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

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

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

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

${\displaystyle a_{1}+a_{2}+\ldots +a_{k}=n+k\quad \mapsto \quad (a_{1}-1)+(a_{2}-1)+\ldots +(a_{k}-1)=n}$

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

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

Однородные многочлены [ править ]

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

См. Также [ править ]

• Звезды и стержни (комбинаторика)

Ссылки [ править ]

• Хойбах, Сильвия; Мансур, Туфик (2009). Комбинаторика произведений и слов . Дискретная математика и ее приложения. Бока-Ратон, Флорида: CRC Press. ISBN 978-1-4200-7267-9. Zbl  1184.68373 .

Внешние ссылки [ править ]

• Калькулятор разбиения и состава