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

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

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

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

Примеры

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

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, и композиции отрицательных целых чисел отсутствуют.Есть 2 ^{п -1} композиции n ≥ 1; вот доказательство:

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

{\big (}\,\overbrace {1\,\square \,1\,\square \,\ldots \,\square \,1\,\square \,1} ^{n}\,{\big )}

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

\sum _{k=1}^{n}{n-1 \choose k-1}=2^{n-1}.

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

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

Однородные полиномы

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

См. также

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

Ссылки

^ Хойбах, Сильвия ; Мансур, Туфик (2004). «Композиции из n частей в комплекте». Конгресс Нумерантиум . 168 : 33–51. CiteSeerX 10.1.1.484.5148 .
^ Эгер, Штеффен (2013). «Ограниченные взвешенные целочисленные композиции и расширенные биномиальные коэффициенты» (PDF) . Журнал целочисленных последовательностей . 16 .

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

Внешние ссылки

Калькулятор разделов и составов

[1] Хойбах, Сильвия ; Мансур, Туфик (2004). «Композиции из n частей в комплекте». Конгресс Нумерантиум . 168 : 33–51. CiteSeerX 10.1.1.484.5148 .

[2] Эгер, Штеффен (2013). «Ограниченные взвешенные целочисленные композиции и расширенные биномиальные коэффициенты» (PDF) . Журнал целочисленных последовательностей . 16 .

[1]

[2]