- Считать варианты по правилам произведения и суммы
- Выбирать между размещениями и сочетаниями в зависимости от того, важен ли порядок
- Раскрывать бином с помощью треугольника Паскаля и находить любой коэффициент
Сколько существует разных 4-значных PIN-кодов банковской карты? На каждое место ставится одна из 10 цифр: 10 · 10 · 10 · 10 = 10 000 вариантов. Сколькими способами класс из 25 человек может выбрать 3 делегатов? 2300 способами! Выписать все варианты невозможно — комбинаторика учит считать их без перебора. На ней основаны теория вероятностей, криптография и программирование.
Правила произведения и суммы
- n₁, n₂, …, nₖчисло вариантов на каждом шаге
- Nобщее число вариантов
Правило произведения: если выбор делается в несколько последовательных шагов («и это, и то»), числа вариантов на каждом шаге перемножаются.
- n, mчисла вариантов в двух группах без общих элементов
Правило суммы: если выбирают «либо это, либо то» и группы не пересекаются, числа вариантов складываются.
а) В кафе 3 вида супа, 4 вторых блюда и 2 напитка. Сколько разных обедов из супа, второго блюда и напитка можно заказать?
б) Сколько существует трёхзначных чисел с различными цифрами?
в) Лейла выбирает одну книгу: один из 5 романов или один из 7 сборников стихов. Сколько у неё вариантов?
Показать решениеСкрыть решение
б) Разряд сотен: не может быть 0 — 9 вариантов. Десятки: любая цифра, кроме первой, включая 0 — 9 вариантов. Единицы: оставшиеся 8 цифр. 9 · 9 · 8 = 648.
в) «Либо роман, либо стихи» — правило суммы: 5 + 7 = 12.
Факториал и перестановки
n! = 1 · 2 · 3 · … · n — произведение всех натуральных чисел от 1 до n. По определению 0! = 1. Например, 5! = 120, 10! = 3 628 800 — факториал растёт очень быстро.
- nчисло различных элементов, которые переставляют
Число перестановок: количество способов расставить n различных элементов в ряд. На первое место — n вариантов, на второе — n − 1 и так далее.
а) Сколькими способами можно расставить на полке 5 разных книг?
б) 6 учеников встают в ряд. Сколько существует расстановок, если Айсель и Мурад должны стоять рядом?
Показать решениеСкрыть решение
б) «Склеим» Айсель и Мурада и будем считать их одним элементом: тогда переставляются 5 элементов — 5! = 120. Внутри пары они могут стоять 2! = 2 способами.
120 · 2 = 240. (Без условия было бы 6! = 720.)
Размещения и сочетания
- nобщее число элементов
- kчисло выбираемых и упорядочиваемых элементов (k ≤ n)
Размещения: из n элементов выбирают k и упорядочивают — порядок важен. Справа стоят k убывающих множителей, начиная с n.
- nобщее число элементов
- kчисло выбираемых элементов; порядок не учитывается
Сочетания: из n элементов просто выбирают k — порядок не важен. Каждая группа из k элементов в размещениях посчитана k! раз, поэтому делим на k!.
| Что делаем? | Порядок важен? | Формула | Пример |
|---|---|---|---|
| переставляем все n элементов | да | Pₙ = n! | 5 книг на полке: 120 |
| выбираем k из n и упорядочиваем | да | Aₙᵏ | староста, заместитель, секретарь из 25: 13 800 |
| просто выбираем k из n | нет | Cₙᵏ | 3 делегата из 25: 2300 |
| на каждое из k мест — один из n вариантов (с повторениями) | да | nᵏ | 4-значный PIN: 10⁴ = 10 000 |
В классе 25 учеников.
а) Сколькими способами можно выбрать старосту, его заместителя и секретаря?
б) Сколькими способами можно выбрать 3 делегатов на конференцию?
Показать решениеСкрыть решение
б) Три делегата равноправны, порядок не важен: C₂₅³ = A₂₅³ / 3! = 13 800 / 6 = 2300.
- n, kцелые неотрицательные числа, k ≤ n
Первое свойство: выбрать k элементов — то же самое, что «не выбрать» остальные n − k. Второе свойство — правило построения треугольника Паскаля: C₅² + C₅³ = 10 + 10 = 20 = C₆³.
В кружке 6 мальчиков и 4 девочки. Выбирают команду из 5 человек.
а) Сколько команд, в которых ровно 2 девочки?
б) Сколько команд, в которых хотя бы одна девочка?
в) Из кружка случайно выбирают 2 человек. Какова вероятность, что обе — девочки?
Показать решениеСкрыть решение
б) Через противоположное событие: «хотя бы одна девочка» = все − «без девочек». C₁₀⁵ − C₆⁵ = 252 − 6 = 246.
в) Всех пар: C₁₀² = 45, пар из двух девочек: C₄² = 6. P = 6/45 = 2/15 ≈ 0,13.
Бином Ньютона и треугольник Паскаля
- nнатуральный показатель
- Cₙᵏбиномиальные коэффициенты
Бином Ньютона. Общий член: Tₖ₊₁ = Cₙᵏ · aⁿ⁻ᵏ · bᵏ. В разложении n + 1 слагаемое, сумма коэффициентов равна 2ⁿ. В разложении (a − b)ⁿ знаки чередуются: +, −, +, …
| n | Биномиальные коэффициенты | Сумма |
|---|---|---|
| 0 | 1 | 1 = 2⁰ |
| 1 | 1 1 | 2 = 2¹ |
| 2 | 1 2 1 | 4 = 2² |
| 3 | 1 3 3 1 | 8 = 2³ |
| 4 | 1 4 6 4 1 | 16 = 2⁴ |
| 5 | 1 5 10 10 5 1 | 32 = 2⁵ |
| 6 | 1 6 15 20 15 6 1 | 64 = 2⁶ |
а) Раскройте (x + 2)⁴.
б) Найдите коэффициент при x² в разложении (2x − 1)⁵.
Показать решениеСкрыть решение
(x + 2)⁴ = x⁴ + 4 · 2x³ + 6 · 4x² + 4 · 8x + 16 = x⁴ + 8x³ + 24x² + 32x + 16.
б) Общий член: C₅ᵏ · (2x)⁵⁻ᵏ · (−1)ᵏ. Для x² нужно 5 − k = 2 ⇒ k = 3.
C₅³ · 2² · (−1)³ = 10 · 4 · (−1) = −40.
Главное
- Правило произведения: варианты последовательных шагов перемножаются; правило суммы: варианты «либо—либо» складываются.
- Pₙ = n! — число всех перестановок n элементов.
- Если порядок важен — Aₙᵏ = n!/(n − k)!, если нет — Cₙᵏ = n!/(k!(n − k)!).
- В задачах «хотя бы один» проще вычесть противоположный случай из общего числа.
- Коэффициенты (a + b)ⁿ — n-я строка треугольника Паскаля; общий член Cₙᵏaⁿ⁻ᵏbᵏ.
Проверь себя
Вопросов: 10. Каждый правильный ответ приносит XP.