Сколько существует разных 4-значных PIN-кодов банковской карты? На каждое место ставится одна из 10 цифр: 10 · 10 · 10 · 10 = 10 000 вариантов. Сколькими способами класс из 25 человек может выбрать 3 делегатов? 2300 способами! Выписать все варианты невозможно — комбинаторика учит считать их без перебора. На ней основаны теория вероятностей, криптография и программирование.
Правила произведения и суммы
Где
- n₁, n₂, …, nₖ
- число вариантов на каждом шаге
- N
- общее число вариантов
Правило произведения: если выбор делается в несколько последовательных шагов («и это, и то»), числа вариантов на каждом шаге перемножаются.
Где
- n, m
- числа вариантов в двух группах без общих элементов
Правило суммы: если выбирают «либо это, либо то» и группы не пересекаются, числа вариантов складываются.
Представь правило произведения в виде дерева. У Мурада 3 рубашки (белая, синяя, зелёная) и 2 пары брюк (чёрные, серые). От каждой рубашки отходят 2 ветки — по одной на каждые брюки, поэтому всего 3 · 2 = 6 комплектов: белая–чёрные, белая–серые, синяя–чёрные, синяя–серые, зелёная–чёрные, зелёная–серые. Если же нужно выбрать только одну вещь — либо одну из 3 кепок, либо один из 2 шарфов, — варианты складываются: 3 + 2 = 5. Коротко: «и то, и это» — умножай, «либо то, либо это» — складывай.
Правила произведения и суммы
Задача
а) В кафе 3 вида супа, 4 вторых блюда и 2 напитка. Сколько разных обедов из супа, второго блюда и напитка можно заказать?
б) Сколько существует трёхзначных чисел с различными цифрами?
в) Лейла выбирает одну книгу: один из 5 романов или один из 7 сборников стихов. Сколько у неё вариантов?
Показать решениеСкрыть решение
Решение
б) Разряд сотен: не может быть 0 — 9 вариантов. Десятки: любая цифра, кроме первой, включая 0 — 9 вариантов. Единицы: оставшиеся 8 цифр. 9 · 9 · 8 = 648.
в) «Либо роман, либо стихи» — правило суммы: 5 + 7 = 12.
Формула включений и исключений. Если две группы пересекаются, правило суммы считает общие элементы дважды, поэтому их один раз вычитают. Для трёх групп: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. Здесь |A| — число элементов множества A.
Делящиеся на 2, 3 или 5
Задача
Сколько из чисел 1, 2, …, 100 делятся на 2, на 3 или на 5?
Показать решениеСкрыть решение
Решение
На 6 — 16, на 10 — 10, на 15 — 6; на 30 — 3.
50 + 33 + 20 − 16 − 10 − 6 + 3 = 74.
Значит, 100 − 74 = 26 чисел не делятся ни на одно из них — например, 1, 7, 11, 13 и все простые числа больше 5.
Чтобы читать дальше, зарегистрируйся бесплатно
Остальные разделы урока, тест и заметки открываются с аккаунтом Educora. Регистрация занимает минуту, а прогресс сохраняется на всех твоих устройствах.
Факториал и перестановки
ФакториалОпределение
n! = 1 · 2 · 3 · … · n — произведение всех натуральных чисел от 1 до n. По определению 0! = 1. Например, 5! = 120, 10! = 3 628 800 — факториал растёт очень быстро.
Где
- n
- число различных элементов, которые переставляют
Число перестановок: количество способов расставить n различных элементов в ряд. На первое место — n вариантов, на второе — n − 1 и так далее.
Выпиши все
Задача
Сколькими способами Айсель (A), Лейла (L) и Мурад (M) могут встать в ряд?
Показать решениеСкрыть решение
Решение
A первая: ALM, AML
L первая: LAM, LMA
M первый: MAL, MLA
Получилось 6 порядков. Правило подсчёта говорит то же: 3 варианта для первого места, 2 — для второго, 1 — для последнего: 3 · 2 · 1 = 3! = 6.
Перестановки
Задача
а) Сколькими способами можно расставить на полке 5 разных книг?
б) 6 учеников встают в ряд. Сколько существует расстановок, если Айсель и Мурад должны стоять рядом?
Показать решениеСкрыть решение
Решение
б) «Склеим» Айсель и Мурада и будем считать их одним элементом: тогда переставляются 5 элементов — 5! = 120. Внутри пары они могут стоять 2! = 2 способами.
120 · 2 = 240. (Без условия было бы 6! = 720.)
Повторяющиеся элементы и круглый стол
Задача
1) Сколько различных семизначных чисел можно записать цифрами 1, 1, 2, 2, 2, 3, 3, используя каждую ровно один раз?
2) Сколькими способами 6 человек могут сесть за круглый стол, если важен только порядок по кругу?
Показать решениеСкрыть решение
Решение
2) Если все пересядут на одно место по кругу, рассадка не изменится, а у каждой рассадки 6 таких поворотов: 6!/6 = 5! = 120. Иначе: закрепим место одного человека и рассадим остальных 5.
Размещения и сочетания
Где
- n
- общее число элементов
- k
- число выбираемых и упорядочиваемых элементов (k ≤ n)
Размещения: из n элементов выбирают k и упорядочивают — порядок важен. Справа стоят k убывающих множителей, начиная с n.
Где
- n
- общее число элементов
- k
- число выбираемых элементов; порядок не учитывается
Сочетания: из n элементов просто выбирают k — порядок не важен. Каждая группа из k элементов в размещениях посчитана k! раз, поэтому делим на k!.
Когда важен порядок? Возьмём трёх учеников — A, B, C — и выберем двоих. Если им дают разные должности (капитан и заместитель), AB и BA — разные выборы. Если это просто пара, которая едет на соревнование, то AB и BA — одна и та же пара.
| Капитан и заместитель (порядок важен) | Просто пара (порядок не важен) |
|---|---|
| AB, BA | {A; B} |
| AC, CA | {A; C} |
| BC, CB | {B; C} |
| всего 6 = A₃² | всего 3 = C₃² |
| Что делаем? | Порядок важен? | Формула | Пример |
|---|---|---|---|
| переставляем все 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₆³.
Почему C₅² + C₅³ = C₆³? Это объясняет одна история. Из 6 учеников, среди которых Айсель, выбираем команду из 3 человек: C₆³ = 20 команд. В каждую команду Айсель либо входит, либо нет. Команды с Айсель: выбираем ещё 2 из остальных 5 — C₅² = 10. Команды без неё: выбираем всех 3 из остальных 5 — C₅³ = 10. 10 + 10 = 20. И равенство C₅² = C₅³ так же просто: выбрать 2 человек, которые едут, — то же самое, что выбрать 3, которые остаются.
- Для C₁₀³ запиши в числителе 3 числа по убыванию, начиная с 10: 10 · 9 · 8 = 720.
- В знаменателе запиши 3! = 1 · 2 · 3 = 6.
- Раздели: 720 : 6 = 120. Проще сначала сократить: 9 : 3 = 3 и 8 : 2 = 4, тогда 10 · 3 · 4 = 120.
- Если k большое, переверни задачу: C₂₀¹⁸ = C₂₀² = (20 · 19) / 2 = 190.
Экзаменационная задача: выбор группы
Задача
В кружке 6 мальчиков и 4 девочки. Выбирают команду из 5 человек.
а) Сколько команд, в которых ровно 2 девочки?
б) Сколько команд, в которых хотя бы одна девочка?
в) Из кружка случайно выбирают 2 человек. Какова вероятность, что обе — девочки?
Показать решениеСкрыть решение
Решение
б) Через противоположное событие: «хотя бы одна девочка» = все − «без девочек». C₁₀⁵ − C₆⁵ = 252 − 6 = 246.
в) Всех пар: C₁₀² = 45, пар из двух девочек: C₄² = 6. P = 6/45 = 2/15 ≈ 0,13.
Классическая олимпиадная идея — метод «звёздочек и перегородок». Разделить n одинаковых предметов между m людьми — то же самое, что выложить в ряд n звёздочек и m − 1 перегородку: перегородки делят ряд на m частей. Например, ★★|★★★★★|★★★ означает 2, 5 и 3. Мы лишь выбираем места перегородок среди n + m − 1 мест, поэтому число способов равно Cₙ₊ₘ₋₁ᵐ⁻¹.
Делим конфеты
Задача
1) Сколькими способами можно разделить 10 одинаковых конфет между 3 детьми?
2) А если каждый ребёнок должен получить хотя бы одну?
Показать решениеСкрыть решение
Решение
2) Сначала дадим каждому ребёнку по конфете; оставшиеся 7 делим свободно: C₉² = (9 · 8)/2 = 36.
Те же числа — количество решений уравнения x + y + z = 10 в целых неотрицательных (66) и в натуральных (36) числах.
Бином Ньютона и треугольник Паскаля
Где
- n
- натуральный показатель
- Cₙᵏ
- биномиальные коэффициенты
Бином Ньютона. Общий член: Tₖ₊₁ = Cₙᵏ · aⁿ⁻ᵏ · bᵏ. В разложении n + 1 слагаемое, сумма коэффициентов равна 2ⁿ. В разложении (a − b)ⁿ знаки чередуются: +, −, +, …
Начни с известного: (a + b)² = a² + 2ab + b² — коэффициенты 1, 2, 1 — это 2-я строка треугольника Паскаля. Умножь ещё раз на (a + b) — получится (a + b)³ = a³ + 3a²b + 3ab² + b³, 3-я строка: 1, 3, 3, 1. Помогают две закономерности: от слагаемого к слагаемому степень a уменьшается на 1, а степень b растёт, и в каждом слагаемом сумма двух степеней равна n. При n = 3: a³, a²b, ab², 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⁶ |
Почему сумма коэффициентов n-й строки равна 2ⁿ? Подставим в бином Ньютона a = b = 1: (1 + 1)ⁿ = Cₙ⁰ + Cₙ¹ + … + Cₙⁿ. Есть и доказательство подсчётом: у множества из n элементов 2ⁿ подмножеств (каждый элемент либо берём, либо нет), и Cₙᵏ из них содержат ровно k элементов. Если же подставить a = 1, b = −1, получится Cₙ⁰ − Cₙ¹ + Cₙ² − … = 0: подмножеств с чётным числом элементов столько же, сколько с нечётным.
Начинки для пиццы
Задача
В пиццерии 8 видов начинок. Сколько разных пицц можно заказать (любой набор начинок, возможно, пустой)? В скольких из них чётное число начинок?
Показать решениеСкрыть решение
Решение
Пицц с чётным и с нечётным числом начинок поровну, поэтому чётное число начинок у 128 пицц. Проверка по 8-й строке: C₈⁰ + C₈² + C₈⁴ + C₈⁶ + C₈⁸ = 1 + 28 + 70 + 28 + 1 = 128 ✓.
Интерактив
Разложение бинома и коэффициент
Задача
а) Раскройте (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.
Бином Ньютона — ещё и инструмент приближённых вычислений и теории вероятностей. Если x мало, слагаемые с x², x³, … быстро становятся крошечными, поэтому (1 + x)ⁿ ≈ 1 + nx + Cₙ²x². А когда монету бросают n раз, каждая последовательность орлов и решек имеет вероятность 1/2ⁿ, а ровно k орлов выпадает в Cₙᵏ последовательностях — это биномиальное распределение, один из главных законов вузовской теории вероятностей.
Приближение и бросание монеты
Задача
1) Оцените 1,01¹⁰ без калькулятора.
2) Монету бросают 10 раз. Какова вероятность, что орёл выпадет ровно 5 раз?
Показать решениеСкрыть решение
Решение
2) Всего 2¹⁰ = 1024 равновозможных последовательности, и в C₁₀⁵ = 252 из них ровно 5 орлов: P = 252/1024 = 63/256 ≈ 0,246. Значит, даже самый вероятный результат выпадает реже, чем в одной серии из четырёх.
Запомни
- Правило произведения: варианты последовательных шагов перемножаются; правило суммы: варианты «либо—либо» складываются.
- Pₙ = n! — число всех перестановок n элементов.
- Если порядок важен — Aₙᵏ = n!/(n − k)!, если нет — Cₙᵏ = n!/(k!(n − k)!).
- В задачах «хотя бы один» проще вычесть противоположный случай из общего числа.
- Коэффициенты (a + b)ⁿ — n-я строка треугольника Паскаля; общий член Cₙᵏaⁿ⁻ᵏbᵏ.