Калькулятор комбинаторики онлайн

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

Комбинаторика — раздел математики, изучающий дискретные структуры и методы подсчёта количества способов расположить, выбрать или упорядочить элементы конечного множества. Название происходит от латинского слова combinare (объединять, сочетать). Комбинаторика — одна из старейших областей математики: первые задачи встречались ещё в древнеиндийских трактатах (VI век н.э.), а систематическое развитие началось в XVII веке благодаря работам Блеза Паскаля и Пьера Ферма.

Наш онлайн-калькулятор комбинаторики позволяет вычислить четыре основных типа комбинаторных величин: перестановки P(n), размещения A(n,k), сочетания C(n,k) и сочетания с повторениями C̅(n,k). Для каждого вычисления калькулятор показывает пошаговую факториальную декомпозицию — все промежуточные значения факториалов, из которых складывается результат. Это особенно полезно при подготовке к ЕГЭ и ОГЭ, когда нужно не просто получить ответ, но и продемонстрировать ход решения.

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

Перестановки P(n) — формула и примеры

Перестановки (обозначаются P(n) или Pₙ) — это количество способов расположить все n различных элементов в определённом порядке. Формула перестановок:

P(n) = n! = n × (n−1) × (n−2) × … × 2 × 1

Здесь n! (n-факториал) — произведение всех натуральных чисел от 1 до n. По определению, 0! = 1 и 1! = 1.

Пример 1. Сколькими способами можно расставить 5 книг на полке? Каждый порядок расстановки — это перестановка. Ответ: P(5) = 5! = 5 × 4 × 3 × 2 × 1 = 120 способов.

Пример 2. Сколькими способами 8 бегунов могут финишировать в забеге (при условии, что нет одинаковых результатов)? Ответ: P(8) = 8! = 40 320 вариантов.

Пример 3. В очереди стоят 10 человек. Сколько существует различных очередей? P(10) = 10! = 3 628 800. Уже для 10 элементов число перестановок исчисляется миллионами, а для 20 элементов P(20) = 20! ≈ 2,43 × 10¹⁸ — это почти два с половиной квинтиллиона вариантов.

Перестановки — частный случай размещений, когда k = n, то есть мы берём все элементы без исключения. Если среди n элементов есть одинаковые (повторяющиеся), то используют формулу перестановок с повторениями: P(n; n₁, n₂, …, nₖ) = n! / (n₁! × n₂! × … × nₖ!), где n₁, n₂, …, nₖ — количества одинаковых элементов каждого типа. Например, число анаграмм слова «АББА» (4 буквы, А — 2 раза, Б — 2 раза): 4! / (2! × 2!) = 24 / 4 = 6.

Размещения A(n,k) — формула и примеры

Размещения (обозначаются A(n,k), Aⁿₖ или P(n,k) в англоязычной литературе) — это количество упорядоченных выборок k элементов из n различных, без повторений. Формула:

A(n,k) = n! / (n−k)! = n × (n−1) × (n−2) × … × (n−k+1)

Здесь порядок выбранных элементов важен: выборка {A, B, C} и {C, B, A} считаются разными размещениями. Количество множителей в произведении равно k.

Пример 1. Из 20 кандидатов нужно выбрать председателя, заместителя и секретаря. Порядок важен (три разные должности), повторения нет. A(20,3) = 20! / 17! = 20 × 19 × 18 = 6 840 способов.

Пример 2. Сколькими способами можно составить трёхзначный код из цифр 1–9 без повторения цифр? A(9,3) = 9 × 8 × 7 = 504.

Пример 3. На олимпиаде 15 участников. Сколькими способами можно распределить золотую, серебряную и бронзовую медали? A(15,3) = 15 × 14 × 13 = 2 730.

Заметим, что A(n,n) = n! = P(n) — при k = n размещения совпадают с перестановками. Также A(n,1) = n — выбор одного элемента из n даёт n вариантов, что соответствует интуиции.

Размещения с повторениями — случай, когда каждый элемент можно выбирать более одного раза. Формула: Ā(n,k) = nᵏ. Например, количество четырёхзначных PIN-кодов из цифр 0–9: 10⁴ = 10 000.

Сочетания C(n,k) — биномиальные коэффициенты

Сочетания (обозначаются C(n,k), Cⁿₖ или «n choose k») — это количество неупорядоченных выборок k элементов из n различных, без повторений. Формула:

C(n,k) = n! / (k! × (n−k)!)

Сочетания также называют биномиальными коэффициентами, так как они являются коэффициентами в разложении бинома Ньютона. Порядок выбранных элементов не имеет значения: выборки {A, B, C} и {C, A, B} — это одно и то же сочетание.

Связь с размещениями: C(n,k) = A(n,k) / k! — сочетание получается из размещения делением на количество перестановок k выбранных элементов (k!), так как порядок не важен.

