Читать Элементы комбинаторики и теории вероятностей

Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Все разнообразие комбинаторных формул может быть выведено из двух основных утверждений, касающихся конечных множеств – правило суммы и правило произведения [1] .

Если конечные множества не пересекаются, то число элементов X U {или} Y равно сумме числа элементов множества X и числа элементов множества Y.

То есть, если на первой полке стоит X книг, а на второй Y, то выбрать книгу из первой или второй полки, можно X+Y способами.

Если элемент X можно выбрать k способами, а элемент Y – m способами, то пару (X,Y) можно выбрать k*m способами.

То есть, если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами.

Пересекающиеся множества

Но бывает так, что множества X и Y пересекаются, тогда пользуются формулой, где X и Y – множества, а – область пересечения.

Пример 1. Пусть 20 человек знают английский и 10 – немецкий, из них 5 знают и английский, и немецкий. Сколько человек всего знают один язык?

Ответ: 10+20—5=25 человек.

Очень часто для наглядного решения задачи применяются круги Эйлера.

Пример 2. Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским – 28, французским – 42. Английским и немецким одновременно владеют 8 человек, английским и французским – 10, немецким и французским – 5, всеми тремя языками – 3. Сколько туристов не владеют ни одним языком?

Решение: Выразим условие этой задачи графически (см. рис.2.1). Обозначим кругом тех, кто знает английский, другим кругом – тех, кто знает французский, и третьим кругом – тех, кто знают немецкий.

Рис.2.1.

Рис.2.2.

Всеми тремя языками владеют три туриста, значит, в общей части кругов вписываем число 3. Английским и французским языком владеют 10 человек, а 3 из них владеют еще и немецким. Следовательно, только английским и французским владеют 10—3=7 человек.

Аналогично получаем, что только английским и немецким владеют 8—3=5 человек, а немецким и французским 5—3=2 туриста. Вносим эти данные в соответствующие части рисунка 2.2.

Определим теперь, сколько человек владеют только одним, из перечисленных языков. Немецкий знают 30 человек, но 5+3+2=10 из них владеют и другими языками, следовательно, только немецкий знают 20 человек. Аналогично получаем, что одним английским владеют 13 человек, а одним французским – 30 человек (см. рис.2.3).

Рис.2.3.

По условию задачи всего 100 туристов. 20+13+30+5+7+2+3=80 туристов знают хотя бы один язык, следовательно, 20 человек не владеют ни одним из данных языков.

Пример 3. Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны?

Это пример задачи на размещение без повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными.

Если X-множество, состоящие из n элементов, m≤n, то размещением без повторений из n элементов множества X по m называется упорядоченное множество А, содержащее m элементов из m элементов.