Kitobni o'qish: «Элементы комбинаторики и теории вероятностей»

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.

Всеми тремя языками владеют три туриста, значит, в общей части кругов вписываем число 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 человек не владеют ни одним из данных языков.

1.3. Размещения без повторений

Пример 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.

Значит, ответ на выше поставленную задачу будет

1.4. Перестановки без повторений

В случае n=m (см. размещения без повторений) А из n элементов по m называется перестановкой множества x.

Количество всех перестановок из n элементов обозначают P_n.

P_n=n!

Действительно при n=m:

(2.2)

Пример 4. Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если цифры в числе не повторяются?

Решение:

Найдем количество всех перестановок из этих цифр: P₆=6!=720

Пример 5. «Проказница Мартышка, Осел, Козел, Да косолапый Мишка

Затеяли играть квартет …Стой, братцы стой! – Кричит Мартышка, – погодите! Как музыке идти? Ведь вы не так сидите…

И так, и э так пересаживались – опять музыка на лад не идет.

Тут пуще прежнего пошли у них раздоры И споры, Кому и как сидеть…»

Вероятно, крыловские музыканты так и не перепробовали всех возможных мест. Однако способов не так уж и много. Сколько?

Решение

Здесь речь идет о перестановке из четырех элементов,

Значит, возможно, P₄=4!=24 варианта перестановок.

1.5. Сочетания без повторений.

Сочетанием без повторений называется такое размещение, при котором порядок следования элементов не имеет значения.

Всякое множество X состоящее из m элементов, называется сочетанием из n элементов по m.

Таким образом, количество вариантов при сочетании будет меньше числа вариантов размещений.

Число сочетаний из n элементов по m обозначается.

(2.3).

Пример 6. У одного человека 7 книг по математике, а у второго – 9. Сколькими способами они могут обменять друг у друга две книги на две книги.

Решение:

Так как порядок следования книг не имеет значения, то выбор 2_ух книг – сочетание. Первый человек может выбрать 2 книги

способами. Второй человек может выбрать 2 книги

. Значит всего по правилу произведения возможно 21*36=756 вариантов.

1.6. Решение типовых задач.

Задача 1. Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?

Решение: X=17, Y=13

По правилу суммы X U Y=17+13=30 тем.

Задача 2. Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один билет из спортлото или автомотолотереи?

Решение: Так как денежно-вещевая лотерея в выборе не участвует, то всего 6+10=16 вариантов.

Задача 3. Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать?

Решение: Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 12*3=36 вариантов переплета.

Задача 4. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

Решение: В таких числах последняя цифра будет такая же, как и первая, а предпоследняя – как и вторая. Третья цифра будет любой. Это можно представить в виде XYZYX, где Y и Z -любые цифры, а X – не ноль. Значит по правилу произведения количество цифр одинаково читающихся как слева направо, так и справа налево равно 9*10*10=900 вариантов.

Задача 5. Сколькими способами 4 юноши могут пригласить четырех из шести девушек на танец?

Решение: два юноши не могут одновременно пригласить одну и ту же девушку. И варианты, при которых одни и те же девушки танцуют с разными юношами, считаются разными, поэтому:

Возможно 360 вариантов.

Задача 6. Сколько трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются одновременно), если на нем всего 10 цифр.

Решение:

Так как кнопки нажимаются одновременно, то выбор этих трех кнопок – сочетание. Отсюда возможно вариантов.

Задача 7. У одного человека 7 книг по математике, а у второго – 9. Сколькими способами они могут обменять друг у друга две книги на две книги.

Решение:

Так как порядок следования книг не имеет значения, то выбор 2_ух книг – сочетание. Первый человек может выбрать 2 книги способами. Второй человек может выбрать 2 книги. Значит всего по правилу произведения возможно 21*36=756 вариантов.

Задача 8. При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать?

Решение:

Первый игрок делает выбор из 28 костей. Второй из 28—7=21 костей, третий 14, а четвертый игрок забирает оставшиеся кости.

Следовательно, возможно.