28. Вычисление числа вариантов

Определения и обозначения

Факториал числа n — произведение всех натуральных чисел от 1 до n: n! = 1·2·3·...·n. По соглашению 0! = 1. Факториал сокращает запись длинных произведений и встречается во всех основных комбинаторных формулах.

Перестановка — это упорядочивание всех n различных элементов. Число перестановок обозначают Pₙ и вычисляют по формуле Pₙ = n!. Такая модель подходит, когда используются все объекты, а их порядок создаёт разные варианты.

Размещение — выбор и упорядочивание k элементов из n различных элементов. Его число обозначают Aₙᵏ и находят по формуле Aₙᵏ = n!/(n−k)!. Размещения нужны, когда выбирают только часть объектов и порядок выбранных объектов имеет значение.

Сочетание — выбор k элементов из n различных элементов без учёта их порядка. Число сочетаний обозначают Cₙᵏ и вычисляют так: Cₙᵏ = n!/(k!(n−k)!). Эта формула подходит для групп и наборов, где перестановка участников не создаёт нового результата.

Как это устроено

Сначала по условию нужно выяснить, что именно считается вариантом. Если расставляются все объекты, это перестановка; если выбирается часть и порядок важен, это размещение; если выбирается часть без порядка, это сочетание. Например, места призёров образуют размещение, состав команды — сочетание, а порядок всех книг на полке — перестановку.

При перестановках первый элемент можно выбрать n способами. После этого для второго остаётся n−1 элементов, для третьего — n−2, и так далее, пока для последнего не останется один вариант. По правилу умножения общее число равно n·(n−1)·...·2·1 = n!.

Для размещения рассуждение о первых шагах такое же, но выбор заканчивается после k позиций. Число вариантов равно n·(n−1)·...·(n−k+1). Если домножить это произведение на (n−k)!, получится n!, поэтому исходное произведение можно записать как n!/(n−k)!.

В размещениях порядок учитывается: капитан и заместитель — разные назначения. В сочетаниях набор учеников А, Б и В один и тот же, как бы ни записывать эти фамилии. Каждый набор из k элементов в размещениях встречается k! раз, поэтому Aₙᵏ = Cₙᵏ·k!, а для вычислений выбирают формулу после проверки смысла задачи.

Основные виды вычисления числа вариантов

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

Разбор задач

Расстановка книг

Сколькими способами можно расставить 5 различных книг на полке? Используются все книги, а изменение порядка двух книг даёт новую расстановку. Значит, перед нами перестановка.

1. Определяем число элементов: n = 5.
2. Применяем формулу перестановок: P₅ = 5!.
3. Вычисляем факториал: 5! = 5·4·3·2·1 = 120.

Ответ: 120 способов.

Назначение на должности

Сколькими способами можно выбрать и назначить капитана, заместителя и секретаря из 10 учащихся? Выбираются три человека, но должности различаются, поэтому один и тот же состав с другими ролями считается новым вариантом. Это размещение трёх элементов из десяти.

1. Записываем n = 10 и k = 3.
2. Используем формулу: A₁₀³ = 10!/(10−3)! = 10!/7!.
3. Сокращаем факториалы: A₁₀³ = 10·9·8 = 720.

Ответ: 720 способов.

Выбор команды

Сколько существует команд из 4 человек, которые можно выбрать из 12 учащихся? Внутри команды нет капитана и закреплённых мест, поэтому порядок фамилий не важен. Следовательно, нужно найти сочетание, а не размещение.

1. Берём n = 12 и k = 4.
2. Подставляем в формулу: C₁₂⁴ = 12!/(4!·8!).
3. Сокращаем: C₁₂⁴ = (12·11·10·9)/(4·3·2·1) = 495.

Ответ: 495 команд.

Типичные ошибки

Сочетания используют вместо размещений, когда роли или порядок имеют значение. Так ошибаются, если смотрят только на число выбранных объектов и не анализируют их назначение. Проверьте себя вопросом: изменится ли результат после перестановки элементов?

Размещения используют вместо сочетаний, считая один набор в разных порядках разными вариантами. Причина ошибки — запись участников по очереди вместо рассмотрения состава группы. Если перестановка элементов не меняет результат, нужно сочетание.

При переходе от сочетаний к размещениям забывают множитель k! и смешивают формулы Aₙᵏ и Cₙᵏ. Один набор из k элементов имеет k! различных порядков, поэтому Aₙᵏ = Cₙᵏ·k!. Сверьте формулу с тем, учитывается ли порядок.

Нельзя сокращать n! с (n−k)!, пропуская промежуточные множители. Верно записывать n! = n·(n−1)·...·(n−k+1)·(n−k)!, после чего сокращать только последний множитель. Такая запись помогает не потерять числа.

Связь с другими темами

Для вычисления числа вариантов нужны правило умножения, правило сложения и умение преобразовывать факториалы. Правило умножения объясняет последовательный выбор, а факториалы делают запись короче. Эти знания служат основой комбинаторных формул.

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

Такие формулы помогают считать коды, расписания, маршруты и способы выбора объектов. В каждом случае нужно перевести условие на язык «выбираем», «упорядочиваем» или «распределяем». После этого подходящая формула становится понятной.

Что запомнить

• Факториал: n! = 1·2·3·...·n.
• Перестановка использует все элементы и учитывает их порядок.
• Размещение выбирает k элементов и учитывает их порядок.
• Сочетание выбирает k элементов, но не учитывает их порядок.
• Aₙᵏ = Cₙᵏ·k!.
• Перед вычислением нужно определить, важен ли порядок выбранных элементов.