Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Общий вид формулы включения и исключения




Пусть имеется n предметов, некоторые из которых обладают свойствами а1, а2, …, аn. Каждый предмет может либо не обладать ни одним из этих свойств, либо обладать одним или несколькими свойствами одновременно.

Обозначим N(аi или aj или … или ak) количество предметов, обладающих хотя бы одним из свойств аi, aj, … ak.

Для того чтобы определить количество предметов, обладающих хотя бы одним из свойств a1, a2…an, используют формулу:

N(a1 или а2 или … или аn)=N(a1)+N(a2)+…+N(an)-N(a1 и a2)-N(a1 и a3)-…-N(a1 и an)-…-N(an-1 и an)+N(a1 и a2 и a3)+…N(an-2 и an-1 и an)+…+(-1)n-1N(a1 и a2 и … и an).

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

При одном свойстве формула очевидна. Каждый предмет либо обладает этим свойством, либо не обладает им. N(a)=N(a)

Предположим, что формула доказана для случая когда число свойств меньше или равно n-1. Тогда:

N(a1 или а2 или … или аn-1, или аn)= N((a1 или а2 или … или аn-1) или аn) =

=N(a1 или а2 или … или аn-1)+N(аn) – N ((a1 или а2 или … или аn-1) и аn) = =[N(a1)+N(a2)+…+N(an-1)-N(a1 и a2) – N (a1 и a3) – … – N (a1 и an-1) – …– N (an-2 и an-1)+

+N(a1 и a2 и a3)+…+N(an-3 и an-2 и an-1)+…+ +(-1)n-2 N(a1 и a2 и … и an-1)] +N(аn) –

– N((a1 и аn)или (а2 и аn)или … или (аn-1 и аn))=

=[N(a1)+N(a2)+…+N(an-1)-N(a1 и a2) – N(a1 и a3) – …– N (a1 и an-1) – …– N (an-2 и an-1)+

+N(a1 и a2 и a3)+…+ +N(an-3 и an-2 и an-1)+…+ +(-1)n-2 N(a1 и a2 и … и an-1)] +N(аn) –

– [N(a1 и аn)+N (а2 и аn)+ … +N(аn-1 и аn) – N (a1 и а2 и an) – … N(an-2 и аn-1 и аn)+…+

+(-1)n-2N(a1 и a2 и … и аn)]=

=N(a1)+N(a2)+…+N(an) – N (a1 и a2) – N (a1 и a3) – …– N (a1 и an) –…– N (an-1 и an)+

+N(a1 и a2 и a3)+…+N(an-2 и an-1 и an)+…+ (-1)n-1 N(a1 и a2 и … и an)

Что и требовалось доказать.

Задача. Исследователь рынка сообщает следующие данные. Из 1000 опрошенных 811 нравится шоколад, 752 нравятся конфеты и 418 – леденцы, 570 нравится шоколад и конфеты, 356 – шоколад и леденцы, 348 – конфеты и леденцы, а 297 – все три вида сладостей. Показать, что в этой информации содержатся ошибки.

Решение. Обозначим через А свойство опрошенного любить шоколад, через В – свойство опрошенного любить конфеты, через С – свойство опрошенного любить леденцы.

По условию задачи N(А)=811, N(В)=752, N(С)=418, N(А и В)=570, N(А и С)=356,

N(В и С)=348, N(А и В и С)=297.

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

N(А или В или С)=N(А)+N(В)+N(С)-N(А и В)-N(А и С)-N(В и С)+N(А и В и С)=811+752+418-570-356-348+297=1004.

Опрошено было всего 1000 человек, следовательно, в предложенной информации содержатся ошибки.

Размещения с повторениями

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

Задача. Каково число последовательностей длины n, состоящих из 0 и 1?

Решение. Заметим, что последовательность длины n можно получить из последовательности длины n – 1, дописывая в конец последовательности либо 1, либо 0. Значит, из каждой последовательности длины n – 1 получается две последовательности длины n. Ответ на вопрос задачи – 2n.

Данная задача относится к классу задач о размещении с повторениями.

Размещениями с повторениями из n элементов по k называются всевозможные комбинации по k элементов, составленные из элементов данных n видов. При этом в комбинацию могут входить и предметы одного вида, а две комбинации считаются различными, если они отличаются друг от друга или видом входящих в них элементов, или порядком этих элементов.

Количество размещений с повторениями обозначается и равно nk.

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

1. При к=1 каждое размещение с повторениями состоит из одного элемента. Его можно выбрать n способами. Таким образом, =n1.

2. Предположим, что верно равенство =nk-1. Размещения с повторениями из n элементов по k можно получить из размещений с повторениями из n элементов по k-1 элементу добавлением любого из n элементов.

По правилу произведения получаем = ∙n=nk-1 ∙n=nk




Поделиться с друзьями:


Дата добавления: 2014-12-29; Просмотров: 481; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.013 сек.