Правила суммы и произведений

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

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

Правило суммы: если объект $$А$$ можно выбрать $$m$$ способами, а объект $$В$$ другими $$n$$ способами, то выбор "либо $$А$$, либо $$В$$ " может быть осуществлен $$m + n$$ способами.

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

Правило произведения: если объект $$А$$ выбран $$m$$ способами и после каждого из таких выборов, объект $$В$$, в свою очередь может быть выбран $$n$$ способами, то выбор " $$A$$ и $$B$$ " в указанном порядке может быть осуществлен $$m \times n$$ способами.

Задача 1 (о шашках)

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

Правила игры в шашки известны.

Сложность этой задачи состоит в том, что для разных положений белой шашки есть разное число положений черной шашки, при которых эту шашку можно бить (рис 7.1).

(рис 7.1)

Если белая шашка стоит на поле $$а1$$, то существует лишь 1 положение, при котором она находится под боем. Если белая шашка стоит на поле $$с3$$, то число искомых положений черной шашки равно 4. Наконец, если белая шашка прошла в "дамки", на поле $$h8$$, то имеется 6 положений черной шашки, на которых ее можно бить белой шашкой.

Складывая полученное число вариантов для каждой позиции, получим 87.

Ясно, что существует ровно столько же положений, при которых черная шашка может бить белую. А положений, при которых обе шашки могут бить друг друга, меньше (рис 7.2).

(рис 7.2)

Например, если белая шашка стоит на краю доски, то ее нельзя бить, где бы ни стояла черная шашка. Поэтому всем полям на краю соответствуют нули. Точно так же находим числа, соответствующие другим полям. Складывая их, получаем, что искомая расстановка возможна 50 способами.

Найдем число положений, при котором ни одна из 2 шашек (черная или белая) не может бить другую. Эту задачу можно было бы решить так же, как и предыдущие, ставя белую шашку на каждое из черных полей и подсчитывая, сколькими способами можно поставить черную шашку так, чтобы ни одна из этих шашек не могла бить другую. Но, здесь проще свести задачу к уже решенной. Для этого сначала найдем общее число положений, которыми можно поставить на доску белую и черную шашки. Белую шашку можно поставить на любую из 32 клеток, следовательно, для черной останется 31 позиция. Отсюда вытекает, что расстановка возможна $$32 \times 31 = 992$$ способами. Но из них 87 способов, при которых черная шашка бьет белую и 87 способов, при которых белая шашка бьет черную. Поэтому надо отбросить $$2 \times 87 = 174$$ способа. Однако следует учесть, что при этом некоторые способы оказываются отброшенными дважды: из-за того, что черная шашка может бить белую шашку, и белая шашка может бить черную шашку. Таких положений 50. Поэтому число положений, в которых ни одна шашка не может бить другую, равно $$992 - 174 + 50 = 868$$.

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

Разобранные примеры позволяют сформулировать общий закон.

Пусть имеется $$N$$ предметов , некоторые из которых обладают свойствами $$a_1,a_2,.....,a_n$$.

Обозначим через $$N(a_i ,a_j ,....,a_k )$$ количество предметов , обладающих свойствами $$a_i ,a_j ,..., a_k$$.(и, может быть , еще некоторыми из других свойств ).

Если надо подчеркнуть , что берутся предметы , не обладающие некоторым свойством, то это свойство пишется со штрихами. Например: $$N(a_1,a_2, a_4')$$ - количество предметов, обладающих свойством $$a_1,a_2$$, но не обладающих свойством $$a_4'$$.

В самом простом случае при одном свойстве $$N(a')=N-N(a)$$, где $$N$$ - общее число элементов, формула очевидна.

Если имеются два свойства $$a_1, a_2 $$, то$$N(a_1'a_2')=N-N(a_1)-N(a_2)+N(a_1, a_2).$$

Действительно , каждый элемент , обладающий свойствами $$a_1$$ и $$a_2$$ одновременно вычитается дважды, следовательно, к этой разности нужно добавить $$N(a_1,a_2)$$.

Обобщением этого правила является следующий принцип включения-исключения:

$$\begin{array}{l} N(a_1', a_2',..., a_n') = N - N(a_1) - N(a_2) - ..... - N(a_n) + N(a_1a_2) + N(a_1a_3) + ..... + N(a_{n-1}a_n)\\ - N(a_1a_2a_3) - N(a_1a_2_a4) - ....- N(a_{n-2}a_{n-1}a_n) +...+(-1)^n N(a_1a_2....a_n) .\\ \end{array}$$

Задача.

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

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

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

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

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

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

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

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

$$N(a_1'a_2'a_3')=100-N(a_1)-N(a_2)-N(a_3)+N(a_1a_2)+N(a_1a_3)+N(a_2a_3)-N(a_1a_2a_3)$$ $$N(a_1)=50; N(a_2)=33; N(a_3)=20; N(a_1a_2)=16; N(a_1a_3)=10; N(a_2a_3)=6; N(a_1a_2a_3)=3.$$ $$N(a_1'a_2'a_3')=100 - 50 - 33 - 20 + 16 + 10 + 6 - 3=26.$$

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

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

Задача "В чем ошибка ?".

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

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

Обозначим:

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

Найдем $$N(a_1'a_2'a_3')$$ - ? то есть число девочек , которое учатся на 3 и ниже и не занимаются спортом.

$$N(a_1)=25; N(a_2)=30; N(a_3)=28; N(a_1a_2)=16; \\ N(a_1a_3)=18; N(a_2a_3)=17; N(a_1a_2a_3)=15; N=45.$$ $$\begin{array}{l} N(a_1'a_2'a_3') = N - N(a_1) - N(a_2) - N(a_3) + N(a_1a_2) + N(a_1a_3) + N(a_2a_3) -N(a_1a_2a_3)=\\ = 45 - 25 - 30 - 28 + 16 + 18 + 17 - 15 = -2.\\ \end{array}$$

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