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

Лекция 2

Согласно классическому определению подсчет вероятности события А сводится к подсчету числа благоприятствующих ему исходов. Делают это обычно комбинаторными методами.

Комбинаторика раздел математики, в котором изучаются задачи выбора элементов из заданного множества и расположения их в группы по заданным правилам, в частности задачи о подсчете числа комбинаций (выборок), получаемых из элементов заданного конечного множества. В каждой из них требуется подсчитать число возможных вариантов осуществления некоторого действия, ответить на вопрос «сколькими способами?».

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

Правило умножения (основной принцип): если из некоторого конечного множества первый объект (элемент x) можно выбрать n способами и после каждого такого выбора второй объект (элемент у) можно выбрать m способами, то оба объекта (x и y) в указанном порядке можно выбрать n´m способами.

Этот принцип, очевидно, распространяется на случай трех и более объектов.

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

а) цифры не повторяются?

б) цифры могут повторяться?

Имеется 5 различных способов выбора цифры для первого места (слева в трехзначном числе). После того как первое место занято, например, цифрой 2, осталось четыре цифры для заполнения второго места. Для заполнения третьего места остается выбор из трех цифр. Следовательно, согласно правилу умножения имеется 5×4×3 = 60 способов расстановки цифр, т. е. искомое число трехзначных чисел есть 60. (Вот некоторые из этих чисел: 243, 541, 514, 132,...) Понятно, что если цифры могут повторяться, то трехзначных чисел 5×5×5= 125. (Вот некоторые из них: 255, 333, 414, 111, 122,...)

Правило суммы. Если некоторый объект х можно выбрать n способами, а объект у можно выбрать m способами, причем первые и вторые способы не пересекаются, то любой из указанных объектов (х или у), можно выбрать n+m способами.

Это правило распространяется на любое конечное число объектов.

Пример 2. В студенческой группе 14 девушек и 6 юношей. Сколькими способами можно выбрать, для выполнения различных заданий, двух студентов одного пола?

По правилу умножения двух девушек можно выбрать 14×13 = 182 способами, а двух юношей - 6×5 = 30 способами. Следует выбрать двух студентов одного пола: двух студенток или двух юношей. Согласно правилу сложения таких способов выбора будет 182 + 30 = 212.

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

Существуют две схемы выбора m элементов (0 < m £ n) из исходного множества: без возвращения (без повторений) и с возвращением (с повторением). В первом случае выбранные элементы не возвращаются обратно; можно отобрать сразу все m элементов или последовательно отбирать их по одному. Во второй схеме выбор осуществляется поэлементно с обязательным возвращением отобранного элемента на каждом шаге.

Схема выбора без возвращений

Пусть дано множество, состоящее из n различных элементов.

Размещением из n элементов по m элементов (0 < m £ n) называется любое упорядоченное подмножество данного множества, содержащее m элементов.

Из определения вытекает, что размещения — это выборки (комбинации), состоящие из m элементов, которые отличаются друг от друга либо составом элементов, либо порядком их расположения.

Число размещений из n элементов по m элементов обозначается символом («А из эн по эм») и вычисляется по формуле

(1)

или

, где (2)

Для составления размещения надо выбрать m элементов из множества с n элементами и упорядочить их, т. е. заполнить m мест элементами множества. Первый элемент можно выбрать n способами, т. е. на первое место можно поместить любой из n элементов. После этого второй элемент можно выбрать из оставшихся n-1 элементов n-1 способами. Для выбора третьего элемента имеется n-2 способа, четвертого — n-3 способа, и, наконец, для последнего m-го элемента - (n-(m-1)) способов. Таким образом, по правилу умножения, существует n(n-1)(n-2)...(n-(m-1)) способов выбора m элементов из данных n элементов, т. е. .

Пример 3. Составить различные размещения по 2 из элементов множества D = {а, b, с}; подсчитать их число.

Из трех элементов можно образовать следующие размещения по два элемента: (а, b), (b, а), (а, с), (с, а), (b, с), (с, b). Согласно формуле (1) их число: = 3×2 = 6.

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

Из определения вытекает, что перестановки — это выборки (комбинации), состоящие из n элементов и отличающиеся друг от друга только порядком следования элементов. Число перестановок из n элементов обозначается символом Р_n («пэ из эн») и вычисляется по формуле

Р_n = n!. (3)

Формула (3) следует из определения перестановки:

Пример 4. Составить различные перестановки из элементов множества Е={2, 7, 8}; подсчитать их число.

Из элементов данного множества можно составить следующие перестановки: (2,7,8); (2,8,7); (7,2,8); (7,8,2); (8,2,7); (8,7,2). По формуле (3) имеем: Р₃ = 3! = 1×2×3 = 6.

Пример 5. Сколькими способами можно расставить на полке 5 различных книг?

Искомое число способов равно числу перестановок из 5 элементов (книг), т. е.

Р₅=5!=1×2×3×4×5 = 120.

Сочетанием из n элементов по m (0 < m £ n) элементов называется любое подмножество, которое содержит m элементов данного множества.

Из определения вытекает, что сочетания — это выборки (комбинации), каждая из которых состоит из m элементов, взятых из данных n элементов, и которые отличаются друг от друга хотя бы одним элементом, т. е. отличаются только составом элементов.

Число сочетаний из n элементов по m элементов обозначается символом («цэ из эн по эм») и вычисляется по формуле

(4)

или

(5)

Число размещений из n элементов по m элементов можно найти следующим образом: выбрать m элементов из множества, содержащего n элементов (это можно сделать способами); затем в каждом из полученных сочетаний (подмножеств) сделать все перестановки для упорядочения подмножеств (это можно сделать Р_m способами). Следовательно, согласно правилу умножения, можно записать:

Отсюда или

Можно показать, что имеют место формулы:

Пример 5. Составить различные сочетания по 2 из элементов множества D - {а, b, с}; подсчитать их число.

Из трех элементов можно образовать следующие сочетания по два элемента: (а, b); (a,с); (b,с). Их число: (формула (4)).

Пример 6. Сколькими способами можно выбрать 3 цветка из вазы, в которой стоят 10 красных и 4 розовых гвоздики? А если выбрать 1 красную гвоздику и 2 розовых?

Так как порядок выбора цветов не имеет значения, то выбрать 3 цветка из вазы, в которой стоят 14 гвоздик, можно способами. По формуле (4) находим: . Далее: красную гвоздику можно выбрать способами. Выбрать две розовые гвоздики из имеющихся четырех можно способами. Поэтому букет из одной красной и двух розовых гвоздик можно составить, по правилу умножения, способами.

Схема выбора с возвращением

Если при выборке m элементов из n элементы возвращаются обратно и упорядочиваются, то говорят, что это размещения с повторениями.

Размещения с повторениями могут отличаться друг от друга элементами, их порядком и количеством повторений элементов. Число всех размещений из n элементов по m с повторениями обозначается символом и вычисляется по формуле (6)

Пример 7. Из 3 элементов а, b, с составить все размещения по два элемента с повторениями.

По формуле (1.12) число размещений по два с повторениями равно . Это: (а,а), (а,b), (а, с), (b,b), (b,а), (b,с), (с,с), (с,а), (с, b)

Пример 8. Сколько пятизначных чисел можно составить, используя цифры:

а) 2. 5, 7, 8;

б) 0, 1, 9?

а) Все пятизначные числа, составленные из цифр 2. 5, 7, 8, отличаются друг от друга либо порядком их следования (например, 25558 и 52855), либо самими цифрами (например, 52788 и 78888). Следовательно, они являются размещениями из 4 элементов по 5 с повторениями, т.е. . Таким образом, искомое число пятизначных чисел равно . Этот же результат можно получить, используя правило умножения: первую цифру слева в пятизначном числе можно выбрать четырьмя способами, вторую — тоже четырьмя способами, третью - четырьмя, четвертую — четырьмя, пятую — четырьмя. Всего получается 4×4×4×4×4=1024 пятизначных чисел.

б) Если пятизначные числа состоят из цифр 0, 1, 9, то первую цифру слева можно выбрать двумя способами (0 не может занимать первую позицию), каждую из оставшихся четырех цифр можно выбрать тремя способами. Согласно правилу умножения, таких чисел будет 2×3×3×3×3=162. (Иначе: .)

Если при выборке m элементов из n элементы возвращаются обратно без последующего упорядочивания, то говорят, что это сочетания с повторениями.

Число всех сочетаний из n элементов по m с повторениями обозначается символом и вычисляется по формуле

(7)

Пример 9. Из трех элементов а, b, с составить все сочетания по два элемента с повторениями.

По формуле (7) число сочетаний по два с повторениями равно . Составляем эти сочетания с повторениями: (а, а), (a. b), (а, с), (b,b), (b, с), (с, с).

Пример 10. Сколькими способами можно составить букет из 5 цветов, если в наличии есть цветы трех сортов?

Рассматриваемое множество состоит из трех различных элементов, а выборки имеют объем, равный 5. Поскольку порядок расположения цветов в букете не играет роли, то искомое число букетов равно числу сочетаний с повторениями из трех элементов по 5 в каждом. По формуле (7) имеем

Пусть в множестве с n элементами есть k различных элементов, при этом 1-й элемент повторяется n₁ раз, 2-й элемент — n₂ раз..., к-й элемент — n_k раз, причем n₁+n₂+…+n_k=n.

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

Число перестановок с повторениями из n элементов обозначается символом

Р_n(n₁, n₂, …,n_k) и вычисляется по формуле

(8)

Пример 11. Сколько различных пятизначных чисел можно составить из цифр 3, 3, 5, 5, 8?

Применим формулу (8). Здесь n=5, n₁=2, n₂=2, n₃= 1. Число различных пятизначных чисел, содержащих цифры 3, 5 и 8, равно

Дата добавления: 2014-01-20