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

Правило произведения

Задача.В магазине «Все для чая» есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем?

Решение.Чашку можно выбрать 5 способами. Для каждого способа выбора чашки существует 3 способа выбора блюдца. Таким образом, имеем 5∙3=15 способов выбора пары предметов.

Если некоторый объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А, В) можно осуществить m∙n способами. Это утверждение называют правилом произведения.

Для доказательства правила произведения заметим, что каждый из m способов выбора объекта А можно совместить с n способами выбора объекта В. В свою очередь, это приводит к m∙n способам выбора пары (А, В).

Может возникнуть ситуация, когда необходимо составить комбинацию из большего числа элементов.

Задача.В магазине «Все для чая» есть еще 4 чайные ложки. Сколькими способами можно купить комплект из чашки, блюдца и ложки?

Решение.Из решения предыдущей задачи известно, что существует 5∙3=15 способов выбора пары предметов чашка – блюдце. Для каждого способа выбора этой пары существует 4 способа выбора ложки. Таким образом, по правилу произведения имеем 5∙3∙4=60 способов выбора комплекта из чашки, блюдца и ложки.

Правило суммы

Задача.Из города А в город Б ведет 6 дорог, а из города Б в город В – 4 дороги, из города А в город Г – 2 дороги, и из города Г в город В – тоже 2 дороги. Сколькими способами можно проехать от А до В?

Решение.Из города А в город В можно попасть либо через город Б, либо через город Г. По правилу произведения через город Б можно проехать 6∙4=24 способами, через город Г – 2∙2=4 способами. Тогда из города А в город В можно попасть 24+4=28 способами.

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

Если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить m+n способами.

При использовании правила суммы необходимо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В.

В рассмотренной выше задаче число выборов после каждого шага зависит от того, какие элементы были выбраны на предыдущих шагах. Рассмотрим пример ещё одной такой задачи.

Задача. Сколькими способами можно поставить на шахматную доску белого и черного королей так, чтобы получилась допустимая по правилам игры комбинация?

Решение.Шахматное поле имеет 64 клетки, поэтому белого короля можно поставить 64 способами. Как известно, король бьет клетки, расположенные непосредственно рядом с ним. Таким образом, если король находится в углу, то под боем находятся 3 клетки, если у стены, то – 5, если в центре, то – 8. Очевидно, что ставить черного короля нельзя в ту же клетку, где находится белый король, и в клетку, которая находится под боем. Так как существует 4 способа поставить короля в угол, 24 способа – у стены и 36 способов – в центре поля, то ответ на вопрос задачи вычисляется следующим образом: 4∙(64–4)+24∙(64–6)+36∙(64–9)=3612

Рассмотрим теперь вопрос, как вычислить количество способов выбора объекта «либо А, либо В», если известно, что некоторые из способов выбора объекта А совпадают с некоторыми способами выбора объекта В.

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

Задача.Из-за различия программ в школах Ярославской области студенты первого курса физико-математического факультета разделились на следующие группы: 47 человек знают алгоритмический язык, 35 – язык программирования Паскаль и 23 – оба языка программирования. Сколько человек на курсе знают хотя бы один язык программирования?

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

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

59=23+24+12=23+(47–23)+(35–23)=47+35–23.

Таким образом, к числу студентов, знающих алгоритмический язык, необходимо прибавить число знающих язык Паскаль. При этом некоторые студенты попадают в оба списка и оказываются «прибавленными дважды». Это как раз те, которые знают оба языка программирования. Вычитая их число, получаем число студентов, знающих хотя бы один язык.

Запишем формулу в общем виде.

Обозначим через а1 свойство студента знать алгоритмический язык, через а2 – свойство студента знать Паскаль, через N(а1) – количество студентов, знающих алгоритмический язык, через N(а2) – количество студентов, знающих Паскаль. Тогда

N(а1или а2)= N(а1)+N(а2)-N(а1и а2).

Эту формулу называют формулой включения и исключения.

Задача.Теперь усложним задачу. Пусть 47 студентов знают алгоритмический язык, 35 – язык Паскаль, 23 – Паскаль и алгоритмический язык, 20 – знают Бейсик, 12 – алгоритмический язык и Бейсик, 11 – Паскаль и Бейсик, 5 – все три языка. Вопрос тот же: сколько человек на курсе знают хотя бы один язык программирования?

Решение.Решая эту задачу аналогично предыдущей, получим:

47+35+20-23-12-11+5=61.

Используя обозначения, предложенные выше, получаем следующую формулу для трех свойств:

N(а1или а2 или а3)= N(а1)+N(а2)+N(а3)-N(а1и а2) -N(а1и а3) -N(а2и а3) +N(а1и а2 и а3)

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

Пусть имеется 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.

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

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

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

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