Базовые идеи комбинаторики

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

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

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

• Сколько различных слов возможно составить из заданного набора букв: "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$ различных перестановок.

# Вычисление факториала
def fact(n):
    return n if n == 1 else n * fact(n - 1)

print(fact(3))

# Итеративное вычисление факториала
def fact2(n):
    res = 1
    for i in range(2, n + 1):
        res *= i
    return res

print(fact2(3))

# Использование reduce вычисление факториала
from functools import reduce

def fact3(n):
    return reduce(lambda x, y: x * y, range(2, n + 1))

print(fact3(6))

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

Под числом размещений понимают количество вариантов, которыми можно записать в ряд подпоследовательность из $K$ элементов некоторой перестановки из $N$ элементов. При этом последовательности из одинаковых элементов, но с различным их порядком следования считаются различными. Количество таких комбинаций расчитывается по формуле: $A_N^K = \frac{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 = \frac{A_N^K}{K!} = \frac{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 = \frac{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⁰

Задача 1. Точки на костях Домино

Для того, чтобы заработать огромный капитал, новым русским необходимо иметь неординарное мышление. Конечно, при такой сложной работе, должны так же присутствовать какие то особенные механизмы для отдыха и развлечений. В этих целях в казино был придуман специальный набор домино для новых русских. Обычные кости домино представляют собой набор из различных комбинаций сочетаний двух плиток, на каждой из которых отображается от 0 до 6 точек. А этот набор представляет собой подобные сочетания плиток, но количество точек на каждой может быть от нуля до заданного значения, которое зависит от интеллектуального уровня игроков. В таком наборе костей присутствуют всевозможные сочетания плиток, но при этом ни одна из костей не повторяется (даже такие комбинации как 2-5 и 5-2 считаются одинаковыми).

Для изготовления данного набора костей перед изготовителем встала проблема вычисления суммарного количества точек на всех костях домино. Это связано с тем, что домино для новых русских украшается бриллиантами, которые представляют собой точки на плитках и при изготовлении необходимо оценить стоимость.

Помогите написать программу, которая решит эту задачу.

Входные данные

Входной файл содержит одно натуральное число $N$ – максимальное количество точек на одной плитке домино. $(N \le 10000)$

Выходные данные

В выходной файл выведите количество бриллиантовых камней, которые необходимо изготовить для заданного набора костей.

Пример

Входной файл	Выходной файл
2	12

Задача 2. Игра с монеткой

Петя играет в интересную игру. Для этой игры необходима монетка. Петя подбрасывает ее $n$ раз и считает, сколько раз выпадает «решка». Если решка выпадает хотя бы $m$ раз, то Петя считает, что он выиграл игру.

Однажды Петя задумался, какова вероятность того, что он выиграет игру. Для этого он хочет найти количество последовательностей результатов подбрасывания монетки, содержащих ровно $n$ подбрасываний, при которых «решка» выпала хотя бы $m$ раз.

Помогите Пете — найдите это число, считая, что при каждом броске монетка может выпасть либо «орлом», либо «решкой».

Входные данные

Входной файл содержит два целых числа: $n$ и $m$ $(1 < n \le 20, 0 \le m \le n)$.

Выходные данные

В выходной файл выведите ответ на задачу.

Примеры

INPUT.TXT	OUTPUT.TXT
2 0	4
3 2	4

Задача 3. Шахматы

Требуется найти число способов расставить на шахматной доске $N * N$ $K$ ладей так, чтобы они не били друг друга. Все ладьи считаются одинаковыми.

Входные данные

Во входном файле записаны натуральные числа $N$ и $K$ $(N, K \le 8)$.

Выходные данные

В выходной файл выведите одно целое число – ответ на задачу.

Пример

chess.in	chess.out
8 8	40320