Задача на комбинаторику обычно выглядит просто, пока не встаёт вопрос: а важен тут порядок или нет? От ответа зависит, какую формулу применять - сочетания или размещения, и результат отличается в разы. Калькулятор выше считает оба варианта через точную арифметику с большими числами, так что для n и r до 1000 не будет ни округлений, ни переполнения.
Сочетания и размещения: в чём разница
Сочетание - это выбор группы элементов, где важен только состав, а порядок отбора роли не играет. Размещение - тот же выбор, но с учётом порядка: разная последовательность элементов даёт разный результат, даже если сам набор одинаковый.
Разница видна на классическом примере. Из десяти друзей нужно выбрать троих для похода в кино. Кто пойдёт первым в зал, а кто вторым, не имеет значения - важен только сам факт, что эти трое идут вместе. Это сочетание, и формула C(n,r) = n! / (r! × (n-r)!) даёт:
C(10,3) = 10! / (3! × 7!) = (10 × 9 × 8) / (3 × 2 × 1) = 720 / 6 = 120
Получается 120 разных троек друзей.
Теперь другая ситуация: из тех же десяти человек нужно выбрать президента, секретаря и казначея клуба. Состав тот же - трое из десяти, но теперь порядок критичен: если Иванов станет президентом, а Петров секретарём, это совсем не то же самое распределение ролей, что наоборот. Здесь работает размещение, A(n,r) = n! / (n-r)!:
A(10,3) = 10! / 7! = 10 × 9 × 8 = 720
Ровно 720 способов распределить три должности между десятью кандидатами - в шесть раз больше, чем сочетаний. Это не совпадение: 720 / 120 = 6 = 3!, то есть числу перестановок внутри тройки.
Почему размещений всегда не меньше, чем сочетаний
Каждое сочетание из r элементов можно расставить в r! разных порядков, и каждая такая расстановка - отдельное размещение. Поэтому связь между ними жёсткая:
A(n,r) = C(n,r) × r!
Если r = 3, множитель r! равен 6, если r = 4 - уже 24. Чем больше элементов выбираем за раз, тем сильнее размещения отрываются от сочетаний по числу вариантов. Исключение - случаи r = 0 и r = 1: переставлять пустой набор или один-единственный элемент некуда, поэтому A(n,0) = C(n,0) = 1, а A(n,1) = C(n,1) = n.
Пример с кодами без повторения цифр
Другая типичная задача: сколько трёхзначных кодов без повторения цифр можно составить из пяти разных цифр, скажем 1, 2, 3, 4, 5. Здесь код 123 и код 321 - это разные коды, хотя используют одни и те же цифры, значит порядок важен и нужно размещение:
A(5,3) = 5 × 4 × 3 = 60
Логика та же, что и при ручном подсчёте: на первое место можно поставить любую из пяти цифр, на второе - любую из оставшихся четырёх, на третье - любую из оставшихся трёх. 5 × 4 × 3 = 60 вариантов. Если бы порядок цифр в коде не имел значения (что для кодов встречается редко), результат сводился бы к сочетанию C(5,3) = 10 - в шесть раз меньше, тот же множитель 3!.
Как понять, что перед вами: сочетание или размещение
Работает простой тест. Представьте, что вы поменяли местами два элемента в уже выбранном наборе. Если от этого ничего не изменилось по сути задачи - перед вами сочетание. Если получился новый, отличный от прежнего результат - размещение.
Выбор членов команды, лотерейных чисел, ингредиентов для блюда - обычно сочетания, порядок отбора не имеет значения для итога. Расстановка мест на подиуме, распределение ролей, составление пароля или кода - размещения, потому что позиция каждого элемента меняет результат.
Как пользоваться калькулятором
Выберите режим - сочетания или размещения, укажите общее число элементов n и сколько из них выбираете r. Результат обновляется сразу при вводе, без отдельной кнопки. Если ввести r больше n, калькулятор покажет предупреждение вместо числа: выбрать больше элементов, чем есть в наборе, невозможно ни при каком порядке.
Для больших n и r числа быстро становятся огромными - факториал растёт стремительно, и уже C(1000,500) выражается сотнями цифр. Расчёт идёт через целочисленную арифметику с большими числами, так что итог остаётся точным даже там, где обычный калькулятор на основе чисел с плавающей точкой выдал бы округлённое приближение.