Элементы комбинаторики
 Скачать 1.52 Mb.
|
|
Задачи называются комбинаторными, если в них определяется число способов осуществления того или иного действия ЭЛЕМЕНТЫ КОМБИНАТОРИКИ Наука, изучающая способы решения комбинаторных задач, называется комбинаторикой. Комбинаторика - это раздел математики, в котором исследуются и решаются задачи выбора элементов из исходного множества и расположения их в некоторой комбинации, составленной по заданным правилам ИСТОРИЯ ВОЗНИКНОВЕНИЯ Слово «комбинаторика» происходит от латинского слова «combinare», которое означает «соединять, сочетать» Принцип умноженияТребуется совершить путешествие по маршруту Оренбург- -Самара-Казань. Известно, что из Оренбурга до Самары можно добраться поездом, самолетом или на автомобиле; из Самары до Казани: самолетом, поездом, пароходом или на автомобиле. Сколькими способами можно осуществить такое путешествие? Задача: Решение 12 способов Оренбург Самара Казань ПОЕЗД САМОЛЕТ АВТОМОБИЛЬ ПОЕЗД САМОЛЕТ АВТОМОБИЛЬ ТЕПЛОХОД Из Оренбурга до Самары можно добраться 3 способами, для каждого из них из Самары до Казани – 4 способами. Таким образом, такое путешествие можно осуществить 12 способами. Принцип умноженияЕсли требуется выполнить одно за другим k действий, причем первое действие можно выполнить способами, второе – способами,…, k-ое – способами, то все k действий вместе можно выполнить способами Теорема ПЕРЕСТАНОВКИРазличные упорядоченные множества одного и того же множества из n элементов называются перестановками этого множества Множество из n элементов называется упорядоченным, если каждому элементу этого множества поставлено в соответствие натуральное число (номер элемента) от 1 до n. В противном случае, множество называется неупорядоченным Определение Для одного и того же множества из n элементов можно получить различные упорядоченные множества Определение - число перестановок из n элементов …….. Факториал ПЕРЕСТАНОВКИТеорема Число перестановок множества из n элементов равно Доказательство: Определим сколькими способами n предметов можно расставить по n местам. 1-ое место можно заполнить n способами; 2-ое место можно заполнить (n-1) способами; …….. (n-1)-ое место можно заполнить 2 способами; n-ое место можно заполнить 1 способом. Таким образом, общее число способов осуществления данного действия равно Следствие n различных предметов по n местам можно расставить n! способами РАЗМЕЩЕНИЯУпорядоченное m-элементное подмножество множества из n элементов называется размещением из n элементов по m Как из множества, состоящего из n элементов, выбрать упорядоченное подмножество из m элементов? Например, как рассадить за праздничный стол 12 гостей, если всего 15 мест? Задача:_Определение_-_число_размещений_из_n_элементов_по_mm_различных_предметов_по_n_местам_можно_расставить_способамиРешение'>Задача: Определение - число размещений из n элементов по m m различных предметов по n местам можно расставить способами Решение Следствие далее представленной теоремы Число приглашенных гостей можно рассадить способами РАЗМЕЩЕНИЯТеорема Число размещений множества из n элементов по m равно Доказательство: 1-ый элемент можно выбрать n способами; 2-ой элемент можно выбрать (n-1) способами; ………………. m-ый элемент можно выбрать (n-(m-1)) способами. Таким образом, общее число способов выбрать упорядоченное подмножество равно n(n-1)…(n-(m-1)). СОЧЕТАНИЯПроизвольное m-элементное подмножество множества из n элементов называется сочетанием из n элементов по m Как из множества, состоящего из n элементов, выбрать неупорядоченное подмножество из m элементов? Например, в студенческой группе из 25 человек выбрать 3 для выполнения какой-нибудь общественной работы? Порядок выдвижения кандидатур значения не имеет. Задача: Определение - число сочетаний из n элементов по m Решение Количество способов выбрать 3 человека из 25 для выполнения поручения m одинаковых предметов по n местам можно расставить способами Следствие далее представленной теоремы СОЧЕТАНИЯТеорема Число сочетаний множества из n элементов по m равно Доказательство: Известно, что число упорядоченных m-элементных подмножеств множества из m элементов равно Среди них встречаются множества, состоящие из одинаковых элементов и отличающиеся только порядком расположения этих элементов. Разобьем все упорядоченные подмножества на группы множеств, состоящих из одинаковых элементов. Число множеств внутри каждой группы будет m!. Следовательно, групп (а значит и неупорядоченных подмножеств) будет РАЗБИЕНИЯПредставление (разложение) множества из n элементов в виде суммы (объединения) r попарно непересекающихся неупорядоченных подмножеств, состоящих из элементов соответственно, называется разбиением множества из n элементов на r подмножеств по элементов соответственно Разбиение множества из n элементов на r попарно непересекающихся подмножеств. Например, студенческую группу из 25 человек нужно разбить на 3 подгруппы по 5, 8, 12 человек соответственно для выполнения хозяйственных работ на субботнике. Задача: Определение - число разбиений из n элементов по Решение Группу из 25 человек на подгруппы из 5, 8, 12 человек можно разбить способами РАЗБИЕНИЯ1-ое множество, состоящее из m1 элементов, можно выбрать способами; 2-ое множество - способами; ….. (r-1)-ое множество - способами; r-ое множество - 1 способом. Общее число способов будет равно Теорема Число разбиений множества из n элементов на r попарно непересекающихся подмножеств по элементов равно Доказательство: Случайным событием (просто событием, исходом) называется любой факт, который в результате испытания может произойти или непроизойти ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ВЕРОЯТНОСТЕЙ Под испытанием (опытом, экспериментом) понимается выполнение определенного комплекса условий, в которых наблюдается то или иное явление, фиксируется тот или иной результат
1) бросание игрального кубика; 2) cдача экзамена; 3) выстрел из винтовки; 4) химический эксперимент и др. Случайные события обозначают заглавными буквами латинского алфавита: A, B, C, … ПРИМЕРЫ ПРИМЕРЫ Элементарные исходы – это события, обладающие следующими cвойствами;
одно из них; 2) для любого события (возможного в результате опыта), по наступившему элементарному событию, можно определить произошло оно или нет Среди всех возможных событий , которые, по воле случая, в результате опыта происходят или не происходят выделяют элементарные исходы (элементарные события) Элементарные события обозначают ω или ωi Совокупность всех элементарных событий называют пространством элементарных событий Пространство элементарных событий обозначают Любое подмножество множества Ω называют событием Событие А происходит тогда и только тогда, когда происходит одно из элементарных событий, входящих в А ТИПЫ СОБЫТИЙПРИМЕРЭлементарными событиями являются: - выпадение цифры «0»; - выпадение цифры «1»; - выпадение цифры «2»; - выпадение цифры «4»; - выпадение цифры «7». Рассмотрим кубик, на гранях которого написаны цифры 1, 7, 0, 1, 2, 4. Опыт состоит в том, что бросаем кубик и смотрим, какая цифра появится на верхней грани. Задача: Пространство элементарных исходов: - событие, состоящее в том, что выпадет четная цифра; - событие, состоящее в том, что выпадет нечетная цифра; - событие, состоящее в том, что появится простое число. ПРИМЕРПредположим, в результате опыта появилась цифра 7. В этом случае произошли события B и C, а событие А не произошло События называются совместными, если появление одного не исключает появление другого. В противном случае события называются несовместными А и В – несовместные события; В и С – совместные события Невозможным для данного опыта является событие, состоящее в том, что появится цифра 5. ОПЕРАЦИИ НАД СОБЫТИЯМИСуммой событий А и B называется событие Определение ОБОЗНАЧЕНИЕ С=А+B или Событие А+В происходит тогда и только тогда, когда происходит или событие А или событие В или и А и В одновременно ОПЕРАЦИИ НАД СОБЫТИЯМИПроизведением событий А и B называется событие Определение ОБОЗНАЧЕНИЕ С=АB или Событие АВ происходит тогда и только тогда, когда одновременно происходят события А и В. Если события А и В несовместны, то . ОПЕРАЦИИ НАД СОБЫТИЯМИРазностью событий А и B называется событие Определение ОБОЗНАЧЕНИЕ С=А-B или Событие А-В происходит тогда и только тогда, когда событие А происходит, а В не происходит ОПЕРАЦИИ НАД СОБЫТИЯМИСобытие называется противоположным событием к А Определение ОБОЗНАЧЕНИЕ ОПЕРАЦИИ НАД СОБЫТИЯМИОПЕРЕДЕЛЕНИЕ ВЕРОЯТНОСТИВозникновение теории вероятностей как науки относится к середине 17 века. Первое определение вероятности было дано Бернулли Вероятность – степень уверенности в том, что событие произойдет и отношение к достоверности как части к целому Классическое определение вероятности сформулировано в курсе лекций Лапласа ОПРЕДЕЛЕНИЕ ВЕРОЯТНОСТИ КЛАССИЧЕСКОЕ ГЕОМЕТРИЧЕСКОЕ СТАТИСТИЧЕСКОЕ АКСИОМАТИЧЕСКОЕ ОПЕРЕДЕЛЕНИЕ ВЕРОЯТНОСТИВероятностью события А называется число, равное отношению числа элементарных исходов, благоприятствующих появлению события А к общему числу исходов Определение (классическое определение вероятности) Пусть пространство элементарных событий Ω состоит из конечного числа равновозможных элементарных исходов . Произвольное событие А можно представить , . Событие А соответствует k элементарным исходам. Невозможному событию не соответствует ни одного исхода Каждому элементарному событию соответствует только один элементарный исход Событию Ω соответствует n элементарных исходов ЗАМЕЧАНИЕ Классическое определение вероятности может применяться лишь в тех случаях, когда:
конечного числа элементарных исходов; 2) элементарные исходы равновероятны. ПРИМЕРЭлементарными событиями являются: - выпадение цифры «0»; - выпадение цифры «1»; - выпадение цифры «2»; - выпадение цифры «4»; - выпадение цифры «7». Рассмотрим кубик, на гранях которого написаны цифры 1, 7, 0, 1, 2, 4. Опыт состоит в том, что бросаем кубик и смотрим, какая цифра появится на верхней грани. Задача: Пространство элементарных исходов: - событие, состоящее в том, что выпадет четная цифра; - событие, состоящее в том, что выпадет нечетная цифра; - событие, состоящее в том, что появится простое число. ПРИМЕР- событие, состоящее в том, что выпадет четная цифра; - событие, состоящее в том, что выпадет нечетная цифра; - событие, состоящее в том, что появится простое число. В данном опыте события не равновероятны, так как появлению цифры 1 соответствует 2 грани, появлению остальных цифр по одной грани. К данной модели можно применить классическое определение вероятности, если на гранях с цифрами 1 сделать дополнительные пометки, например 1’ и 1” и вместо элементарного события ω1 рассмотреть элементарные события ω1’ и ω1”. В этом случае пространство элементарных событий будет иметь вид ПРИМЕРОПЕРЕДЕЛЕНИЕ ВЕРОЯТНОСТИГеометрическая интерпретация вероятности была предложена английским математиком Венном Геометрическое определение вероятности применяется в тех случаях, когда имеется бесконечное число равновероятных исходов. ОПЕРЕДЕЛЕНИЕ ВЕРОЯТНОСТИВероятностью события А, состоящего в том, что при бросании точки на отрезок [A, B] она попадет на отрезок [С, Д] [А, В], называется число, определяемое по формуле Наиболее распространены 3 модели 1 Имеем отрезок [А, В]. Бросаем в него точку. Теоретически точка может попасть в любую точку X отрезка [А, В]. Пространство элементарных событий состоит из бесконечного числа элементарных исходов, следовательно классическое определение вероятности применить нельзя. ОПЕРЕДЕЛЕНИЕ ВЕРОЯТНОСТИВероятностью события А, состоящего в том, что при бросании точки в область G она попадет в замкнутую ограниченную область с гладкой или кусочно гладкой границей , называется число, определяемое по формуле 2 Пусть на плоскости ОХУ задана замкнутая ограниченная область G с гладкой или кусочно-гладкой границей. Каждой такой области можно поставить в соответствие число S(G) – площадь области. Бросаем точку в область G. Элементарное событие – nочка попадеn в точку P области G. Пространство элементарных исходов состоит из бесконечного числа равновероятных исходов ОПЕРЕДЕЛЕНИЕ ВЕРОЯТНОСТИВероятностью события А, состоящего в том, что при бросании точки в область T она попадет в область , называется число, определяемое по формуле 3 Пусть в задано замкнутое ограниченное тело T с гладкой или кусочно-гладкой границей. Ему можно поставить в соответствие число V(T) - объем тела. Все три определения можно свести к одному, если вместо числовых характеристик области использовать термин мера области - mes Вероятностью события А, состоящего в том, что при бросании точки в область D она попадет в область , называется число, определяемое по формуле СВОЙСТВА ГЕОМЕТРИЧЕСКОГО ОПРЕДЕЛЕНИЯ ВЕРОЯТНОСТИМера области, соответствующая элементарному событию, равна нулю . Благоприятной области для невозможного события нет Благоприятной областью для события Ω является вся область D . ПРИМЕРПусть время прихода одного из них –
При этом Встреча произойдет если: Два друга договорились встретиться между 12 и 13 часами дня. Пришедший первым ждет второго в течении 20 минут, после чего уходит. Найти вероятность того, что встреча произойдет, если каждый наудачу выбирает время своего прихода от 12 до 13 часов. Задача: Решение ОПЕРЕДЕЛЕНИЕ ВЕРОЯТНОСТИОпределение (статистическое определение вероятности) Статистическое определение вероятности является следствием обработки результатов различных наблюдений и положило начало науке математическая статистика Проведем серию из N опытов. Как часто появится событие A? (Например, бросаем монету несколько раз. Сколько раз при бросании монеты появится «герб»?) Пусть NА – число появлений события А в серии из N опытов. Частотой (относительной частотой) появления события А в серии из N опытов называется число, равное отношению числа появлений события А в серии из N опытов к общему числу опытов СВОЙСТВА ЧАСТОТЫНапример, если бросили монету 3 раза и каждый раз выпало «решка», то частота появления «герба» в данной серии опытов равна нулю, но событие не является невозможным ОПЕРЕДЕЛЕНИЕ ВЕРОЯТНОСТИОпыты показывают, что при больших N частота νА в различных сериях испытаний оказывается приближенно одинаковыми, то есть существует некоторое значение p(A), называемое вероятностью события А, около которого группируются указанные частоты Так как при проведении экспериментов или сбора информации возможны погрешности, то обычно проводят несколько серий опытов (например k серий), в которых число испытаний равно N1, N2,…,Nk. Опрределяют частоту появления события в каждой серии и под вероятностью понимают число |