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

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

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

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

N(a₁ или а₂ или … или а_n)=N(a₁)+N(a₂)+…+N(a_n)-N(a₁ и a₂)-N(a₁ и a₃)-…-N(a₁ и a_n)-…-N(a_n-1 и a_n)+N(a₁ и a₂ и a₃)+…N(a_n-2 и a_n-1 и a_n)+…+(-1)^n-1N(a₁ и a₂ и … и a_n).

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

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

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

N(a₁ или а₂ или … или а_n-1, или а_n)= N((a₁ или а₂ или … или а_n-1) или а_n) =

=N(a₁ или а₂ или … или а_n-1)+N(а_n) – N ((a₁ или а₂ или … или а_n-1) и а_n) = =[N(a₁)+N(a₂)+…+N(a_n-1)-N(a₁ и a₂) – N (a₁ и a₃) – … – N (a₁ и a_n-1) – …– N (a_n-2 и a_n-1)+

+N(a₁ и a₂ и a₃)+…+N(a_n-3 и a_n-2 и a_n-1)+…+ +(-1)^n-2 N(a₁ и a₂ и … и a_n-1)] +N(а_n) –

– N((a₁ и а_n)или (а₂ и а_n)или … или (а_n-1 и а_n))=

=[N(a₁)+N(a₂)+…+N(a_n-1)-N(a₁ и a₂) – N(a₁ и a₃) – …– N (a₁ и a_n-1) – …– N (a_n-2 и a_n-1)+

+N(a₁ и a₂ и a₃)+…+ +N(a_n-3 и a_n-2 и a_n-1)+…+ +(-1)^n-2 N(a₁ и a₂ и … и a_n-1)] +N(а_n) –

– [N(a₁ и а_n)+N (а₂ и а_n)+ … +N(а_n-1 и а_n) – N (a₁ и а₂ и a_n) – … N(a_n-2 и а_n-1 и а_n)+…+

+(-1)^n-2N(a₁ и a₂ и … и а_n)]=

=N(a₁)+N(a₂)+…+N(a_n) – N (a₁ и a₂) – N (a₁ и a₃) – …– N (a₁ и a_n) –…– N (a_n-1 и a_n)+

+N(a₁ и a₂ и a₃)+…+N(a_n-2 и a_n-1 и a_n)+…+ (-1)^n-1 N(a₁ и a₂ и … и a_n)

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

Задача. Исследователь рынка сообщает следующие данные. Из 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. Ответ на вопрос задачи – 2ⁿ.

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

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

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

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

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

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

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

Дата добавления: 2014-12-29