Пример 1. Из класса в 30 учеников нужно выбрать команду из 4 человек для олимпиады. Порядок не важен. C(30,4) = 30! / (4! × 26!) = (30 × 29 × 28 × 27) / (4 × 3 × 2 × 1) = 27 405 способов.

Пример 2. В лотерее нужно угадать 6 чисел из 45. Количество возможных комбинаций: C(45,6) = 45! / (6! × 39!) = 8 145 060. Вероятность угадать все 6 чисел: 1 / 8 145 060 ≈ 0,0000123%.

Пример 3. Сколько диагоналей в выпуклом n-угольнике? Каждая диагональ соединяет 2 несмежные вершины. Всего отрезков между вершинами: C(n,2) = n(n−1)/2, из них n — стороны. Итого диагоналей: C(n,2) − n = n(n−3)/2.

Важнейшие свойства сочетаний:

• Симметрия: C(n,k) = C(n, n−k). Например, C(10,3) = C(10,7) = 120.
• C(n,0) = C(n,n) = 1 — существует ровно один способ выбрать 0 или все n элементов.
• C(n,1) = n — выбор одного элемента из n.
• Формула Паскаля: C(n,k) = C(n−1,k−1) + C(n−1,k) — основа треугольника Паскаля.
• Сумма строки: Σ C(n,k) = 2ⁿ для k от 0 до n — общее количество подмножеств множества из n элементов.

Сочетания с повторениями C̅(n,k)

Сочетания с повторениями (обозначаются C̅(n,k) или H(n,k)) — количество способов выбрать k элементов из n типов, когда каждый тип можно выбирать неограниченно, и порядок не важен. Формула:

C̅(n,k) = C(n+k−1, k) = (n+k−1)! / (k! × (n−1)!)

Эта формула эквивалентна задаче о распределении k одинаковых шаров по n различным ящикам (метод «звёзд и полосок»). Представим k шаров как звёзды (★) и n−1 разделитель как полоски (|). Любая последовательность из k звёзд и n−1 полосок определяет одно распределение, а количество таких последовательностей равно C(n+k−1, k).

Пример 1. В кафе 4 вида пирожных. Сколькими способами можно купить 6 штук? C̅(4,6) = C(9,6) = 84.

Пример 2. Решить в целых неотрицательных числах уравнение x₁ + x₂ + x₃ = 10. Количество решений: C̅(3,10) = C(12,10) = 66.

Пример 3. Нужно раздать 7 одинаковых конфет 3 детям. Количество способов: C̅(3,7) = C(9,7) = 36.

Треугольник Паскаля — таблица биномиальных коэффициентов

Треугольник Паскаля — бесконечная числовая таблица треугольной формы, в которой каждый элемент равен сумме двух элементов, расположенных над ним (формула Паскаля). Строка с номером n содержит значения C(n,0), C(n,1), C(n,2), …, C(n,n). Назван в честь французского математика Блеза Паскаля (1623–1662), хотя аналогичные конструкции были известны задолго до него — в Китае (треугольник Яна Хуэя, XIII век), в Персии (Омар Хайям, XI век) и в Индии (Пингала, II век до н.э.).

Первые строки треугольника Паскаля (начиная с n = 0):

Свойства треугольника Паскаля, которые полезны при решении задач:

• Сумма строки n равна 2ⁿ. Например, строка 5: 1 + 5 + 10 + 10 + 5 + 1 = 32 = 2⁵.
• Диагонали содержат натуральные числа (1, 2, 3, …), треугольные числа (1, 3, 6, 10, …), тетраэдрические числа и т. д.
• Каждый чётный ряд (кроме крайних единиц) содержит только чётные числа тогда и только тогда, когда n — степень двойки.
• Числа Фибоначчи можно найти, суммируя элементы «мелких» диагоналей треугольника Паскаля.

Треугольник Паскаля — это не просто таблица для быстрого нахождения C(n,k). Он связывает между собой комбинаторику, алгебру (бином Ньютона), теорию чисел (делимость биномиальных коэффициентов) и даже фрактальную геометрию (треугольник Серпинского получается при закрашивании чётных элементов треугольника Паскаля).

Бином Ньютона — связь комбинаторики и алгебры

Бином Ньютона — формула для разложения n-й степени суммы двух слагаемых в сумму слагаемых, каждое из которых содержит биномиальный коэффициент:

(a + b)ⁿ = Σ C(n,k) × aⁿ⁻ᵏ × bᵏ для k от 0 до n

Развёрнутая запись: (a + b)ⁿ = C(n,0)·aⁿ + C(n,1)·aⁿ⁻¹·b + C(n,2)·aⁿ⁻²·b² + … + C(n,n)·bⁿ.

