Комбинаторика - раздел олимпиадного программирования (а так же и раздел математики), где ставится вопрос о подсчете числа вариантов выбора элементов из некоторого, как правило, конечного множества согласно заданным правилам.

В качестве примеров комбинаторных задач могут быть следующие:

• Сколько различных слов возможно составить из заданного набора букв: "ATBTATBZA"?
• Сколько вариантов команд из 3х мальчиков и 2х девочек можно составить при наличии 10 мальчиков и 12 девочек?
• Сколько существует различных счастливых 6-значных билетов с суммой цифр, равной 30?

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

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

Число перестановок N!

Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N. Количество различных перестановок порядка N равно N! = 1*2*3 ... * (N-1) * N. Заметим, что 0!=1. Для факториала справедлива следующая рекурентная запись: N! = (N-1)!*N.

Например, для N=3 существует всего 6 таких перестановок: (1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 1 2) и (3 2 1). Число N! называют факториалом и произносят как "Н факториал". В нашем случае как раз получилось 3! = 1*2*3 = 6 различных перестановок.

Число размещений A_N^K

Под числом размещений понимают количество вариантов, которыми можно записать в ряд подпоследовательность из K элементов некоторой перестановки из N элементов. При этом последовательности из одинаковых элементов, но с различным их порядком следования считаются различными. Количество таких комбинаций расчитывается по формуле: A_N^K = N!/(N-K)!.

Например, для N=4 и K=2 из перестановки (1 2 3 4) можно составить следующие последовательности из 2х элементов: (1 2), (1 3), (1 4), (2 3), (2 4), (3 4), (2 1), (3 1), (4 1), (3 2), (4 2), (4 3). Всего получилось A₄² = 4!/(4-2)! = 12 вариантов.

Число сочетаний C_N^K

Под числом сочетаний понимают количество вариантов, которыми можно выбрать K элементов из некоторого множества, состоящего из N элементов. При этом последовательности из одинаковых элементов, но с различным их порядком следования считаются равными. Количество таких комбинаций расчитывается по формуле: C_N^K = A_N^K/K! = N!/(K!*(N-K)!).

Например, для N=4 и K=2 из перестановки (1 2 3 4) можно составить следующие последовательности из 2х элементов: (1 2), (1 3), (1 4), (2 3), (2 4), (3 4). Всего получилось С₄² = 4!/(2!*(4-2)!) = 6 вариантов.

Число сочетаний очень часто используется при решении комбинаторных задач. Например, при игре в "спортлото 5 из 36" с помощью данной формулы можно расчитать вероятность угадывания 5 номеров, т.к. общее число возможных вариантов выбора 5 из 36 равно С₃₆⁵.

Формулы, использующие число сочетаний:

• C_N^K = C_N-1^K-1 + C_N-1^K
• C_N⁰ + C_N¹ + ... + C_N^N = 2^N
• (x+y)^N=C_N⁰*x⁰*y^N+ ...+C_N^K*x^K*y^N-K+...+C_N^N*x^N*y⁰