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

В математиці, композиція цілого n являє собою спосіб запису n в вигляді суми послідовності (строго) додатних цілих чисел. Дві послідовності, які розрізняються порядком їх членів, визначають різні композиції їх сум, в той час їх можна розглядати як однакові розбиття цього числа. Кожне ціле число має скінченне число різних композицій. Негативні числа не мають будь-яких композицій, але 0 має одну композицію — порожню послідовність. Кожне натуральне число n має 2ⁿ⁻¹ різних композицій.

Бієкція між 3-бітними двійковими числами і композиціями 4

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

Для подальшого узагальнення, A-обмежена композиція цілого числа n для підмножини A (без невід'ємних або додатних) цілих чисел являє собою упорядкований набір з одного або декількох елементів в A, сума яких дорівнює n.

Приклади

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.

Число композицій

За домовленістю порожню композицію вважають єдиною композицією 0, і що немає композицій від'ємних цілих чисел. Існує 2ⁿ⁻¹ композицій чисел n ≥ 1. Доведення:

Розміщення знака «плюс» або коми в кожному з n − 1 комірок масиву

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

відповідає унікальній композиції n. І навпаки, кожна композиція n визначає розподіл знаків плюс і ком. Оскільки для кожного з n − 1 місця у нас є дві можливості, то загальна кількість комбінацій відповідно до правила добутку буде 2ⁿ⁻¹, що і потрібно довести. Той же аргумент показує, що кількість композицій n складених точно з k частин можна отримати за допомогою біноміального коефіцієнту ${n-1 \choose k-1}$. Далі, підсумовуючи всі можливі кількості частин, у підсумку отримуємо 2ⁿ⁻¹ як загальну суму композицій n:

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

Для слабких композицій це кількість буде ${n+k-1 \choose k-1}$, бо кожна k-композиція n + k відповідає одному з n за правилом [a + b + … + c = n + k] → [(a − 1) + (b − 1) + … + (c − 1) = n].

Для A-обмежених композицій кількість композицій n на k частинах можна отримати через розширений біноміальний (або поліноміальний) коефіцієнт ${\binom {k}{n}}_{(1)_{a\in A}}=[x^{n}](\sum _{a\in A}x^{a})^{k}$.

Дивиться також

• Зірки та риски

Посилання

• Heubach, Silvia; Mansour, Toufik (2009). Combinatorics of Compositions and Words. Discrete Mathematics and its Applications. Boca Raton, FL: CRC Press. ISBN 978-1-4200-7267-9. Zbl 1184.68373.

Зовнішні посилання

• Калькулятор розбиттів і композицій [Архівовано 30 Червня 2018 у Wayback Machine.]