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

Размещения, сочетания и перестановки. Формулу выбирать не нужно — ответь на два вопроса, и калькулятор подберёт её сам.

ОТВЕТЬ НА ДВА ВОПРОСА

Порядок важен Первое и второе место — не то же, что второе и первое. Отметь для паролей, шифров, призовых мест; сними для команды, комиссии, набора карт Элемент можно взять несколько раз Цифра в коде повторяется, а вынутый из урны шар — нет

Всего элементов n из чего выбираем Выбираем k сколько берём

Размещения без повторений A(n, k) = n! / (n−k)!

Как это считается

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

Выбор сводится к двум вопросам: важен ли порядок и можно ли брать элемент повторно. Первый отделяет размещения от сочетаний, второй — обычные формулы от формул с повторениями.

A_{n}^{k} = \frac{n!}{(n - k)!} C_{n}^{k} = \frac{n!}{k! (n - k)!}

Числа те же, ответы разные. Распределить между семью спортсменами три призовых места — 210 способов. Выбрать из тех же семерых троих в команду — 35. Разница ровно в 3! = 6 раз: столько перестановок внутри тройки, и в сочетаниях они не различаются.

Факториалы целиком считать не нужно: в дроби 7!/4! общий хвост сокращается и остаётся 7·6·5 — по множителю на каждое место.

Формулы рядом

Выбор формулы — это выбор клетки: слева вопрос о порядке, сверху — о повторениях.

	БЕЗ ПОВТОРЕНИЙ	С ПОВТОРЕНИЯМИ
Порядок важен размещения	$A_{n}^{k} = \frac{n!}{(n - k)!}$	${\overset{ˉ}{A}}_{n}^{k} = n^{k}$
Порядок не важен сочетания	$C_{n}^{k} = \frac{n!}{k! (n - k)!}$	${\overset{ˉ}{C}}_{n}^{k} = C_{n + k - 1}^{k}$

Перестановки стоят отдельно: там берут не часть элементов, а все сразу.

Все элементы различны	$P_{n} = n!$
Есть одинаковые	$P (n_{1}, n_{2}, \dots) = \frac{n!}{n_{1}! n_{2}! \dots}$

Примеры расчёта

Порядок важен: призовые места

A_{7}^{3} = ?

Определяем, важен ли порядок

$Размещения без повторений$

Порядок важен: наборы из одних и тех же элементов, расставленных по-разному, считаются разными. Так устроены пароли, шифры, распределение призовых мест.
Считаем размещения

$A_{7}^{3} = \frac{n!}{(n - k)!} = \frac{7!}{4!} = 7 \cdot 6 \cdot 5 = 210$

Факториалы сокращаются: в 7! и 4! общий хвост, после деления остаётся произведение 3 убывающих множителей начиная с 7. Считать 7! целиком не нужно — это лишняя работа и повод ошибиться.

210

Золото у Иванова и серебро у Петрова — не то же, что наоборот. Порядок различается, значит это размещения, а не сочетания.

Порядок не важен: та же семёрка, но в команду

C_{7}^{3} = ?

Определяем, важен ли порядок

$Сочетания без повторений$

Порядок не важен: набор из одних и тех же элементов — это один и тот же результат, как бы его ни перечисляли. Так устроены выбор команды, раздача карт, состав комиссии.
Считаем сочетания

$C_{7}^{3} = \frac{n!}{k! (n - k)!} = \frac{7!}{3! \cdot 4!} = \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35$

В числителе после сокращения остаётся то же произведение, что и у размещений, а деление на 3! убирает перестановки внутри выбранной группы: порядок здесь не различается.
Проверяем через размещения

$C_{7}^{3} \cdot 3! = 35 \cdot 6 = 210 = A_{7}^{3}$

Каждое сочетание можно упорядочить k! способами — и получится ровно множество всех размещений. Сходится, значит выбрана та формула.

35

Числа те же, задача другая — и ответ меньше ровно в 3! = 6 раз. Команда одна и та же, в каком порядке ни перечисляй её состав. Получилось 210 в задаче про выбор — значит, посчитан порядок, которого нет.

Перестановки с повторениями: МАТЕМАТИКА

МАТЕМАТИКА \to P (2, 3, 2, 1, 1, 1) = ?

