Page 197 - 4496

k
C n k - C n s s 
Приклад 2. З групи в 15 чоловік потрібно відібрати
бригаду, в яку повинні входити не менше 5 чоловік. Скільки є
варіантів вибору?
Підрахуємо число несприятливих комбінацій вибору,
тобто складемо варіанти бригад з 1, 2, 3, 4 чоловік. Їх
кількість рівна:

2
C  C  C  C 15 = 15 +105 + 455 +1365 = 1940.
1
3
4
15
15
15
А загальна кількість бригад рівна 215 - 1. Різниця дає
число сприятливих комбінацій.
Для вирішення останньої задачі можна використовувати
так звані "рівноважні" коди. Рівноважними кодами довжини n
ваги k називаються двійкові послідовності довжини п, що
містять рівно k одиниць ( і n-k нулів). Число таких кодів
визначається виразом: Р(k, n-k). Випишемо, наприклад, всі
коди довжини 5 ваги 3:
1)1 1 100
2) 1 1 0 1 0
3) 1 10 0 1
4) 1 0 1 1 0
5) 1 0 1 0 1
6) 1 0 0 1 1
7) 0 1 1 1 0
8) 0 1 1 0 1
9) 0 1 0 1 1
10) 0 0 1 1 1

Легко помітити, що кожний стовпець містить 6 одиниць
і 4 нулі. Крім того, якщо узяти будь-які два стовпці і
поставити їх рядом, то завжди знайдеться комбінація 00.
Якщо ж узяти три будь-які стовпці, то комбінації 000 не буде.
Якщо тепер рахувати номери рядків 1), 2) ..., 10)
номерами ключів, а кожний стовпець розглядати як спосіб
видачі ключів конкретному члену комісії, то ми одержимо
рішення поставленої задачі при 5 членах комісії і пороговому
значенні k = 3. Якщо тепер побудувати таблицю кодів
довжини 7 ваги 4, ми одержимо рішення початкової задачі.

194