Комбінації (комбінаторика) - вибір підмножини незважаючи на порядок

Ми іноді робимо вибір з безлічі без урахування порядку. Такий вибір називається комбінацією. Якщо ви граєте в карти, наприклад, ви знаєте, що в більшості ситуацій порядок, в якому ви тримаєте карти, не має значення.

Приклад 1 Знайдіть всі комбінації 3-х букв, взятих з набору в 5 букв.

Коли ми знаходимо все комбінації з набору з 5 об'єктами, якщо ми беремо 3 об'єкти за один раз, ми знаходимо все 3-елементні підмножини. В такому випадку порядок об'єктів не розглядається. тоді,
називається одним і тим же набором як і.

підмножина
Безліч A є підмножиною B, і означає що A це підмножина і / або збігається з B якщо кожен елемент A є елементом B.

Елементи підмножина не впорядковані. Коли розглядаються комбінації, не розглядається порядок!

комбінація
Комбінація, що містить k об'єктів є підмножиною, що складається з k об'єктів.

Ми хочемо записати формулу для обчислення число поєднань з n об'єктів, якщо взято до об'єктів одночасно.

позначення комбінації
Число сполучень з n об'єктів, якщо взято до об'єктів одночасно, позначається n Ck.

Ми називаємо n Ckчісло поєднань. Ми хочемо записати загальну формулу для n Ck для будь-якого k ≤ n. По-перше, це вірно, що n Cn = 1, тому що безліч з n елементами має тільки одне подмножестов з n елементами, є саме безліч. По-друге, n C1 = n, тому що безліч з n елементами має тільки n підмножин з 1 елементом в кожному. Нарешті, n C0 = 1, тому що безліч з n елементами має тільки одне підмножина з 0 елементами, тобто порожня множина ∅. Щоб розглянути інші поєднання, давайте повернемося до прикладу 1 і порівняємо число комбінацій з числом перестановок.

Зверніть увагу, що кожна комбінація з 3-х елементів має 6, або 3. перестановок.
3! • 5 C3 = 60 = 5 P3 = 5 • 4 • 3,
so
.
Загалом, число поєднань з k елементів, вибраних з n об'єктів. n Ck раз перестановок цих елементів k. має дорівнювати числу перестановок n елементів по k елементів:
k! .n Ck = n Pk
n Ck = n Pk / k!
n Ck = (1 / k!). n Pk
n Ck =

Комбінації k об'єктів з n об'єктів
Загальна кількість комбінацій до елементів з n об'єктів позначається n Ck. визначається
(1) n Ck =,
або
(2) n Ck =

Інший тип позначення для n Ck це біномінальної коефіцієнт. Причина для такої термінології буде зрозуміла нижче.

Приклад 2 Обчислити, використовуючи формули (1) і (2).

Майте на увазі, що не означає n / k.

Приклад 3 Обчисліть і.

Рішення Ми використовуємо формулу (1) для першого виразу і формулу (2) для другого. тоді
,
використовуючи (1), і
,
іспоьлзуя формулу (2).

Зверніть увагу, що
,
і використовуючи результат прикладу 2 дає нам
.
Звідси випливає, що число 5-ти елементного підмножини з безлічі 7 елементів те ж саме, що і число 2-елементного підмножини безлічі з 7 елементів. Коли 5 елементів вибираються з набору, вони не включають в себе 2 елементи. Щоб побачити це, розглянемо безліч:

В цілому, ми маємо наступне. Цей результат дає альтернативний спосіб обчислення комбінації.

Підмножини розміру k і розміру
і n Ck = n Cn-k
Число підмножин розміру до безлічі з n об'єктами таке ж, як і число підмножин розміру n - к. Число сполучень k об'єктів з безлічі n об'єктів, таке ж як і число поєднань з n об'єктів, взятих одночасно.

Тепер ми будемо вирішувати завдання з комбінаціями.

Приклад 4 Мічиганський лотерея. Що проводиться в штаті Мічиган два рази в тиждень лотерея WINFALL має джек-пот, який, по крайней мере, дорівнює 2 млн. Доларів США. За один долар гравець може закреслити будь-які 6 чисел від 1 до 49. Якщо ці числа збігаються з тими, які випадають при проведенні лотереї, гравець виграє. (Джерело: Мічиганський лоттерея)
a) Скільки можливих комбінацій з 6-ти чисел в цій лотереї?
б) Припустимо, що 10 хвилин у Вас йде на те, щоб купити лотерейний квиток і закреслити 6 чисел. Скільки лотерейних квитків ви можете купити за 4 дні?
c) Скільки людей ви повинні були б найняти на 4 дні, щоб купити квитки з усіма можливими комбінаціями і бути впевненим, що ви виграєте?

Рішення
a) Тут немає порядку чисел. Ви закреслюєте кожні 6 чисел від 1 до 49. Тоді, число можливих комбінацій одно

b) По-перше, ми порахуємо число хвилин в 4-х днях:
4days • (24 год / 1 день). (60 хв / 1 ч) = 5760 хв.
Тоді, ви могли б купити 576 квитків за 4 дні.
c) Вам необхідно було б найняти 13,983,816 / 576, або близько 24278 чоловік щоб купити квитки з усіма можливими комбінаціями для гарантованого виграшу. (З умовою, що квитки можна купувати 24 години на добу.)

Приклад 5 Скільки комітетів може бути сформовано з групи 5-ти губернаторів і 7-ми сенаторів, якщо кожен комітет складається з 3-х губернаторів і 4-х сенаторів?

Рішення Три губернатора можуть бути обрані 5 C3 шляхами і 4 сенатора можуть бути обрані 7 C4 шляхами. Якщо ми використовуємо фундаментальний метод підрахунку, то отримаємо, що число можливих комітетів одно