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

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 элементов (обозначается PN) равно N! (эн факториал), где N!=1*2*...*N. По определению считается, что 0!=1.

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

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

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

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

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

Предлагаем самостоятельно вывести следующие полезные формулы:
СN0 = CNN = 1 (N>=1)
CNK = CNN-K (правило симметрии)
CNK = CN-1K-1 + CN-1K (правило Паскаля) (N>1, 0 < K < N)
CN0 + CN1 + ... + CNN = 2N

Последняя формула может буть получена как следствие известного соотношения под названием бином Ньютона: (x+y)N=CN0*x0*yN+ ...+CNK*xK*yN-K+...+CNN*xN*y0
При x = y = 1 бином Ньютона дает приведенную формулу.

Задача 15-1. Шахматы
Задача 15-2. Карточки
Задача 15-3. Великий Комбинатор