Метод включений и исключений

Пусть множество A имеет N элементов и n одноместных отношений (свойств) . Каждый из N элементов может обладать или не обладать любым из этих свойств. Обозначим через число элементов, обладающих свойствами и, может быть, некоторыми другими. Тогда число N(0) элементов, не обладающих ни одним из свойств , определяется по следующей формуле, называемой формулой включений и исключений:

, (*)

Где , , .

Пример 1. Пусть колода состоит из n карт, пронумерованных числами . Сколькими способами можно расположить карты в колоде так, чтобы ни для одного карта с номером i не занимала i-е место?

Решение. Имеется n свойств в виде «i-я карта занимает в колоде i-е место». Число всевозможных расположений карт в колоде равно . Число расположений, при которых карта с номером занимает место ( ), равно Тогда ,

.

Используя формулу (*), получаем, что число N(0) расположений, при которых ни одно из свойств не выполнено, равно

.

Обобщая формулу (*), получим формулу, позволяющую вычислить число N(r) элементов, обладающих ровно r свойствами :

. (**)

Пример 2. Пусть - функция для вещественных чисел x – наибольшее целое число, не превосходящее x. Для положительных целых чисел a и b значение функции равно количеству чисел из множества , которые делятся на a, т.е. кратных a. Сколько положительных чисел от 1 до 500 делятся ровно на одно из чисел 3, 5 или 7

Решение. Обозначим свойства делимости на 3, 5 и 7 соответственно через и . Тогда для N=500 имеем , , . Т.к. - число общих кратных для чисел 3 и 5, наименьшее общее кратное которых равно 15, то совпадает с количеством чисел, которые делятся на 15, т.е. . Аналогично, , , . По формуле (**) находим искомое число чисел

*Задача повышенной трудности

Пусть - число перестановок из n элементов, представимых в виде произведения r циклов, не имеющих общих элементов (например, ), а - число различных разбиений n отличных друг от друга элементов на r классов.

Доказать, что

(а)

(б)

(G.Pólya)

Решение. Перестановку n+1элементов, представимую в виде произведения r циклов, можно получить из перестановки n элементов двумя способами. Во-первых, цикл единичной длины, содержащий новый элемент, можно присоединить к перестановке n элементов, представимой в

виде произведения r-1 циклов. Во-вторых, новый элемент можно ввести в любой из r циклов, на которые разлагается перестановка n элементов. Так как во втором случае новый элемент можно ввести после любого из r старых элементов, то

(1)

(Если считать, , то это соотношение выполняется при n=1,2,..; r=1,…,n). Если , то из соотношения (1) следует, что (x+n)p_n(x)=p_n+1(x). Последнее соотношение позволяет методом математической индукции доказать тождество «а», приведенное в условии задачи. Аналогично доказывается второе тождество задачи. Разбиение n+1 отличимых друг от друга элементов на r классов можно получить из разбиения n элементов двумя способами. Во-первых, можно присоединить класс, состоящий только из одного нового элемента, к разбиению n элементов на r-1 класс. Во-вторых, новый элемент можно включить в любой из r классов, на которые разбиты n старых элементов. Так как во втором случае новый элемент можно ввести в любой из r классов старого разбиения, то . (Если считать, что лишь при 1£r£n, то это соотношение выполняется при n, r=1,2,…). Пусть f_r(x)=x(x-1)…(x-r+1). Так как легко проверить, что f_r+1(x)+rf_r(x)=xf_r(x), тождество «б», приведенное в условиях задачи, следует из соотношений

Задача 2.1. Доказать тождество:

Решение. Для доказательства решим двумя способами следующую комбинаторную задачу: подсчитать число строк в таблице вхождений элементов в подмножества множества m. В этой таблице строки имеют вид: iÎ{…,i,…}, где справа стоит подмножество, содержащее элемент i. Рассмотрим правые части строк данной таблицы. Будем рассматривать произвольное k-элементное подмножество и подсчитаем количество строк, в которых оно встречается. Оно встречается ровно в k строках – каждая из этих строк определяется одним из элементов этого подмножества. Поэтому, все

k-элементные подмножества дадут строк таблицы. Общее число строк таблицы дает левая часть данного тождества. Теперь будем пересчитывать строки другим способом. Каждое число встречается одинаковое число раз в левой части строк таблицы (каждый элемент входит в одно и то же число подмножеств). Подсчитаем, число подмножеств, в которые входит элемент m. Эти подмножества однозначно определяются своими дополнительными элементами к элементу m. Эти элементы составляют подмножество множества m-1. Число подмножеств множества m, содержащих элемент m, равно числу всех подмножеств множества m-1, то есть числу 2^m-1. Теперь умножим это число на число всех элементов, при этом получим правую часть исходного тождества: m2^m-1.™

Определение 2.4. Мультимножеством, состоящим из элементов некоторого множества называется неупорядоченная совокупность, состоящая из элементов данного множества, которые могут в ней повторяться.

Например, {1,3,3,3,4,4} – мультимножество элементов множества 4.

Приведем пример на подсчет числа мультимножеств.

Задача 2.2. Имеются пирожные трех сортов. Сколькими способами можно выбрать пять пирожных?

Решение. Можно выбрать все пирожные одного сорта тремя способами. Если выбирается два сорта пирожных, то таких возможностей будет ровно 12 (тремя способами можно выбрать два сорта из трех, а четырьмя способами можно разделить пять пирожных по сортам). Если используется все три сорта, то это означает, что к трем разным пирожным нужно добавить еще два произвольным образом. Таких возможностей имеется 6 штук (тремя способами можно добавить два одинаковых пирожных, тремя способами можно добавить два разных). Таким образом, общее число мультимножеств: .

Можно сделать вывод: общее число мультимножеств m элементов из множества n равно .

Можно проинтерпретировать этот результат следующим образом: число мультимножеств равно числу раскладок пяти одинаковых карточек по трем разным ящикам. Действительно, по мультимножеству однозначно можно построить раскладку m одинаковых карточек по n разным ящикам. Сколько имеется элементов i в мультимножестве, столько карточек кладется в i-ый ящик. Существует также и обратная процедура. Пусть имеется раскладка карточек по ящикам. На карточках, лежащих в каждом ящике,

будем ставить номер ящика. Если, затем, высыпать все карточки в одно место, то получится мультимножество нужного вида. Далее, разбиению множества m на n непересекающихся подмножеств можно дать следующую интересную комбинаторную интерпретацию. Итак, пусть в первом подмножестве содержится l₁ элементов, во втором подмножестве - l₂ элементов и так далее. В последнем подмножестве - l_n элементов. Построим m-буквенное слово в алфавите, состоящем из n символов, следующим образом. Элементы множества m будем считать номерами позиций в этом слове, а номера подмножеств – его буквами. Иными словами, в i-ой позиции должна стоять буква, имеющая номер подмножества, в которое попало число в i при разбиении. Легко видеть, что имея слово, можно «разбросать» номера позиций его букв по подмножествам, соответствующим номерам букв по счету в алфавитном порядке. Таким образом, всего таких слов будет штук.