Page 191 - 4496

допомогою 0 і 1, причому 1 відповідають предметам, а 0
виконують функцію роздільників. Тоді записавши k одиниць і
додавши n - 1 нуль, ми одержимо комбінацію, при якій
вибираються k предметів першого типа і жодного предмету
решти типів. Переставляючи всіма способами ці k одиниць і n
- 1 нуль, ми кожного разу одержуватимемо деяку розстановку,
що складається з k предметів. Тоді
k
Р(k, n-1)= (k + n - 1)!/(k!(n - 1)!) = C n k 1 (5.8)

5.9 Властивості чисел поєднань
Приведемо деякі властивості числових поєднань, які
часто використовуються при перетвореннях формул
комбінаторики.
C  C n k
k
1. n n
C  C k 1  C k
k
2. n n 1 n 1
C  C  C  ...  C  2 n
0
2
n
1
3. n n n n
Перша властивість абсолютно очевидна. Друга легко
доводиться, якщо обидва члени правої частини представити
по формулі (7). Третю властивість можна довести методом
математичної індукції. Для прикладу, при n = 2 маємо:
C 2 0  C 1 2  C 2 2  1 2  1 2 2 .
Для n = 3 одержимо:
C 3 0  C 1 3  C 3 2  C 3 3  1 3 3 1 2 3

5.10 Комбінаторні задачі з обмеженнями

Розглянемо декілька типів задач, в яких на комбінації
накладаються певні обмеження.
а) Задача про левів і тигрів. Є 5 левів і 4 тигри.
Необхідно їх розставити в ряд, але при цьому відомо, що тигр
не може йти спокійно за тигром. Тоді розставляємо левів з
проміками (їх буде 6) і в них розставимо тигрів. Таким чином,

188