Виправлення надлишку

Ідея: Додайте, потім виправте

Порахуйте кожну групу окремо, потім відніміть пораховане двічі.

• Кратних $6$ до $300$: $50$
• Кратних $9$: $33$; обом, тобто $18$: $16$
• Разом: $50+33-16=67$

Формула: Включення й виключення

$|A\cup B\mid =\mid A\mid +\mid B\mid -\mid A\cap B|$

Додайте множини, потім один раз відніміть перетин.

Типова помилка: Обидва означає найменше спільне кратне

Ділиться на $6$ і $9$ не означає ділиться на $6\times 9=54$.

Натомість Беріть найменше спільне кратне, $18$. Добуток годиться, лише коли числа не мають спільного дільника.

Ідея: Чому знаки чергуються

Для більшої кількості множин: додайте окремі, відніміть пари, додайте трійки і так далі.

• Елемент у $3$ множинах: $\left(\genfrac{}{}{0ex}{}{3}{1}\right)-\left(\genfrac{}{}{0ex}{}{3}{2}\right)+\left(\genfrac{}{}{0ex}{}{3}{3}\right)=1$
• Кожен елемент зрештою пораховано рівно один раз

Ідея: Рахуйте те, чого не хочете

«Не поруч», «хоча б один» і «жодного» підказують доповнення.

• Пара не поруч у ряду з $7$: $7!-2\times 6!=3600$

Приклад: Жоден лист не у своєму конверті

$4$ листи лягають у $4$ підписані конверти. Скількома способами жоден не потрапить у свій?

1. Хоча б один правильно: $24-12+4-1=15$
2. Жодного правильно: $4!-15=9$

Формула: Безладдя

$D(n)=(n-1)\times (D(n-1)+D(n-2))$

Почніть із D(1) = 0 і D(2) = 1. Частка безладь швидко наближається до 1/e.

Швидка перевірка: 5 листів, 5 конвертів

Скількома способами $5$ листів можна покласти в $5$ підписаних конвертів так, щоб жоден не був у своєму?

Ідея: Проговорюйте виправлення

Назвіть множини, потім що пораховано двічі і як ви це виправляєте.

• Скажіть заздалегідь, що переходите до доповнення
• Завершіть випадком, який можна перелічити, як-от $D(3)=2$