Комбинаторика

Правила суммы и произведения, факториал, перестановки, размещения и сочетания, бином Ньютона и треугольник Паскаля.

  • 9…11 классы
  • 25 мин
  • 10 вопросов
  • Урок 56 из 92

В этом уроке ты узнаешь

  • Считать варианты по правилам произведения и суммы
  • Выбирать между размещениями и сочетаниями в зависимости от того, важен ли порядок
  • Раскрывать бином с помощью треугольника Паскаля и находить любой коэффициент

Сколько существует разных 4-значных PIN-кодов банковской карты? На каждое место ставится одна из 10 цифр: 10 · 10 · 10 · 10 = 10 000 вариантов. Сколькими способами класс из 25 человек может выбрать 3 делегатов? 2300 способами! Выписать все варианты невозможно — комбинаторика учит считать их без перебора. На ней основаны теория вероятностей, криптография и программирование.

Правила произведения и суммы

N = n₁ · n₂ · … · nₖ

Где

n₁, n₂, …, nₖ
число вариантов на каждом шаге
N
общее число вариантов

Правило произведения: если выбор делается в несколько последовательных шагов («и это, и то»), числа вариантов на каждом шаге перемножаются.

N = n + m

Где

n, m
числа вариантов в двух группах без общих элементов

Правило суммы: если выбирают «либо это, либо то» и группы не пересекаются, числа вариантов складываются.

Простое объяснение

Представь правило произведения в виде дерева. У Мурада 3 рубашки (белая, синяя, зелёная) и 2 пары брюк (чёрные, серые). От каждой рубашки отходят 2 ветки — по одной на каждые брюки, поэтому всего 3 · 2 = 6 комплектов: белая–чёрные, белая–серые, синяя–чёрные, синяя–серые, зелёная–чёрные, зелёная–серые. Если же нужно выбрать только одну вещь — либо одну из 3 кепок, либо один из 2 шарфов, — варианты складываются: 3 + 2 = 5. Коротко: «и то, и это» — умножай, «либо то, либо это» — складывай.

Правила произведения и суммы

Задача

а) В кафе 3 вида супа, 4 вторых блюда и 2 напитка. Сколько разных обедов из супа, второго блюда и напитка можно заказать?
б) Сколько существует трёхзначных чисел с различными цифрами?
в) Лейла выбирает одну книгу: один из 5 романов или один из 7 сборников стихов. Сколько у неё вариантов?

Показать решениеСкрыть решение

Решение

а) Три шага (суп, второе, напиток) — правило произведения: 3 · 4 · 2 = 24.
б) Разряд сотен: не может быть 0 — 9 вариантов. Десятки: любая цифра, кроме первой, включая 0 — 9 вариантов. Единицы: оставшиеся 8 цифр. 9 · 9 · 8 = 648.
в) «Либо роман, либо стихи» — правило суммы: 5 + 7 = 12.
Углублённо
|A ∪ B| = |A| + |B| − |A ∩ B|

Формула включений и исключений. Если две группы пересекаются, правило суммы считает общие элементы дважды, поэтому их один раз вычитают. Для трёх групп: |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?

Показать решениеСкрыть решение

Решение

На 2 делятся 50 чисел, на 3 — 33, на 5 — 20.
На 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 — факториал растёт очень быстро.

Pₙ = n!

Где

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 учеников встают в ряд. Сколько существует расстановок, если Айсель и Мурад должны стоять рядом?

Показать решениеСкрыть решение

Решение

а) P₅ = 5! = 1 · 2 · 3 · 4 · 5 = 120.
б) «Склеим» Айсель и Мурада и будем считать их одним элементом: тогда переставляются 5 элементов — 5! = 120. Внутри пары они могут стоять 2! = 2 способами.
120 · 2 = 240. (Без условия было бы 6! = 720.)
Углублённо

Повторяющиеся элементы и круглый стол

Задача

1) Сколько различных семизначных чисел можно записать цифрами 1, 1, 2, 2, 2, 3, 3, используя каждую ровно один раз?
2) Сколькими способами 6 человек могут сесть за круглый стол, если важен только порядок по кругу?

Показать решениеСкрыть решение

Решение

1) Если бы все 7 цифр были различны, получилось бы 7! = 5040 расстановок. Но перестановка двух единиц, трёх двоек или двух троек даёт то же число, поэтому каждое число посчитано 2! · 3! · 2! = 24 раза: 5040 / 24 = 210.
2) Если все пересядут на одно место по кругу, рассадка не изменится, а у каждой рассадки 6 таких поворотов: 6!/6 = 5! = 120. Иначе: закрепим место одного человека и рассадим остальных 5.

Размещения и сочетания

Aₙᵏ = n! / (n − k)! = n · (n − 1) · … · (n − k + 1)Aₙᵏ = n! / (n − k)! = n · (n − 1) · … · (n − k + 1)

Где

n
общее число элементов
k
число выбираемых и упорядочиваемых элементов (k ≤ n)

Размещения: из n элементов выбирают k и упорядочивают — порядок важен. Справа стоят k убывающих множителей, начиная с n.

Cₙᵏ = n! / (k! · (n − k)!) = Aₙᵏ / k!Cₙᵏ = n! / (k! · (n − k)!) = Aₙᵏ / k!

Где

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₃²
Каждая пара встречается в левом столбце дважды (2! = 2 порядка), поэтому C₃² = A₃² / 2! = 6 / 2 = 3.
Что делаем?Порядок важен?ФормулаПример
переставляем все 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 делегатов на конференцию?

