Олимпиады по программированию

olympiads.ru

МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Занятие 15. Комбинаторика - 1.

На практике часто встречаются задачи, формулировка которых начинается со слов: "Сколько существует...", "Сколькими способами" и т. д. Такие задачи принято называть комбинаторными, а раздел математики, который их изучает - комбинаторикой.

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

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

• Правило произведения. Если элемент а можно выбрать m способами, а элемент b (независимо от выбора элемента а) - n способами, то выбор "а и b" можно сделать m·n способами.
• Правило суммы. Если элемент а можно выбрать m способами, а элемент b (независимо от выбора элемента а) - n способами, то выбор "а или b" можно сделать m + n способами.

Продемонстрируем действие этих правил на примере следующей простой задачи:

Требуется найти количество двузначных чисел с четной суммой цифр.

Двузначное число имеет четную сумму цифр только в одном из следующих двух случаев: либо обе цифры четные, либо обе цифры нечетные. Значит, по правилу суммы, количество двузначных чисел с четной суммой цифр равно сумме количеств двузначных чисел, у которых обе цифры четные, и двузначных чисел, у которых обе цифры нечетные. По правилу произведения, первых чисел 4*5=20 (на место первой цифры можно поставить все четные цифры, кроме 0, а на место второй просто все четные цифры), а вторых 5*5=25. Итого, двузначных чисел с четной суммой цифр 20+25=45.

Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N. Например, перестановками из 3 элементов будут: 123, 132, 213, 231, 312, 321; а вот 112 и 134 таковыми не являются. Количество различных перестановок из N элементов (обозначается P_N) равно N! (эн факториал), где N!=1*2*...*N. По определению считается, что 0!=1.

Действительно, на первое место можно поставить любой из N предметов, на второе - любой из N-1 оставшихся и т.д.

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

Действительно, на первое место мы можем поставить любой из N имеющихся предметов, на второе любой из N-1 оставшихся, ..., на K-е - любой из N-K+1 оставшихся.

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

Действительно, размещения от сочетаний отличаются только тем, что в размещениях мы выбранные K элементов должны расставить на K различных мест, что можно сделать K! различными способами.

Предлагаем самостоятельно вывести следующие полезные формулы:
С_N⁰ = C_N^N = 1 (N>=1)
C_N^K = C_N^N-K (правило симметрии)
C_N^K = C_N-1^K-1 + C_N-1^K (правило Паскаля) (N>1, 0 < K < N)
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⁰
При x = y = 1 бином Ньютона дает приведенную формулу.