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

В математиці, композиція цілого n являє собою спосіб запису n в вигляді суми послідовності (строго) додатних цілих чисел. Дві послідовності, які розрізняються порядком їх членів, визначають різні композиції їх сум, в той час їх можна розглядати як однакові розбиття цього числа. Кожне ціле число має скінченне число різних композицій. Негативні числа не мають будь-яких композицій, але 0 має одну композицію — порожню послідовність. Кожне натуральне число n має 2n−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.

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

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

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

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

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

Для A-обмежених композицій кількість композицій n на k частинах можна отримати через розширений біноміальний (або поліноміальний) коефіцієнт .[2]

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

Посилання
  1. Heubach, Silvia; Mansour, Toufik (2004). Compositions of n with parts in a set. Congressus Numerantium 168: 33–51.
  2. Eger, Steffen (2013). Restricted weighted integer compositions and extended binomial coefficients. Journal of Integer Sequences 16.
  • 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.

Зовнішні посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.