Формула включения и исключения.

Чтобы найти мощность объединения двух множеств нужно из суммы их мощностей вычесть мощность их пересечения. При этом каждый элемент объединения будет посчитан ровно один раз.

.

Аналогичная формула имеет место для трех множеств.

Она справедлива и в общем случае

Докажем эту формулу, называемую формулой включения и исключения. Пусть элемент x входит ровно в k подмножеств . Вклад, который дает этот элемент в правую часть, равен

,

как это следует из тождества 4 для биномиальных коэффициентов (п. 1.2.). Поэтому в правой части будет полное число элементов, что и доказывает формулу.

В практических задачах часто имеется некоторое множество U и система его подмножеств U₁,…,U_m. Требуется найти число элементов множества U, не принадлежащих ни одному из множеств U₁,…,U_m. В этом случае формула включения и исключения выглядит следующим образом

.

Рассмотрим пример. В группе, состоящей из 20 человек, 6 знают немецкий, 7 – французский и 8 – английский язык, 3 человека знают немецкий и французский, 4 – немецкий и английский, 5 – французский и английский и один человек знает все 3 языка. Сколько человек не знают ни одного иностранного языка?

Решение: 20-(6+7+8)+(3+4+5)-1=10.

Другой пример. Пусть требуется найти число целочисленных решений системы

Введем новые переменные , , . Система перепишется в виде

Пусть U – множество решений системы

U₁ – множество решений системы

U₂ – множество решений системы

U₃ – множество решений системы

согласно п. 1.1.

Чтобы найти мощность множества U₁, достаточно в соответствующей системе сделать замену . Это дает

Аналогично, ,

Далее, легко видеть, что

, ,

Поэтому в соответствии с формулой включения и исключения число решений исходной системы равно

В качестве ещё одного примера рассмотрим известную задачу о беспорядках. Требуется найти число перестановок чисел 1,2,…,n, в которых никакое число i не стоит на i – ом месте. Всего перестановок . Перестановок, в которых число i стоит на i – ом месте, Перестановок, в которых два различных числа i и j стоят на своих местах, и т.д. По формуле включения и исключения имеем

Отметим, что выражение в скобках с ростом стремится к .

Практическое занятие №2 по теме: «Элементы комбинаторики.»

1) Разложить по формуле бинома Ньютона: 1. ; 2. .

Решение:

1.

2.

.

2) Найти 6-й член разложения (5х² – 6а²)¹⁰.

Решение:

3) Вычислить

Решение:

.

4) В разложении вычислить член, не содержащий “x”.

Решение: .

.

, .

T₅ – не содержит “x”,

.

5) Сколько чисел в первой сотне которые, не делятся нацело ни на 2, ни на 3, ни на 5?

Эта задача решается с помощью формулы включения-исключения.

Введем обозначения:

- свойство чисел делиться на 2;

- свойство чисел делиться на 3;

- свойства чисел делиться на 5;

Тогда, означает,что число делится на 6, означает,что число делится на 10, означает,что число делится на 15, наконец, означает, что число делится на 30.

По формуле включения-исключения имеем

Таким образом, 26 чисел из 100 не делятся ни на 2,ни на 3, ни на 5.

Аналогичная задача. Сколько чисел не делятся нацело на 2, 3, 5, из первой тысячи? Эти задачи в математике были сформулированы математиком Эратосфеном. В математике Эратосфена интересовал как раз вопрос о том, как найти все простые числа среди натуральных чисел от до .

6) Староста одной группы дал следующие сведения о студентах:

в группе учатся 45 студентов, в том числе 25 юношей. 30 студентов учатся на хорошо и отлично, в том числе 16 юношей. Спортом занимаются 28 студентов, в том числе 18 юношей и 17 студентов, которые учатся на хорошо и отлично. 15 юношей учатся на 4 и 5 и занимаются спортом.

Обозначим:

- принадлежность к мужскому полу; - хорошую успеваемость; - увлечение спортом.

Найдем -? то есть число девочек, которое учатся на 3 и ниже и не занимаются спортом.

Но, отрицательного ответа не может быть, следовательно, в сведениях есть ошибка.

IV. ТЕОРИЯ ГРАФОВ

Основные понятия