Определяем, важен ли порядок

$Перестановки с повторениями$

Порядок важен: наборы из одних и тех же элементов, расставленных по-разному, считаются разными. Так устроены пароли, шифры, распределение призовых мест.
Считаем повторы

$МАТЕМАТИКА, n = 10$

Всего букв 10. Повторяются: М — 2, А — 3, Т — 2.
Считаем перестановки с повторениями

$P (2, 3, 2, 1, 1, 1) = \frac{n!}{n_{1}! n_{2}! \dots} = \frac{10!}{2! \cdot 3! \cdot 2! \cdot 1! \cdot 1! \cdot 1!} = 151200$

Обычный факториал считал бы одинаковые элементы разными и завысил ответ. Деление на факториал каждой группы убирает перестановки внутри неё: менять местами две одинаковые буквы — значит получать то же самое слово.

151200

Десять букв дали бы 10! = 3 628 800 перестановок, будь они все разными. Но три «А» неразличимы между собой, как и пары «М» и «Т». Деление на 2!·3!·2! убирает эти повторы.

Сочетания с повторениями: пять пирожных четырёх сортов

{\overset{ˉ}{C}}_{4}^{5} = ?

Определяем, важен ли порядок

$Сочетания с повторениями$

Порядок не важен: набор из одних и тех же элементов — это один и тот же результат, как бы его ни перечисляли. Так устроены выбор команды, раздача карт, состав комиссии.
Считаем сочетания с повторениями

${\overset{ˉ}{C}}_{4}^{5} = C_{n + k - 1}^{k} = C_{8}^{5} = 56$

Задача сводится к обычным сочетаниям из 8 по 5. Приём такой: набор записывают строкой из k шариков и n − 1 перегородок между сортами. Каждая такая строка задаёт ровно один набор, и наоборот — значит, считать можно их.

56

Берут больше, чем есть сортов, и это законно: сорт не кончается. Формулу не узнают в лицо из-за того, что в ней n и k складывают, хотя везде до этого вычитали.

Вопросы

Как понять, размещения это или сочетания?

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

Почему ответы различаются ровно в k! раз?

Каждое сочетание можно упорядочить k! способами, и все упорядочивания вместе дают ровно множество размещений: Aⁿₖ = Cⁿₖ · k!. Калькулятор показывает эту проверку отдельным шагом.

Что значит «с повторениями»?

Выбранный элемент не выбывает и его можно взять снова: цифра в пин-коде повторяется, вынутый из урны шар — нет. При этом k может быть больше n: пятизначный код из десяти цифр — 10⁵.

Почему 0! = 1?

Пустое множество можно расставить единственным способом — никак. Это не исключение, а частный случай: без такого соглашения ломались бы формулы, где n − k обращается в ноль.

Можно ли выбрать больше элементов, чем есть?

Без повторений — нет, калькулятор откажется считать. С повторениями — можно, ограничения на k там нет.

Что такое биномиальный коэффициент и треугольник Паскаля?

Другое название числа сочетаний Cⁿₖ — из школьного бинома Ньютона (a+b)ⁿ, где такие числа стоят перед каждым слагаемым разложения. Их можно построить и без факториалов: в треугольнике Паскаля каждое число — сумма двух соседних сверху. Строка треугольника с номером n — это Cⁿ₀, Cⁿ₁, …, Cⁿₙ по порядку, посчитанные без единого деления.

Зачем считать буквы в слове?

Задача про перестановки букв «МАТЕМАТИКИ» — самая частая на эту формулу. Введи слово целиком, повторы посчитаются сами: три «А», две «М», две «Т».

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

Калькулятор

Как это считается

Формулы рядом

Примеры расчёта

Порядок важен: призовые места

Определяем, важен ли порядок

Считаем размещения

Порядок не важен: та же семёрка, но в команду

Определяем, важен ли порядок

Считаем сочетания

Проверяем через размещения

Перестановки с повторениями: МАТЕМАТИКА

Определяем, важен ли порядок

Считаем повторы

Считаем перестановки с повторениями

Сочетания с повторениями: пять пирожных четырёх сортов

Определяем, важен ли порядок

Считаем сочетания с повторениями

Вопросы

Похожие калькуляторы