Элементы комбинаторики и теории вероятностей
Шрифт:
1. Основные формулы комбинаторики
Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Все разнообразие комбинаторных формул может быть выведено из двух основных утверждений, касающихся конечных множеств – правило суммы и правило произведения [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
Рис.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 элементов.
Количество всех размещений из n элементов по m обозначают
(2.1)
n! – n-факториал (factorial анг. сомножитель) произведение чисел натурального ряда от 1 до какого либо числа n. n!=1*2*3*…*n. 0!=1.
Значит, ответ на выше поставленную задачу будет
В случае n=m (см. размещения без повторений) А из n элементов по m называется перестановкой множества x.
Количество всех перестановок из n элементов обозначают Pn.
Pn=n!
Действительно при n=m:
(2.2)
Пример 4. Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если цифры в числе не повторяются?
Решение:
Найдем количество всех перестановок из этих цифр: P6=6!=720
Пример 5. «Проказница Мартышка, Осел, Козел, Да косолапый Мишка
Затеяли играть квартет …Стой, братцы стой! – Кричит Мартышка, – погодите! Как музыке идти? Ведь вы не так сидите…
И так, и э так пересаживались – опять музыка на лад не идет.
Тут пуще прежнего пошли у них раздоры И споры, Кому и как сидеть…»
Вероятно, крыловские музыканты так и не перепробовали всех возможных мест. Однако способов не так уж и много. Сколько?
Решение
Здесь речь идет о перестановке из четырех элементов,
Значит, возможно, P4=4!=24 варианта перестановок.