Изучаемые явления, процессы, системы иногда удобно представить графически. Графические представления - удобный способ иллюстрации содержания различных понятий. Например, диаграмма Эйлера–Винна, гистограмма, круговые диаграммы и т.д. С помощью графиков можно судить о количественных соотношениях сравниваемых объектов, что значительно упрощает их анализ. С помощью графов решают многие задачи управления, сетевого планирования, принятия решений в условиях неопределенностей. При этом не все детали рисунка одинаково важны, например, длина, кривизна ребер, взаимное расположение вершин на плоскости. Графическое представление – это описание исследуемой системы с помощью вершин и ребер (дуг), соединяющих эти вершины.

Определение. Графом G называется совокупность двух множеств: вершин V и ребер E, между элементами которых определено отношение инцидентности – каждое ребро еÎЕ инцидентно ровно двум вершинам , , которые оно соединяет.

При этом вершина и ребро е называются инцидентными друг другу, а вершины и , являющиеся для ребра её концевыми точками, называются смежными. Часто вместо и еÎЕ пишут соответственно , еÎG. Ребро, соединяющее две вершины, может иметь направление от одной вершины к другой. Тогда ребро называется направленным (ориентированным) или дугой и изображается стрелкой, направленной от вершины, называемой началом, к вершине, называемой концом. Граф, содержащий направленные ребра (дуги) с началом и концом , называется ориентированным (ор-графом) и ненаправленные - неориентированным (н-графом). Ребра, инцидентные одной и той же паре вершин, называются параллельными (кратными). Граф, содержащий кратные ребра, называется мультиграфом. Ребро, концевые вершины которого совпадают, называется петлей. Если множество его элементов графа (вершин и ребер) конечно, то он называется конечным. Если же множество вершин V (ребер Е) пусто, то граф называется пустым. Граф без петель и кратных ребер называется полным, если каждая пара вершин соединена ребром.

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

Локальной степенью (или просто степенью) вершины н – графа G называется количество ребер , инцидентных вершине . В н-графе сумма степеней всех вершин равна удвоенному числу ребер “m” графа, т.е. четна (в графе с петлями петля дает вклад 2 в степень вершины).

В н-графе число вершин нечетной степени четно. Для вершин графа определяются две локальные степени:

1) - число ребер с началом в вершине (количество выходящих из ребер);

2) - количество входящих в вершину ребер, для которых эта вершина является концом.

Петля дает вклад 1 в обе эти степени. В орграфе суммы степеней всех вершин и равны количеству ребер этого графа и равны между собой:

.

Графы G₁ и G₂ равны G₁=G₂, если их множества вершин и ребер (выраженных через пары инцидентных им вершин) совпадают: V₁=V₂ и Е₁=Е₂. Граф G считается полностью заданным, если нумерация его вершин и ребер зафиксирована. Графы, отличающиеся только нумерацией вершин и ребер, называются изоморфными.

Пример 1:

Рис 1.

G₁ – G₇ – неориентированные графы;

G₈ – G₁₂ – орграфы, G₁ = G₂ ;

G₇ – не является полным, хотя каждая пара вершин соединена ребром, но имеется одна петля;

G₃ – все вершины этого графа являются изолированными, т.е. Е = 0;

G₄ – G₅ – являются дополнением друг другу ;

G₆ – мультиграф, т.к. содержит кратные ребра а и в, е и f;

G₈ – ориентированный граф, канонически соответствующий Н – графу G₅;

G₉ – G₁₀ – не равны, т.к. имеют отличающиеся ребра;

G₁₁ – ор.граф (мультиграф), а и в – кратные;

G₁₂ – не мультиграф (а и в различно ориентированы).

Пример 2:

Рис.2

G₁ и G₃ – оба графа имеют по четыре вершины V = {1, 2, 3,4}.

Степени вершины н – графа : r (1) =3, r (2) =4, r (3) =3, r (4) =4.

Тогда , т.е. равна , где 7 – число ребер графа.

Степени вершин орграфа :

r₁ (1) =2, r₁ (2) =3, r₁ (3) =1, r₁ (4) =1, r₂ (1) =1, r₂ (2) =1, r₂ (3) =2, r₂ (4) =3.

Тогда (число ребер).

Не нашли, что искали? Воспользуйтесь поиском: