Правило произведения

Основные понятия комбинаторики: перестановки, сочетания, размещения

При решении многих практических задач часто приходится имеющиеся предметы (элементы) соединять в разные наборы (комбинации). Например - парфюмерные наборы, конфеты, инструменты, спортивные команды. Задачи которые рассматривают такие соединения и находится число различных соединений, называют комбинаторными.

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

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

Общие правила комбинаторики

Правило суммы

Если некоторый объект А можно выбрать 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) способами (причем, каждый следующий объект выбирается независимо от выбора предыдущего объекта), то объекты А₁, А₂, … , А_nможно выбрать k = k₁ · k₂ ·…· k_n способами.

Например, сколькими способами можно составить трехзначное число, делящееся на 5? Число имеет три позиции, каждую из которых мы назовем событием:

· событие А₁ –число сотен, их можно выбрать k₁ =9 (все цифры, кроме 0) способами;

· событие А₂ – число десятков, их можно выбрать k₂ = 10 (все цифры, включая 0) способами;

· событие А₃ – число единиц, которым удовлетворяет только две цифры: 0 и 5, следовательно, k₃ = 2. Таким образом, всего получаем n = k₁ · k₂ · k₃ = 9 · 10 · 2 = 180 чисел.

Типы соединений

Одним из важнейших понятий современной математики является понятие множества. Говорят о множестве учащихся в группе, о множестве букв в алфавите, о множестве изделий в упаковке и т.д.

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

Множество будем записывать, располагая его элементы в фигурных скобка {a, b, c, … , e, f}.

Во множестве порядок элементов роли не играет, так {a, b} = {b, a}.

Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается символом ø.

Множества элементов называются соединениями.

Различают три типа соединений:

· перестановки из n элементов;

· размещения из n элементов по m;

· сочетания из n элементов по m (m < n).