Показать решениеСкрыть решение

Решение

а) Должности разные, порядок важен: A₂₅³ = 25 · 24 · 23 = 13 800.
б) Три делегата равноправны, порядок не важен: C₂₅³ = A₂₅³ / 3! = 13 800 / 6 = 2300.
Cₙᵏ = Cₙⁿ⁻ᵏCₙᵏ + Cₙᵏ⁺¹ = Cₙ₊₁ᵏ⁺¹Cₙ⁰ = Cₙⁿ = 1

Где

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, которые остаются.

  1. Для C₁₀³ запиши в числителе 3 числа по убыванию, начиная с 10: 10 · 9 · 8 = 720.
  2. В знаменателе запиши 3! = 1 · 2 · 3 = 6.
  3. Раздели: 720 : 6 = 120. Проще сначала сократить: 9 : 3 = 3 и 8 : 2 = 4, тогда 10 · 3 · 4 = 120.
  4. Если k большое, переверни задачу: C₂₀¹⁸ = C₂₀² = (20 · 19) / 2 = 190.

Экзаменационная задача: выбор группы

Задача

В кружке 6 мальчиков и 4 девочки. Выбирают команду из 5 человек.
а) Сколько команд, в которых ровно 2 девочки?
б) Сколько команд, в которых хотя бы одна девочка?
в) Из кружка случайно выбирают 2 человек. Какова вероятность, что обе — девочки?

Показать решениеСкрыть решение

Решение

а) 2 девочки из 4 и 3 мальчика из 6 — правило произведения: C₄² · C₆³ = 6 · 20 = 120.
б) Через противоположное событие: «хотя бы одна девочка» = все − «без девочек». 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) А если каждый ребёнок должен получить хотя бы одну?

Показать решениеСкрыть решение

Решение

1) n = 10, m = 3: C₁₂² = (12 · 11)/2 = 66.
2) Сначала дадим каждому ребёнку по конфете; оставшиеся 7 делим свободно: C₉² = (9 · 8)/2 = 36.
Те же числа — количество решений уравнения x + y + z = 10 в целых неотрицательных (66) и в натуральных (36) числах.

Бином Ньютона и треугольник Паскаля

(a + b)ⁿ = Cₙ⁰aⁿ + Cₙ¹aⁿ⁻¹b + Cₙ²aⁿ⁻²b² + … + Cₙⁿbⁿ

Где

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Биномиальные коэффициентыСумма
011 = 2⁰
11 12 = 2¹
21 2 14 = 2²
31 3 3 18 = 2³
41 4 6 4 116 = 2⁴
51 5 10 10 5 132 = 2⁵
61 6 15 20 15 6 164 = 2⁶
Треугольник Паскаля. По краям стоят единицы, каждое внутреннее число равно сумме двух чисел над ним: 10 = 4 + 6, 20 = 10 + 10. Строка n — это коэффициенты разложения (a + b)ⁿ.
Углублённо

Почему сумма коэффициентов n-й строки равна 2ⁿ? Подставим в бином Ньютона a = b = 1: (1 + 1)ⁿ = Cₙ⁰ + Cₙ¹ + … + Cₙⁿ. Есть и доказательство подсчётом: у множества из n элементов 2ⁿ подмножеств (каждый элемент либо берём, либо нет), и Cₙᵏ из них содержат ровно k элементов. Если же подставить a = 1, b = −1, получится Cₙ⁰ − Cₙ¹ + Cₙ² − … = 0: подмножеств с чётным числом элементов столько же, сколько с нечётным.

Начинки для пиццы

Задача

В пиццерии 8 видов начинок. Сколько разных пицц можно заказать (любой набор начинок, возможно, пустой)? В скольких из них чётное число начинок?

Показать решениеСкрыть решение

Решение

Каждая начинка либо есть в пицце, либо нет: 2⁸ = 256 пицц (включая пиццу без начинок).
Пицц с чётным и с нечётным числом начинок поровну, поэтому чётное число начинок у 128 пицц. Проверка по 8-й строке: C₈⁰ + C₈² + C₈⁴ + C₈⁶ + C₈⁸ = 1 + 28 + 70 + 28 + 1 = 128 ✓.

Интерактив

Загрузка симуляции…
Биномиальные коэффициенты симметричны относительно середины: C₁₀ᵏ = C₁₀¹⁰⁻ᵏ. Самый большой — посередине: C₁₀⁵ = 252. Их сумма равна 2¹⁰ = 1024. С ростом n столбцы принимают форму «колокола» — это путь к нормальному распределению.

Разложение бинома и коэффициент

Задача

а) Раскройте (x + 2)⁴.
б) Найдите коэффициент при x² в разложении (2x − 1)⁵.

Показать решениеСкрыть решение

Решение

а) 4-я строка: 1, 4, 6, 4, 1. Степени двойки: 1, 2, 4, 8, 16.
(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 раз?

Показать решениеСкрыть решение

Решение

1) (1 + 0,01)¹⁰ = 1 + 10 · 0,01 + 45 · 0,0001 + 120 · 0,000001 + … ≈ 1 + 0,1 + 0,0045 + 0,00012 = 1,10462. Калькулятор даёт 1,104622…
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ᵏ.
Заметил ошибку или неточность в уроке?

Проверь себя

Вопросов: 10. Каждый правильный ответ приносит XP.

Вопрос 1 / 10

Вопрос 1 / 10. Сколько существует 4-значных PIN-кодов, у которых все цифры различны? (PIN может начинаться с 0.)