Сполуки (комбінації)

Розглянемо такі дві задачі. Скількома способами в класі, у якому 30 учнів, можна вибрати старосту та його заступника? Скількома способами в цьому класі можна призначити двох чергових?

Відповідь до першої задачі вам відома: це кількість 2-елементних упорядкованих підмножин 30-елементної множини, тобто $A_{30}^2$ . Щоб розв’язати другу задачу, треба визначити кількість 2-елементних підмножин 30-елементної множини (саме підмножин, а не впорядкованих підмножин). Кожну з таких підмножин називають сполукою (комбінацією) з 30 елементів по 2 елементи.

Означення

📐Означення — Сполука (комбінація)

Будь-яку $k$ -елементну підмножину заданої $n$ -елементної множини називають сполукою (комбінацією) з $n$ елементів по $k$ елементів.

Кількість усіх можливих сполук із $n$ елементів по $k$ елементів позначають символом $C_n^k$ , використовуючи першу літеру французького слова combinaison — комбінація.

Формула

Розглянемо деяку $n$ -елементну множину. Кількість її $k$ -елементних підмножин дорівнює $C_n^k$ . Із кожної такої підмножини можна утворити $k!$ упорядкованих $k$ -елементних підмножин. Отже, кількість усіх $k$ -елементних упорядкованих підмножин заданої $n$ -елементної множини дорівнює $C_n^k \cdot k!$ , тобто $A_n^k = C_n^k \cdot P_k$ . Звідси

C_n^k = \frac{A_n^k}{P_k}.

⚡Теорема — Формула кількості сполук

Для будь-яких натуральних $n$ і $k$ таких, що $k \leqslant n$ , справедлива формула

C_n^k = \frac{n!}{(n-k)!\, k!}

Зазначимо, що ця формула залишається справедливою і для випадків, коли $k = 0$ або $n = 0$ :

C_n^0 = \frac{n!}{n! \cdot 0!} = 1, \qquad C_0^0 = \frac{0!}{0! \cdot 0!} = 1.

Властивості сполук

⚡Теорема — Симетрія сполук

C_n^k = C_n^{n-k}

Вибираючи $k$ -елементну підмножину $A$ з $n$ -елементної множини $M$ , ми тим самим однозначно задаємо $(n-k)$ -елементну підмножину $M \setminus A$ . Отже, кількість способів вибору $k$ -елементної підмножини дорівнює кількості способів вибору $(n-k)$ -елементної підмножини.

✎Приклад 1 — Геометричне доведення симетрії

Умова. Доведіть, що $C_n^k = C_n^{n-k}$ .

Розв’язання. Формулу при $n > k > 0$ можна довести за допомогою геометричної інтерпретації. Розглянемо прямокутник розміром $m \times k$ , $m \in \mathbb{N}$ , $k \in \mathbb{N}$ , розбитий на $mk$ квадратів. Нехай це схема вулиць деякого міста. Кількість різних найкоротших маршрутів, що ведуть із пункту $A$ до пункту $B$ , дорівнює $C_{m+k}^k$ .

Якщо позначити $m + k = n$ , то отримаємо формулу $C_n^k = C_n^{n-k}$ .

✎Приклад 2 — Сума всіх сполук

Умова. Доведіть, що $C_n^0 + C_n^1 + C_n^2 + \ldots + C_n^n = 2^n$ .

Розв’язання. Ліва частина даної рівності — це кількість підмножин $n$ -елементної множини. У п. 23 ми показали, що ця кількість дорівнює $2^n$ .

Тотожність Паскаля

⚡Теорема — Тотожність Паскаля

C_{n+1}^k = C_n^{k-1} + C_n^k

Доведення. Розглянемо $(n + 1)$ -елементну множину. Зафіксуємо в ній деякий елемент $a$ . Усі $k$ -елементні підмножини розіб’ємо на два типи: які містять елемент $a$ і які його не містять.

Підмножини першого типу формуються в результаті вибору $k - 1$ елемента з $n$ елементів (адже один елемент їм обов’язково належить — це елемент $a$ ). Тому кількість підмножин першого типу дорівнює $C_n^{k-1}$ .

Підмножини другого типу формуються в результаті вибору з $n$ елементів (адже елемент $a$ їм не належить) $k$ елементів. Їхня кількість дорівнює $C_n^k$ .

Отримали, що кількість $k$ -елементних підмножин заданої $(n+1)$ -елементної множини дорівнює $C_n^{k-1} + C_n^k$ . Тому $C_{n+1}^k = C_n^{k-1} + C_n^k$ .

✏Вправа — Задачі на сполуки

У класі 29 учнів. Скількома способами можна сформувати команду з 5 осіб для участі в математичній олімпіаді?
На площині позначено 10 точок так, що жодні три з них не лежать на одній прямій. Скільки існує трикутників із вершинами у цих точках?
У шаховій секції займаються 5 дівчат і 12 хлопчиків. Скількома способами можна сформувати команду з 2 дівчат і 5 хлопчиків для участі в змаганнях?