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

Пусть множество А имеет N элементов и n одноместных отношений (свойств) Р₁,Р₂,…,Р_n. Каждый из N элементов может обладать или не обладать любым из этих свойств. Обозначим через N_{i1...i k} число элементов, обладающих свойствами Р_i1,...,P_{i k} и, может быть, некоторыми другими. Тогда число N(0) элементов, не обладающих ни одним из свойств Р₁,Р₂,…,Р_n, определяется по следующей формуле, называемой формулой включений и исключений:

N(0) = S₀ – S₁ + S₂ -... + (-1)ⁿ S_n ,

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

Имеется n свойств Р_i в виде «i-я карта занимает в колоде i-е место». Число всевозможных расположений карт в колоде равно n!. Число N_{i1...i k} расположений, при которых карта с номером i_j занимает место i_j (j=1,...,k), равно (n-k)!. Тогда S₀ = n!,

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

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

Для положительных целых чисел a и b значение функции равно количеству чисел из множества {1,2,…,b}, которые делятся на а, т.е. кратных а.

П р и м е р 2. сколько положительных чисел от 1 до 500 делятся ровно на одно из чисел 3,5 или 7?

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

 

-2(N₁₂ + N₁₃ + N₂₃) + 3N₁₂₃ = 166 +100 +71 -2(33+23+14) +3 4 =209.

Лабораторная работа №2

Комбинаторный анализ

Цель работы: ознакомиться с элементами комбинаторного анализа, изучить комбинаторные схемы.

 

Таблица 3.1 – Варианты заданий

№ варианта	Задание
	В ящике 5 красных и 4 зеленых яблока. Сколькими способами можно выбрать три яблока из ящика?
	Монету подбросили 3 раза. Сколько различных результатов бросаний можно ожидать?
	Сколькими способами можно вытащить две карты пиковой масти из колоды в 36 карт?
	Десять человек при встрече обмениваются рукопожатиями. Сколько всего рукопожатий будет сделано?
	Доступ к файлу открывается, только если введен правильный пароль – определенный трехзначный номер из нечетных цифр. Каково максимальное число возможных попыток угадать пароль?
	Сколькими способами можно расположить на шахматной доске две ладьи так, чтобы одна не могла взять другую? (Одна ладья может взять другую, если она находится с ней на одной горизонтали или на одной вертикали шахматной доски).
	Сколькими способами можно расположить на полке 10 томов энциклопедии?
	Сколькими способами можно расположить на полке 10 томов энциклопедии так, чтобы девятый и десятый тома рядом не стояли?
	Группу из 10 человек требуется разбить на две непустые подгруппы. Сколькими способами это можно сделать? (Подгруппы считаем различными.)
	Группу из 10 человек требуется разбить на две подгруппы так, чтобы в первой группе было 6 человек, а во второй – 4 человека. Сколькими способами это можно сделать?
	Группу из 16 человек требуется разбить на 3 подгруппы, в первой из которых должно быть 5 человек, во второй — 7 человек, в третьей — 4 человека. Сколькими способами это можно сделать?

Продолжение таблицы 3.1

 

	Сколько существует двузначных чисел, кратных либо 2, либо 5, либо тому и другому числу одновременно?
	Из бригады в 14 врачей ежедневно в течении 7 дней назначают двух дежурных врачей. Определить количество различных расписаний дежурства, если каждый человек дежурит один раз.
	Сколько четырехзначных чисел, составленных из нечетных цифр, содержит цифру 3 (цифры в числах не повторяются)?
	Шесть групп занимаются в 6 расположенных подряд аудиториях. Сколько существует вариантов расписания, при которых группы 1 и 2 находились бы в соседних аудиториях?
	Восемь мешков постельного белья доставляются на пять этажей гостиницы. Сколькими способами можно распределить мешки по этажам? В скольких вариантах на пятый этаж доставлен один мешок? (Мешки считаем различными).
	Два наборщика должны набрать 16 текстов. Сколькими способами они могут распределить эту работу между собой?
	Поезд метро делает 16 остановок, на которых выходят пассажиры. Сколькими способами могут распределиться между этими остановками 100 пассажиров, вошедших в поезд на конечной остановке?
	Акционерное собрание компании выбирает из 50 человек президента компании, председателя совета директоров и 10 членов совета директоров. Сколькими способами можно это сделать?
	Из фирмы, в которой работают 10 человек, 5 сотрудников должны уехать в командировку. Сколько может быть составов этой группы, если директор фирмы, его заместитель и главный бухгалтер одновременно уезжать не должны?

Запрограммировать решение