Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




 

В машиностроении рассматриваются конечные множества. Чтобы подсчитать число элементов конечного множества, образованного в результате объединения или пересечения некоторых конечных множеств, используется комбинаторный анализ. Мы рассмотрим теоремы сложения и умножения, а так же формулу включений и исключений.

 

Теорема 2.2. (Теорема сложения)

Пусть – конечные попарно непересекающиеся множества, т.е. . Тогда

(2.3.1.)

Доказательство. Докажем теорему методом математической индукции.

Базис индукции. Пусть n=2. Пусть множества X1=A и X2=B, мощности которых соответственно равны k1 и k2, т.е. |A|=k1, |B|=k2. Так как AÇB=Æ, то

.

Индуктивный переход. Пусть теорема верна для n. Покажем, что для n+1 будет тоже справедливо. Тогда

Теорема 2.3. (Теорема умножения)

Пусть заданы конечные множества . Тогда

(2.3.2.)

т.е. число элементов декартова произведения множеств равно произведению количеств элементов сомножителей.

Доказательство. Докажем теорему методом математической индукции.

Базис индукции. Пусть n=2. Пусть множества X1=A и X2=B, мощности которых соответственно равны k1 и k2, т.е. |A|=k1, |B|=k2. Первый компонент упорядоченной пары можно выбрать k1 способами, второй – k2 способами. Таким образом, всего имеется k1×k2 различных упорядоченных пар. Значит,

.

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

Пример 2.7. Сколько существует целых чисел между 0 и 1000, содержащих ровно одну цифру 6?

Решение. Пусть S – множество целых чисел между 0 и 1000, содержащих ровно одну цифру 6. Рассмотрим три подмножества S1, S2 и S3 множества S.

S1 – множество, которое содержит число, состоящее из одной цифры, и эта цифра 6;

S2 – множество, содержащее двузначные числа ровно с одной цифрой, равной 6;

S3 – множество, содержащее трехзначные числа ровно с одной цифрой, равной 6.

Множество S1 содержит только один элемент – число 6. Значит, | S1|=1.

В множестве S2 каждый элемент, содержащей 6, имеет ее либо первой, либо второй цифрой. Если 6 – вторая цифра, то существует 8 различных чисел, которые будут стаять на первом месте, поскольку первое число не может быть 0 или 6. Если 6 – первая цифра, то таких чисел 9, поскольку вторая цифра не может быть 6. Таким образом, S2 содержит 8+9=17 элементов, т.е. | S2|=17.

Элемент из S3 содержит 6 как первою, вторую или третью цифру. Если 6 – первая цифра, то существует 9 вариантов выбора второй цифры и 9 вариантов выбора третьей цифры. Согласно комбинаторному принципу умножения, S3 содержит 9 ´9=81 чисел с первой цифрой. Если 6 – вторая цифра, то имеются 9 вариантов выбора третьей цифры и 8 вариантов выбора первой цифры, поскольку первая цифра не может быть нулем. Следовательно, S3 содержит 9´8=72 числа, у которых 6 – вторая цифра. Аналогично, S3 содержит 72 числа, у которых 6 – третья цифра. Следовательно, всего S3 содержит 81+72+72=225 элементов, т.е. |S3|=225.

Поскольку и множества S1, S2 и S3 попарно непересекающиеся, то

.

,

Поставим задачу подсчитать число элементов в объединении

X=X1ÈX2È…ÈXm

конечных множеств , которые могут иметь непустые пересечения между собой, т.е. объединение может быть не разбиением. В общем случае имеет место следующая теорема, которую нетрудно доказать методом математической индукции. Но мы примем теорему без доказательства.


Поделиться:

Дата добавления: 2015-07-26; просмотров: 380; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты