5.4. Элементы комбинаторики

 

Во всех вышеперечисленных испытаниях мы рассматривали появление одного  объекта из некоторого конечного множества. При этом число исходов испытания находилось достаточно просто. Однако, чаще всего, при вычислении вероятности какого-либо события необходимо уметь находить число комбинаций выбора нескольких объектов.

Область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов, называется комбинаторикой. В комбинаторных задачах необходимо подсчитать, сколькими способами можно сделать тот или иной выбор, выполнить то или иное требование, выполнить какое-либо условие.

Первые комбинаторные задачи были связаны с азартными играми: картами, костями, «орлянкой». Наиболее любопытные игроки интересовались, например, тем, сколькими способами можно выбросить данное количество очков, бросая две или три кости или сколькими способами можно получить двух тузов при раздаче карт. Основы теоретических положений комбинаторики были разработаны французскими учеными Блезом Паскалем и Пьером Ферма в XVII веке.

Дальнейшее развитие комбинаторика получила в работах Я. Бернулли, Г. Лейбница и Л. Эйлера.

В наше время комбинаторика получила новый толчок для развития в связи с появлением быстродействующих ЭВМ и широким использованием методов дискретной математики. Комбинаторные методы используются для решения транспортных задач, задач по составлению расписаний, для разработки, кодирования и декодирования шифров, в задачах линейного программирования, статистики, теории информации.

Большинство комбинаторных задач может быть решено с помощью двух основных правил: правила суммы и правила произведения.

Правило суммы и правило произведения

Правило суммы для выбора 2 объектов. Если объект А можно выбрать n способами, а объект В – другими m способами, то выбор «или А, или В» можно осуществить n+m способами.

При использовании правила суммы необходимо осознавать, что множество способов выбора объекта А и множество способов выбора объекта В не должно иметь общей части, в противном случае из суммы n+m нужно вычесть величину общей части множеств А и В.

Пример 5.3. Преступник может проникнуть в квартиру либо через входную дверь, либо через окно. Число способов проникновения через дверь – 4, через окно – 3. Сколько всего существует способов проникновения в квартиру?

Решение. Так как способы проникновения в квартиру через окно и через дверь различны, то мы можем воспользоваться правилом суммы. Тогда количество способов проникновения либо через окно, либо через дверь, т.е. количество различных способов проникновения в квартиру, будет равно 4+3=7.

 

 Правило суммы для выбора m объектов. Если объект можно выбрать  способами, объект  другими  способами, объект  отличными от первых двух  способами, и т.д., объект  -  способами, отличными от первых (m-1), то выбор одного из объектов: или объекта , или объекта , …, или объекта  можно осуществить ++…+ способами.

 

Правило произведения для выбора 2 объектов. Если объект А можно выбрать n способами и после этого действия объект В можно выбрать другими m способами, то выбор пары объектов (А, В) можно осуществить способами.

Действительно, каждый из n способов выбора объекта А можно скомбинировать с различными m способами выбора объекта В. А это и приводит к  способам выбора пары (А, В). Правило произведения можно представить с помощью следующей таблицы:

 ,

где ,  i=1, …, n способы выбора объекта А, ,  j=1, …, m способы выбора объекта B и выбор объекта В не зависит от выбора объекта А.

 

Пример 5.4. Во взводе 25 курсантов. Сколько существует способов назначения командира взвода и его заместителя.

Решение. Сначала выберем командира взвода. Число способов выбора равно 25, так как каждый курсант может быть назначен на эту должность. После этого остается 24 курсанта, из которых может быть назначен заместитель командира взвода. Т.е. число способов назначения заместителя командира – 24. По правилу произведения количество способов назначения пары курсантов на указанные должности = 600.

 

Правило произведения для выбора m объектов. Если объект можно выбрать  способами, после каждого такого выбора объект  можно выбрать другими  способами, после этого объект  можно выбрать  способами, и т.д., после выбора каждого из (m-1) объектов -й может быть выбран  способами, то выбор всех элементов (, , …, ) в указанном порядке можно осуществить žž…ž способами.

 

Пример 5.5. Для запирания некоторых автоматических камер хранения, кейсов применяют цифровые кодовые замки, которые отпираются при наборе заданной комбинации цифр. Замок состоит из 4 дисков, на каждом из которых нанесены все цифры. Сколько времени необходимо злоумышленнику для перебора всех комбинаций замка, если на одну комбинацию он тратит 2 секунды.

Решение. При кодировании и открывании замка каждую цифру можно выбрать 10 способами. Всего цифр -  4, причем в комбинации важен порядок расположения цифр. Значит, по правилу произведения общее число комбинаций равно . Таким образом, для перебора всех комбинаций необходимо потратить  секунд или 5 часов 33 минуты и 20 секунд непрерывной работы. Заметим, что найденное время необходимо для перебора всех комбинаций. Но нужная комбинация может вовсе и не быть последней.

Сочетания

Пример 5.6. Из отделения в 5 курсантов необходимо назначить двоих для патрулирования территории института. Сколькими различными способами можно сделать такой выбор?

Решение. В задаче мы не можем применить правило произведения, найдя сначала число способов выбора 1-го курсанта – 5, а потом – второго – 4 и перемножив их, получив 20 различных нарядов. Причиной этого является то, что порядок выбора курсантов в наряд не имеет значения. Важен лишь состав наряда. Поэтому будем решать задачу следующим образом.

Обозначим курсантов следующим образом: a, b, c, d, e. Из пяти курсантов составим всевозможные пары для несения службы в патруле:

ab,  ac, ad, ae,

       bc, bd, be,

          cd, ce,

                de.

Т.к., к примеру, пара ab и bа идентичны, то всего получается 10 различных вариантов наряда.

 

Такой способ решения является весьма нерациональным. Ведь если было бы необходимо выбрать наряд в 7 курсантов из 20, то (как это будет показано ниже) количество различных вариантов наряда составило бы более 77 тысяч. А попытка получить решение подобным образом окончилась бы полным провалом.

 

Для вывода общих формул комбинаторики рассмотрим вопрос: что общего и в чем заключаются отличия в примерах 5.4 и 5.6. Итак, в этих примерах идет речь о некотором конечном множестве элементов и о количестве его подмножеств, удовлетворяющих заданным требованиям. Так, в примере 5.4 рассматривалось множество курсантов учебной группы, состоявшее из 25 элементов (курсантов), и требовалось найти количество подмножеств, состоящих из 2 элементов (командир взвода и его заместитель). В примере 5.6 из пятиэлементного множества выделялись двухэлементные подмножества (наряды) и подсчитывалось их число.

Различие примеров заключалось в том, что  в примере 5.6 подмножества различались лишь составом курсантов, а порядок элементов не имел значения. Действительно, наряд, состоящий из курсантов Иванова и Петрова, ни чем не отличался от наряда, состоящего из курсантов Петрова и Иванова. В примере 5.4, напротив, подмножества отличались не только своим составом, но и порядком расположения элементов. Назначение Иванова – командиром взвода, а Петрова – заместителем командира взвода отличается от комбинации выбора: Петров – командир взвода, Иванов – его заместитель.

Если подмножества различаются не только составом элементов, но и порядком следования элементов, то они называются упорядоченными. Неупорядоченные подмножества различаются только составом входящих в них элементов. Так, у множества, состоящего из 5 элементов, имеется 10 неупорядоченных подмножеств, состоящих из 2 элементов (см. пример 5.6), и 20 упорядоченных.

 

Пусть имеется множество, состоящее из n элементов. Каждое его неупорядоченное подмножество, содержащее k элементов, называется сочетанием из n элементов по k элементов. Из определения вытекает, что .

Сочетания из n элементов по k элементов – все k - элементные подмножества n – элементного множества, различающиеся только составом элементов. Подмножества, отличающиеся друг от друга порядком следования элементов, не считаются различными. Например, для четырехэлементного множество a, b, c, d сочетаниями из 4 элементов по 3  элемента являются подмножества: abc, abd, acd, bcd.

Число всех сочетаний из n по k элементов обозначается специальным символом . (Читается: «число сочетаний из n по k» или «С из n по k»). C – первая буква французского слова «combinasion» - «сочетание».

 Число сочетаний из n по k элементов определяется следующей формулой:

.                                              (5.2)

Здесь мы использовали функцию факториала:

 (nÎN), 0!=1.

Запись читается: «n факториал».

1!=1,   2!=1 2,  3!=1 2 3=6,  4!=1 2 3 4=24,  5!=1 2 3 4 5=120, 6!=1 2 3 4 5 6=720  и т.д.

Из приведенных выше вычислений факториала ряда чисел очевидно следующее равенство:

n!=(n-1)! n для n>0.

 

Представив n! в виде n!=(n-k)! (n-k+1) (n-k+2) … (n-1) n и сократив числитель и знаменатель формулы (5.2) на (n-k)!, получим следующую формулу для числа сочетаний из n по k элементов:

   (для k>0)                        (5.3)

Если k=0, то . Действительно, существует только одно пустое (не содержащее элементов) подмножество множества из n элементов.

 

Пример 5.7. Сколько различных нарядов, состоящих из 7 курсантов, можно составить из взвода численностью 20 курсантов?

Решение. Количество различных нарядов равно числу сочетаний из 20 по 7 - .  По формуле (5.3) получим

.

Итак, количество различных нарядов равно 77520.

 

Пример 5.8. Сколько поединков по борьбе должны быть проведены между 15 спортсменами, если каждый из них должен встретиться с каждым.

Решение. Должно состояться столько поединков, сколько существует двухэлементных подмножеств у множества, состоящего из 15 элементов, т.е. их число равно . По формуле (5.3) получаем .

Итак, при встрече каждого из 15 спортсменов с каждым должно состояться 105 поединков.

Размещения

Пусть имеется множество, состоящее из n элементов. Каждое его упорядоченное подмножество, содержащее k элементов, называется размещением из n элементов по k элементов. Из определения вытекает, что .

Размещения из n элементов по k элементов – все k-элементные подмножества n – элементного множества, различающиеся не только составом элементов, но и порядком их следования. Например, для четырехэлементного множества a, b, c, d размещениями из 4 элементов по 3  элемента являются подмножества:

abc, acb, bac, bca, cab, cba,

abd, adb, bad, bda, dab, dba,

acd, adc, cad, cda, dac, dca,

bcd, bdc, cbd, cdb, dbc, dcb.

 

Число всех размещений из n по k элементов обозначается символом . (Читается: «число размещений из n по k» или «А из n по k»). А – первая буква французского слова «arrangement», что означает размещение, приведение в порядок.

 Число размещений из n по k элементов определяется следующей формулой:

.                                                   (5.4)

Используя снова равенство n!=(n-k)! (n-k+1) (n-k+2) … (n-1) n и сократив числитель и знаменатель формулы (5.4) на (n-k)!, получим следующую формулу для числа размещений из n по k элементов:

,         где k>0.                (5.5)

Пример 5.9. Сколько различных нарядов, состоящих из 7 курсантов, можно составить из взвода численностью 20 курсантов, если каждый курсант в наряде отличается от другого своими обязанностями?

Решение. Теперь уже количество различных нарядов равно не числу сочетаний из 20 курсантов по 7 курсантам, а числу размещений из 20 по 7  - . По формуле (5.5) вычисляем = 390 700 800.

 

Пример 5.10. Сколько существует различных цифровых номеров автомашин, цифры которых не повторяются?

Решение. Если цифры  номера машины не повторяются, то количество комбинаций номеров равно числу размещений из 10 (общее количество цифр) по 3 (количество цифр в номере автомашины), т.е. равно

.

Перестановки

Перестановками из n элементов называются размещения из n элементов по n  элементов.

Перестановки являются частным случаем размещения. Так как каждая перестановка содержит все n элементов множества, то различные перестановки различаются только порядком следования элементов. Число перестановок из n элементов обозначают символом . Р – первая буква французского слова «permutation» - «перестановка».

Для того, чтобы вычислить число перестановок, подставим k=n в формулу (5.4) для нахождения размещений из n  по n элементов:

 .                                           (5.6)

Значит, число перестановок из n  элементов . Т.е. множество из n элементов можно упорядочить n! способами.

 

Еще раз перепишем формулы (5.2), (5.4) и (5.6) в виде:

,    ,        .

Отсюда очевидно, что . Число размещений из n элементов по k элементов равно числу сочетаний из n элементов по k элементов, умноженному на число перестановок из k элементов.

 

Пример 5.11. Сколько существует вариантов проведения собрания учебной группы, если количество выступающих на собрании – 4?

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

Предыдущая | Главная | Глава 5 | Следующая