1.Основные правила комбинаторики
Все разнообразие комбинаторных формул может быть выведено из двух основных утверждений, касающихся конечных множеств – правило суммы и правило произведения.
Правило суммы
Если конечные множества не пересекаются, то число элементов X U {или} Y равно сумме числа элементов множества X и числа элементов множества Y.
То есть, если на первой полке стоит X книг, а на второй Y, то выбрать книгу из первой или второй полки, можно X+Y способами.
Пример 1.Допустим, что нам необходимо добраться из пункта А в пункт Б. При этом, это можно сделать различными способами (смотрите схему 1):
Схема 1.
В этой схеме:
Существует 2 маршрута самолетом.
1 маршрут поездом.
3 маршрута автобусом.
Таким образом, общее количество маршрутов от пункта A до пункта B составляет:
2+1+3 = 6 (маршрутов или способов).
Правило произведения
Если элемент X можно выбрать k способами, а элемент Y – m способами, то пару (X,Y) можно выбрать k*m способами.
То есть, если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10 = 50 способами.
Пример 2.Смотрите схему 2.
Схема 2.
На данной схеме показано применения правила умножения для 5 объектов. Эти объекты можно выбрать 3*2 = 6 способами.
Очень часто для наглядного решения задачи применяются круги Эйлера [3,5,6].
Пример 3. Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским – 28, французским – 42. Английским и немецким одновременно владеют 8 человек, английским и французским – 10, немецким и французским – 5, всеми тремя языками – 3. Сколько туристов не владеют ни одним языком?
Решение
Выразим условие этой задачи графически. Обозначим одним кругом тех, кто знает английский, другим кругом – тех, кто знает французский, и третьим кругом – тех, кто знают немецкий.
Использование кругов Эйлера для постановки данной задачи.
Схема 1.
Английским и французским языком владеют 10 человек, а 3 из них владеют еще и немецким (см. схему 1). Следовательно, только английским и французским владеют 10 – 3 = 7 человек (см. схему 2).
Схема 2.
Аналогично получаем, что только английским и немецким владеют 8 – 3 = 5 человек, а немецким и французским 5 – 3 = 2 туриста. Вносим эти данные в соответствующие части схемы (см. схему 3).
Схема 3.
Определим теперь, сколько человек владеют только одним из перечисленных языков. Немецкий знают 30 человек, но 5+3+2=10 из них владеют и другими языками, следовательно, только немецкий знают 20 человек. Аналогично получаем, что одним английским владеют 13 человек, а одним французским – 30 человек.
Вносим эти данные в соответствующие части схемы (см. схема 4).
По условию задачи всего 100 туристов. 20+13+30+5+7+2+3 = 80 туристов знают хотя бы один язык, следовательно, 20 человек не владеют ни одним из данных языков.
Ответ: 20 человек не владеют ни одним из данных языков.
Схема 4.