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