Примеры раскрытия бинома:

• (a + b)² = a² + 2ab + b² — коэффициенты 1, 2, 1 (строка 2 треугольника Паскаля).
• (a + b)³ = a³ + 3a²b + 3ab² + b³ — коэффициенты 1, 3, 3, 1.
• (a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴ — коэффициенты 1, 4, 6, 4, 1.

Частные случаи бинома Ньютона, часто встречающиеся на экзаменах:

• При a = 1, b = 1: (1+1)ⁿ = 2ⁿ = Σ C(n,k) — сумма всех биномиальных коэффициентов.
• При a = 1, b = −1: (1−1)ⁿ = 0 = Σ (−1)ᵏ·C(n,k) — знакопеременная сумма равна нулю.
• Обобщённый бином Ньютона (для произвольного действительного показателя α): (1+x)ᵅ = Σ C(α,k)·xᵏ, где C(α,k) = α(α−1)…(α−k+1)/k! (обобщённый биномиальный коэффициент). Эта формула используется в математическом анализе и является основой биномиального ряда.

На ЕГЭ по математике задачи на бином Ньютона встречаются в виде: «Найдите коэффициент при x⁵ в разложении (2x − 3)⁸» или «Вычислите сумму 1 + C(10,1) + C(10,2) + … + C(10,10)». Для решения таких задач достаточно знать формулу бинома и уметь работать с треугольником Паскаля.

Правило произведения и правило суммы

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

Правило произведения (комбинаторное правило умножения): если первый выбор можно сделать m способами, а второй (независимо от первого) — n способами, то оба выбора можно сделать m × n способами. Пример: в гардеробе 5 рубашек и 4 пары брюк. Количество комбинаций одежды: 5 × 4 = 20. Правило обобщается на произвольное число этапов: m₁ × m₂ × … × mₖ.

Правило суммы (комбинаторное правило сложения): если объекты можно разбить на непересекающиеся группы размером m и n, то общее количество объектов равно m + n. Пример: в классе 12 мальчиков и 15 девочек. Количество способов выбрать одного старосту: 12 + 15 = 27. Если группы пересекаются, применяется формула включений-исключений.

Эти два принципа — основа всех комбинаторных вычислений. Формулы перестановок, размещений и сочетаний выводятся именно из правила произведения. Сложные задачи на комбинаторику, как правило, требуют комбинированного применения обоих правил: сначала разбиваем задачу на независимые этапы (произведение), а при наличии альтернативных сценариев складываем результаты (сумма).

Формула включений-исключений

Формула включений-исключений (принцип Сильвестра) позволяет подсчитать мощность объединения нескольких множеств, корректируя ошибки двойного подсчёта:

Для двух множеств: |A ∪ B| = |A| + |B| − |A ∩ B|

Для трёх множеств: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

Пример. В группе из 100 студентов 60 изучают английский, 45 — немецкий, 20 — оба языка. Сколько студентов изучают хотя бы один язык? |A ∪ B| = 60 + 45 − 20 = 85. Значит, 15 студентов не изучают ни одного из этих языков.

Формула включений-исключений используется при вычислении субфакториала (количества беспорядков) — числа перестановок, в которых ни один элемент не стоит на своём месте: !n = n! × Σ (−1)ᵏ / k! для k от 0 до n. Например, !4 = 4! × (1 − 1 + 1/2 − 1/6 + 1/24) = 24 × 3/8 = 9 беспорядков из 4 элементов.

Задачи ЕГЭ по комбинаторике 2026 — типовые примеры с решениями

Задачи на комбинаторику регулярно встречаются в ЕГЭ по математике (профильный уровень) — в заданиях на теорию вероятностей и подсчёт вариантов. Разберём типичные задачи с подробным решением:

Задача 1. Из колоды в 36 карт наугад вытаскивают 3 карты. Какова вероятность, что все три карты — тузы?

Решение. Всего тузов в колоде: 4. Число способов выбрать 3 туза из 4: C(4,3) = 4. Число способов выбрать любые 3 карты из 36: C(36,3) = 36! / (3! × 33!) = (36 × 35 × 34) / 6 = 7 140. Вероятность: P = C(4,3) / C(36,3) = 4 / 7 140 = 1/1 785 ≈ 0,056%.

Задача 2. Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5, если каждая цифра используется ровно один раз?

Решение. Это задача на перестановки: P(5) = 5! = 120 чисел.

Задача 3. В классе 25 учеников. Нужно выбрать 3 человека для участия в конференции. Сколькими способами можно это сделать?

Решение. Порядок не важен (выбираем группу, а не назначаем роли). C(25,3) = 25! / (3! × 22!) = (25 × 24 × 23) / 6 = 2 300 способов.

Задача 4. Сколько слов (осмысленных и бессмысленных) можно составить, переставляя буквы слова «КОМБИНАТОРИКА»?

Решение. Слово содержит 13 букв: К — 2, О — 2, И — 2, А — 2, М — 1, Б — 1, Н — 1, Т — 1, Р — 1. Перестановки с повторениями: 13! / (2! × 2! × 2! × 2!) = 6 227 020 800 / 16 = 389 188 800 различных «слов».

Задача 5. На координатной плоскости из точки (0,0) нужно попасть в точку (5,3), двигаясь только вправо или вверх по единичным отрезкам. Сколько существует различных путей?

Решение. Каждый путь состоит из 5 шагов вправо (→) и 3 шагов вверх (↑), всего 8 шагов. Нужно выбрать 3 позиции из 8 для шагов вверх: C(8,3) = 56 путей.

Комбинаторика в криптографии и информационной безопасности

Комбинаторные формулы — ключевой инструмент оценки стойкости криптографических систем. Количество возможных ключей определяет, насколько сложно взломать шифр методом полного перебора (brute force). Например, пароль из 8 символов, составленный из 26 строчных букв, 26 заглавных букв, 10 цифр и 10 спецсимволов (72 символа), даёт 72⁸ ≈ 7,22 × 10¹⁴ вариантов — это размещения с повторениями.

В покере комбинаторика определяет вероятность каждой комбинации. Количество комбинаций из 5 карт из 52: C(52,5) = 2 598 960. Из них: 4 роял-флеша (вероятность 0,00015%), 36 стрит-флешей (0,0014%), 624 каре (0,024%), 3 744 фулл-хауса (0,144%), 5 108 флешей (0,197%).

В генетике комбинаторика используется для подсчёта числа возможных генотипов. При наличии n генов, каждый из которых имеет 2 аллеля, число возможных генотипов равно 3ⁿ (для диплоидного организма). Для генома человека с примерно 20 000 генов количество теоретически возможных генотипов астрономически велико — это одна из причин уникальности каждого человека.

Рекуррентные соотношения и динамическое программирование

Многие комбинаторные задачи решаются с помощью рекуррентных соотношений — формул, выражающих очередной член последовательности через предыдущие. Классический пример — формула Паскаля для биномиальных коэффициентов: C(n,k) = C(n−1,k−1) + C(n−1,k). Эта рекурренция позволяет вычислять C(n,k) без факториалов, заполняя треугольник Паскаля строка за строкой.

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

• Числа Каталана: Cₙ = C(2n,n) / (n+1) — количество корректных скобочных последовательностей длины 2n, количество бинарных деревьев с n узлами, количество триангуляций выпуклого (n+2)-угольника.
• Числа Стирлинга второго рода S(n,k) — количество способов разбить множество из n элементов на k непустых подмножеств.
• Числа Белла Bₙ = Σ S(n,k) — общее количество разбиений множества из n элементов.
• Разбиения числа p(n) — количество способов представить натуральное число n как сумму натуральных слагаемых (без учёта порядка).

Динамическое программирование позволяет эффективно вычислять эти величины, избегая экспоненциального времени работы рекурсивных алгоритмов.

Производящие функции — мощный метод комбинаторного анализа

Производящие функции (генератрисы) — алгебраический метод кодирования числовых последовательностей {a₀, a₁, a₂, …} в виде формального степенного ряда f(x) = Σ aₙ × xⁿ. Этот метод, разработанный Леонардом Эйлером, позволяет сводить комбинаторные задачи к операциям над рядами — сложению, умножению, дифференцированию.

Производящая функция для биномиальных коэффициентов: (1+x)ⁿ = Σ C(n,k)·xᵏ — это и есть бином Ньютона. Производящая функция для чисел Каталана: C(x) = (1 − √(1−4x)) / (2x). Производящая функция для чисел Фибоначчи: F(x) = x / (1 − x − x²).

Производящие функции особенно полезны при решении задач на целочисленные разбиения, подсчёт деревьев, подсчёт путей на графах и в задачах с ограничениями. В университетских курсах дискретной математики метод производящих функций — один из центральных инструментов комбинаторного анализа.

Источники

• Виленкин Н. Я. «Комбинаторика» — классический учебник по комбинаторному анализу для школьников и студентов
• Колмогоров А. Н. «Алгебра и начала математического анализа. 10–11 классы» — комбинаторика и биномиальные коэффициенты в школьной программе
• Стенли Р. «Перечислительная комбинаторика» — фундаментальная монография по производящим функциям и методам подсчёта
• Graham R., Knuth D., Patashnik O. «Concrete Mathematics» — биномиальные коэффициенты, числа Стирлинга, рекуррентные соотношения
• ФИПИ — Федеральный институт педагогических измерений, демоверсии и задачники ЕГЭ по математике 2026