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

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

Николай Петрович Морозов

Эта книга продолжает разговор, начатый моей книгой «Элементы теории множеств и математической логики», и является практикумом для студентов гуманитарных вузов по данным математическим дисциплинам. Эти две книги обобщают мой опыт проведения практических занятий и семинаров в СПбГИК и СПб филиале Академии Таможенной Службы.

Николай Морозов

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

1.

Основные формулы комбинаторики

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

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

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

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

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

Если элемент 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.