Общие правила комбинаторики
Правило суммы
Если некоторый объект А можно выбрать m способами, а объект В - k способами (не такими, как А), то объект либо А, либо В можно выбрать m + k способами.
Пример: В ящике имеется n разноцветных шариков. Произвольным образом вынимаем один шарик. Сколькими способами это можно сделать? Конечно, n способами.
Теперь эти n шариков распределены по двум ящикам: В первом m шариков, во втором k. Произвольно из какого-нибудь ящика вынимаем один шарик. Сколькими разными способами это можно сделать? Из первого ящика шарик можно вытянуть m различными способами, из второго k: различными способами, всего n = m + k способами.
Правило произведения
Если объект А можно выбрать m способами, а после каждого такого выбора другой объект В можно выбрать (независимо от выбора А) k способами, то пары объектов А и В можно выбрать m · k способами.
Задача: В студенческой группе 14 девушек и 6 юношей. Сколькими способами можно выбрать, для выполнения различных заданий, двух студентов одного пола?
По правилу умножения двух девушек можно выбрать 14 ·13 = 182 способами, а двух юношей 6·5 = 30 способами. Следует выбрать двух студентов одного пола: двух студентов или студенток. Согласно правилу сложения таких способов выбора будет 182 + 30 = 212.
Задача: Сколько можно записать двузначных чисел в десятичной системе счисления?
Поскольку число двузначное, то число десятков (m) может принимать одно из девяти значений: 1,2,3,4,5,6,7,8,9. Число единиц (k) может принимать те же значения и может, кроме того быть равным нулю. Отсюда следует, что m = 9, а k = 10. Всего получим двузначных чисел n = m · k = 9·10 =90.
Следствие
Правило произведения справедливо и для любого конечного числа объектов.
Если некоторый объект Аi (i = 1, 2, …, n) можно выбрать К i (i = 1, 2, …, n) способами (причем, каждый следующий объект выбирается независимо от выбора предыдущего объекта), то объекты А 1, А 2, …, А nможно выбрать k = k 1 · k 2 ·…· kn способами.
Например, сколькими способами можно составить трехзначное число, делящееся на 5? Число имеет три позиции, каждую из которых мы назовем событием:
· событие А 1 –число сотен, их можно выбрать k 1 =9 (все цифры, кроме 0) способами;
· событие А 2 – число десятков, их можно выбрать k 2 = 10 (все цифры, включая 0) способами;
· событие А 3 – число единиц, которым удовлетворяет только две цифры: 0 и 5, следовательно, k 3 = 2. Таким образом, всего получаем n = k 1 · k 2 · k 3 = 9 · 10 · 2 = 180 чисел.
Типы соединений
Одним из важнейших понятий современной математики является понятие множества. Говорят о множестве учащихся в группе, о множестве букв в алфавите, о множестве изделий в упаковке и т.д.
Понятие множества относится к первоначальным, простейшим, понятиям и формально через другие более простые понятия не определяется. Оно воспринимается конкретно, посредством знакомства с различными примерами множества. Множество характеризуется объединением некоторых однородных объектов в одно целое. Объекты, образующие множество, называются элементами множества.
Множество будем записывать, располагая его элементы в фигурных скобка { a, b, c, …, e, f }.
Во множестве порядок элементов роли не играет, так { a, b } = { b, a }.
Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается символом ø.
Множества элементов называются соединениями.
Различают три типа соединений:
1. перестановки из n элементов;
2. размещения из n элементов по m;
3. сочетания из n элементов по m (m < n).
Перестановки. Число перестановок
На практике часто возникают задачи, связанные с установлением порядка во множестве. Например, число мест равно количеству людей, на которых мы должны разместить их. Такая ситуация встречается часто – рассадить n человек на n мест, или приписать каждому человеку номер. Первый человек может выбрать любое из n мест, второй человек выбирает из (n - 1) оставшихся мест, третий человек может выбрать из уже (n - 2) мест, …, предпоследний человек выбирает из 2 мест, последний человек получает последнее место. Мы получаем произведение всех целых чисел от n до 1.
В общем виде произведение всех целых чисел от 1 до n включительно обозначают n! = 1·2·3…(n – 2) · (n – 1) · n.
Определение: Установленный в конечном множестве порядок называют перестановкой его элементов.
Перестановки можно образовывать из элементов любого конечного множества. Число перестановок из n элементов обозначают Рn. Возьмем одноэлементное множество { a }. Ясно, что один элемент можно упорядочить единственным образом, следовательно, Р1 = 1.
Перестановки – это такие соединения по n элементам из данных элементов, которые отличаются одно от другого порядком элементов.
Возьмем двух элементное множество { a, b }. В нем можно установить два порядка: { a, b } или { b, a }. Следовательно, число перестановок из двух элементов Р2 = 2.
Три буквы во множестве { a, b, c } можно расположить, по порядку шестью способами: { a, b, c }{ a, c, b }{ b, a, c }{ b, c, a }{ c, b, a }{ c, a, b }.
Следовательно, общее число способов упорядочения трех элементов множества Р3 = 3 · Р2 = 3 · 2 · 1 = 6.
Рn = n · (n - 1) · (n – 2) · … · 2 · 1 = n!
Определение: Пусть n - натуральное число. Через n! (читается "эн факториал") обозначается число, равное произведению всех натуральных чисел 1 от до n: n! = 1 · 2 · 3 ·... · n. В случае, если n = 0, по определению полагается: 0! = 1.
Пример:Найдем значения следующих выражений:
1! = 1
2! = 1 · 2 = 2
3! = 1 · 2 · 3 = 6
Задача1: Чему равно а) Р 5 б) Р 3
Задача 2: Упростите а) 7! · 8 = 8! б) 12! · 13 ·14 = 14! в) κ! · (κ + 1) = (κ + 1)!