"Математика: алгебра и начала математического анализа, геометрия. Алгебра и начала математического анализа. Базовый и углублённый уровни", Рубин А.Г., Чулков П.В.
Комбинаторика помогает подсчитывать, сколько способов существует для выбора, расположения или распределения объектов, не перечисляя все варианты. Её основные инструменты — правило суммы, правило произведения и формулы для перестановок, размещений и сочетаний. Чтобы выбрать подходящий способ подсчёта, нужно выяснить, выполняются ли этапы последовательно и имеет ли значение порядок выбранных элементов. Эти приёмы применяются в задачах о кодах, соревнованиях, комиссиях и случайном выборе.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Факториал натурального числа n — произведение всех натуральных чисел от 1 до n: n! = 1 · 2 · … · n. Знак ! обозначает факториал, а не обычное умножение на число. По соглашению 0! = 1. Факториалы компактно записывают длинные произведения и входят в формулы подсчёта вариантов.
Перестановка — это упорядочивание всех n различных элементов, при котором каждый используется ровно один раз. Число перестановок обозначают Pₙ и вычисляют по формуле Pₙ = n!. Она нужна, когда требуется посчитать все возможные порядки одного и того же полного набора, например расстановки книг.
Размещение — выбор k элементов из n с учётом порядка: два результата различаются, если те же элементы стоят на разных местах. Формула Aₙᵏ = n!/(n − k)! получается последовательным выбором без повторений. Она подходит, когда выбирают только часть элементов и назначают им разные роли или места.
Сочетание — выбор k элементов из n без учёта порядка. Число сочетаний равно Cₙᵏ = n!/(k!(n − k)!). Здесь перестановка уже выбранных элементов не создаёт нового результата, поэтому сочетания считают, например, при формировании комиссии, где должности участникам не назначаются.
Правило суммы применяют, если нужно выбрать один вариант из нескольких групп, которые не пересекаются. Пусть в одной группе m вариантов, а в другой n; выбор из первой группы не может одновременно оказаться выбором из второй. Тогда к каждому варианту первой группы добавляются варианты второй, и общее число равно m + n. Если группы пересекаются, некоторые исходы окажутся посчитаны дважды, поэтому сначала нужно устранить пересечение или иначе разбить варианты.
Правило произведения подходит, когда решение складывается из этапов, которые выполняются один за другим. Если первый этап можно пройти m способами, а после каждого его результата второй — n способами, каждой из m возможностей соответствуют n продолжений. Поэтому получается m · n пар результатов. Для нескольких этапов умножают число вариантов на каждом из них, учитывая ограничения, которые могли возникнуть раньше.
Факториал возникает при подсчёте перестановок, потому что число доступных элементов уменьшается после каждого выбора. На первое место можно поставить любой из n элементов, на второе — любой из n − 1 оставшихся, затем остаётся n − 2 и так далее, пока для последнего места не останется один вариант. По правилу произведения получаем n · (n − 1) · … · 1 = n!. Каждый порядок учитывается ровно один раз.
Размещение и сочетание оба описывают выбор k элементов из n, но отвечают на разные вопросы. Если важны места или роли, перестановка выбранных элементов меняет результат: например, первое и второе места на соревновании нельзя поменять без изменения исхода. Если важен только состав группы, порядок не создаёт нового варианта. Поэтому перед вычислением полезно спросить себя, останется ли выбор тем же, если поменять выбранные элементы местами.
Формулу сочетаний можно получить из формулы размещений. Сначала посчитаем упорядоченные выборы: их Aₙᵏ. Но каждый набор из k элементов среди них повторяется во всех возможных порядках, а таких порядков k!. Чтобы оставить по одному подсчёту на набор, делим Aₙᵏ на k!: Cₙᵏ = Aₙᵏ/k! = n!/(k!(n − k)!).
| Вид выбора | Что выбирается | Учитывается ли порядок | Формула | Пример применения |
|---|---|---|---|---|
| Правило суммы | Один вариант из нескольких непересекающихся групп | Нет | m + n | Выбор одного предмета из двух групп |
| Правило произведения | Последовательный выбор элементов | Да, по этапам выбора | m · n | Составление пароля из нескольких позиций |
| Перестановка | Все n элементов | Да | Pₙ = n! | Расстановка книг на полке |
| Размещение | k элементов из n | Да | Aₙᵏ = n!/(n − k)! | Выбор призёров по местам |
| Сочетание | k элементов из n | Нет | Cₙᵏ = n!/(k!(n − k)!) | Выбор комиссии |
Сначала определите, выбираете ли вы один из вариантов, проходите несколько этапов или формируете упорядоченную последовательность. Затем проверьте, влияет ли перестановка выбранных элементов на результат. Эта проверка помогает выбрать между размещением и сочетанием.
Задача 1. Сколько различных комплектов можно составить, если выбрать одну рубашку из 5 и одни брюки из 3? Комплект состоит из двух предметов одежды, поэтому выбор проходит в два последовательных этапа. Для каждой рубашки подойдут все три пары брюк, значит, применяем правило произведения.
Ответ: 15 комплектов.
Задача 2. Сколько существует способов выбрать и расставить на первые три места 5 участников соревнования? Участники выбираются не все, а занявшие разные места образуют разные результаты. Например, смена первого и второго места изменит итог, поэтому считаем размещения без повторений.
Ответ: 60 способов.
Задача 3. Из 10 учеников нужно выбрать комиссию из 4 человек, причём один определённый ученик должен войти в комиссию. Состав комиссии важен, а порядок перечисления участников ничего не меняет. Обязательный ученик уже выбран, поэтому остаётся дополнить комиссию тремя людьми из девяти других учеников.
Ответ: 84 комиссии.
Первая ошибка — использовать сочетания, когда порядок важен, ориентируясь только на слово «выбрать». Так теряются разные назначения одних и тех же людей на места. Проверьте себя вопросом: изменится ли результат, если поменять выбранные элементы местами? Если да, нужны размещения.
Обратная ошибка — применять размещения, когда порядок не важен. Тогда одна и та же группа будет посчитана несколько раз в разных последовательностях. Например, комиссия из Ани, Бориса и Веры не меняется от того, в каком порядке перечислены имена. Для проверки представьте конкретный набор и сравните его после перестановки.
Правило суммы нельзя без проверки применять к группам с общими вариантами: общий исход при сложении будет учтён дважды. Ошибка возникает, когда варианты описаны не как непересекающиеся случаи. Перед сложением выясните, может ли один и тот же выбор попасть в обе группы; если может, разделите случаи иначе или учтите пересечение.
При вычислениях встречаются ошибки в факториалах и сокращении дробей. Например, n! — это произведение до 1, а не n · (n − 1); кроме того, 0! равно 1. Раскрывайте только нужные множители: в дроби n!/(n − k)! общая часть сокращается, после чего полезно проверить число оставшихся множителей и подстановку малого значения, например n = 3.
Для работы с комбинаторными формулами понадобятся действия с натуральными числами, сокращение дробей и раскрытие произведений. Понятие множества помогает точно понимать, из каких элементов выбирают и какие варианты считаются одинаковыми. Эти знания служат основой для дальнейших задач на вероятность и биномиальные коэффициенты.
Комбинаторные подсчёты нужны, когда требуется оценить число исходов случайного выбора. Те же правила помогают считать возможные коды, маршруты, расписания и распределения объектов. Умение различать порядок и состав выбора позволяет переносить формулы на такие практические ситуации.
Как понять, нужно складывать или умножать количество вариантов?
Складывай, когда выбирается один вариант из нескольких непересекающихся групп: один и тот же исход не должен относиться сразу к двум группам. Умножай, когда выбор состоит из последовательных этапов и каждый результат первого этапа можно продолжить вариантами второго.
Чем размещение отличается от сочетания?
В размещении выбирают k элементов из n и учитывают их порядок: назначение участников на разные места даёт разные варианты. В сочетании важен только состав выбранной группы, поэтому перестановка её элементов ничего не меняет.
Почему в формуле перестановок появляется факториал?
На первое место можно поставить любой из n элементов, на второе — один из оставшихся n − 1, и так далее. По правилу произведения число расстановок равно n · (n − 1) · … · 1, а это и есть n!.
Почему в сочетаниях порядок выбранных элементов не учитывается?
Сочетание описывает набор, а не последовательность, поэтому перестановки одних и тех же k элементов считаются одним вариантом. Размещение считает этот набор k! раз — по числу его порядков, поэтому при переходе к сочетаниям делят на k!.
Как выбрать формулу, если в условии есть обязательный или запрещённый элемент?
Сначала учти ограничение, затем определи, важен ли порядок оставшегося выбора. Обязательный элемент можно зафиксировать и выбрать остальные из оставшихся; запрещённый — исключить из общего числа доступных элементов.
4.3. Элементы комбинаторики
