МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БАШКОРТОСТАН
Государственное автономное профессиональное образовательное учреждение «Ишимбайский нефтяной колледж»
КУРС ЛЕКЦИИ ПО РАЗДЕЛУ МАТЕМАТИКИ
«КОМБИНАТОРИКА И ЭЛЕМЕНТЫЛОГИКИ»
Составитель: Ишемгулов А.Ф., преподаватель математики
Ишимбай 2015
Представителям самых различных специальностей приходится решать задачи, в которых рассматриваются те или иные комбинации, составленные из букв, цифр и иных объектов. Начальнику цеха надо распределить несколько видов работ между имеющимися станками, заведующему учебной частью школы – составить расписание уроков и т.д.
Область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов, называется комбинаторикой.
Комбинаторика возникла в XVI веке. В жизни привилегированных слоёв тогдашнего общества большое место занимали азартные игры. В карты и кости выигрывались и проигрывались золото и бриллианты, дворцы и имения, породистые кони и дорогие украшения. Понятно, что первоначально комбинаторные задачи касались в основном азартных игр – вопросов, сколькими способами можно выбросить данное число очков, бросая две или три кости, или сколькими способами можно получить двух королей в данной карточной игре. Одним из первых занялся подсчётом числа различных комбинаций при игре в кости итальянский математик Тарталья. Дальнейшее развитие комбинаторики связано с именами Якова Бернулли, Лейбница и Эйлера. За последние годы комбинаторика переживает период бурного развития, связанного с общим повышением интереса к проблемам дискретной математики. Комбинаторные методы используются для решения транспортных задач, в частности задач по составлению расписаний; для составления планов производства и реализации продукции.
Пусть имеется n предметов, отмеченных числами 1, 2, …, n. Из этих предметов выбираем один, записываем число, на нём изображённое, а сам предмет либо возвращаем назад (в этом случае говорят о выборе с возвращением), либо он убирается и больше не может быть выбран (в этом случае говорят о выборе без возвращения). Повторяем эту процедуру k раз.
Запись, полученная в результате всех действий, называется выборкой из n элементов по k.
Запись, полученная по схеме выбора с возвращением, называется выборкой с повторениями, а запись, полученная по схеме выбора без возвращений, называется выборкой без повторений.
Общие правила комбинаторики
Комбинаторные задачи бывают самых разных видов. Но большинство задач решается с помощью двух основных правил – правила суммы и правила произведения.
Правило суммы: если некоторый объект А можно выбрать 
способами, а другой объект В можно выбрать 
способами, то выбор «либо А, либо В» можно осуществить 
способами.
При использовании правила суммы в последней формулировке надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В (или, как мы говорим, чтобы ни одна комбинация не попала сразу в два класса). Если такие совпадения есть, правило суммы утрачивает силу, и мы получим лишь 
способов выбора, где 
- число совпадений.
Пример 1. Из 12 слов мужского рода и 9 слов женского рода надо выбрать одно слово либо мужского, либо женского рода. Сколькими способами можно это сделать?
Р е ш е н и е. По условию задачи 
. По правилу суммы 
(способов).
Правило произведения: если объект А можно выбрать способами и если после каждого такого выбора объект В можно выбрать способами, то выбор пары (А,В) в указанном порядке можно осуществить 
способами.
Пример 2. Из 12 слов мужского рода и 9 слов женского рода надо выбрать по одному слову каждого рода. Сколькими способами это можно сделать?
Р е ш е н и е. По условию задачи .По правилу произведения 
(способами).