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

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

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

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

• 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.

Обратите внимание, что древние санскритские мудрецы обнаружили за много лет до Фибоначчи, что количество композиций любого натурального числа n как суммы 1 и 2 является n-ным числом Фибоначчи! Обратите внимание, что это не общие композиции, как определено выше, поскольку числа ограничены только 1 и 2.

• 1=1 (1)
• 2=1+1=2 (2)
• 3=1+1+1=1+2=2+1 (3)
• 4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2 (5)
• 5=1+1+1+1+1=1+1+1+2=1+1+2+1=1+2+1+1=2+1+1+1=1+2+2= 2+1+2=2+2+1 (8)
• 6 будет иметь 13 комбинаций и т.д.

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

Числа композиций n  +1 в k  +1 упорядоченных разбиений образуют треугольник Паскаля

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

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

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

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

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

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

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

${\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}}$

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

Размерность векторного пространства однородного многочлена степени d от n переменных над полем K — это число слабых композиций d на n частей. Фактически, базис пространства задается набором мономов, таких что . Поскольку показатели степеней могут быть равны нулю, то число таких мономов в точности равно числу слабых композиций d . ${\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}}$

Смотрите также

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

Ссылки

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

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

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

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