Підмножини й шляхи

Ідея: Приберіть порядок

Комітет це розклад без назв посад.

• $12\times 11\times 10=1320$ упорядкованих списків
• Кожна група з $3$ трапляється $3!=6$ разів
• Комітетів: $\frac{1320}{6}=220$

Формула: Комбінації з n по k

$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!\times (n-k)!}$

Вишикуйте n людей і візьміть перших k. Перестановки всередині будь-якої групи нічого не змінюють.

Ідея: Обирайте меншу частину

Обрати, хто входить, те саме, що обрати, хто лишається поза.

• $\left(\genfrac{}{}{0ex}{}{12}{3}\right)=\left(\genfrac{}{}{0ex}{}{12}{9}\right)=220$
• Рахуйте з меншим із k та n − k

Типова помилка: C(n,k), коли ролі різні

Комітет із $3$ людей із головою це не $\left(\genfrac{}{}{0ex}{}{12}{3}\right)$.

Натомість Тест обміну: поміняйте $2$ людей; якщо наслідок змінився, ролі важливі. Тут $\left(\genfrac{}{}{0ex}{}{12}{3}\right)\times 3=660$.

Формула: Правило Паскаля

$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$

Розділіть за одним елементом: він або входить, або ні.

Ідея: Усі підмножини одразу

Кожен із n елементів або входить, або ні, тож підмножин $2^n$.

• $5$ елементів: $2^5=32$ підмножини
• З одним трейдером чи без: $\left(\genfrac{}{}{0ex}{}{11}{2}\right)+\left(\genfrac{}{}{0ex}{}{11}{3}\right)=220$

Приклад: Шляхи на сітці

Ідіть від $(0,0)$ до $(5,4)$ лише праворуч або вгору. Скільки шляхів?

1. Кожен шлях має $5+4=9$ кроків
2. Оберіть, які $4$ ведуть угору: $\left(\genfrac{}{}{0ex}{}{9}{4}\right)=126$

Швидка перевірка: Через точку

Скільки шляхів від $(0,0)$ до $(5,4)$, праворуч або вгору, проходять через $(2,1)$?

Ідея: Проведіть співрозмовника

Скажіть, чи важливий порядок, і покажіть тест обміну одним реченням.

• Коли ділите, скажіть, що саме прибираєте
• На сітці назвіть довжину шляху, потім які кроки обираєте