Розбивки

Розбивки. Набір цілих позитивних чисел називається розбивкою числа п, якщо п = .Числа (і = 1, 2,..., k) називають частинами, а їхню суму п — характеристикою розбивки. При підрахунку числа можливих розбивок можуть враховуватися додаткові умови — тип розбивки, величини і загальне число частин, число повторень.

Приклад. Для числа 4 є 5 розбивок без обмежень. (4, 31, 22, 211, 1111) і вісім розбивок з урахуванням порядку частин (4,31, 13, 22, 211, 121, 112, 1111). Число 8 розбивається на три частини п'ятьма способами: 611, 521, 431, 422, 332.

Якщо прийняти як твірну функцію для розбивки числа п без обмежень р(п) багаточлен p(x) = p(0) + p(1) + p(2) то внесок частини величини k визначається множником () і, отже

р (х) = (1+ х+

З цього співвідношення виходять твірні функції при обмеженнях, що накладаються на чисельні значення частин. Якщо всі частини розбивки не перевершують числа k, то

Для розбивок, усі частини яких різні, є і (х) =(1+ х) (1+ x²)(1+ х ³) ..., а розбивки на непарні частини перелічуються функцією

Приклад. Число способів розміну 8 копійок монетами достоїнством у 1, 2, 3 і 5 копійок. Для цього випадку p(х)=(1+х+х²+...)* *(1+х²+х⁴+...)(1+х³+х⁶+...)(1+х⁵+x¹⁰+...). Коефіцієнт при x⁸ дорівнює 13, що і дає шукані розбивки: 53, 521, 51³, З²1², 3²2, 32²1, 321³, 31⁵, 2⁴, 2³1², 2²1⁴, 21⁶,1⁸ (запис аq означає, що а входить у розбивку q раз). Якщо задати, щоб усі частини були різними, то і(х)=(1+x)(l+х²)(1+х³)(1+х⁵), відкіля знаходимо і(8) = 2 (відповідні розбивки 53 і 521).

Число розбивок п об'єктів на k частин можна визначити за допомогою рекурентної формули

р(п, k) = р(п - k, k) + р(п - k, k - 1) + ...+р(п - k, 1)

при граничних умовах р(n, k) = 0, для n < k і p(k, k) = р(n, 1) = 1.

Приклад. Якщо n = 7 і k = 3, маємо p(7,3) = p(4,3) + р(4,2) + р(4,1); р(4,2) = р(2,2) + p (2,1) = 1 + 1 = 2; р(4,3) = p(1,3) + р(1,2)+ +p(1,1) = 1; р(7,3) = 1 +2+ 1 = 4. Отже, маємо чотири розбивки числа 7 на три частини - 511, 421, 331, 322.

Контрольні запитання

1. Що називають поліноміальною твірною функцією?

2. Що є більш загальним – біном Ньютона чи енумератор?

3. Що таке експоненціальна твірна функція?

4. Що проголошує принцип включення і виключення?

5. Яка формула включення і виключення?

6. Яка різниця між символічним методом, принципом перехресної класифікації, методом решета, формулою обернення?

7. Що можуть дати діаграми Венна для принципу включення і виключення? Як ще графічно проілюструвати принцип включення і виключення?

8. Що є розбивкою?

9. Як зв’язати розбивки з рекурентними співвідношеннями?