Элементы комбинаторики и теории вероятностей

Лекция 2 Элементы комбинаторики и теории вероятностей 2.1 Комбинаторика. Разделы комбинаторики Комбинаторика – раздел математики, в котором изучаются задачи выбора элементов из заданного множества и расположения их в группы по заданным правилам. Наиболее часто используется аппарат перечислительной комбинаторики - для решения задач о подсчете числа комбинаций (выборок), получаемых из элементов заданного конечного множества. В каждой задаче такого рода необходимо ответить на вопрос сколькими способами возможно осуществить что-либо; подсчитать варианты осуществления некоторого действия. 2.1.1 Базовые правила комбинаторики Все задачи комбинаторики1 могут быть решены с помощью трех основных правил, рассмотренных ниже, при этом из указанных правил выводятся все основные формулы комбинаторики. Правило суммы: Если некоторый объект A может быть выбран из совокупности объектов m способами, а другой объект B – n способами, то выбрать либо A, либо B возможно m + n способами. 1 Здесь и далее имеются ввиду задачи перечислительной комбинаторики, если не указано обратное. 20 Правило произведения: Если некоторый объект A может быть выбран из совокупности объектов m способами и после каждого такого выбора объект B можно выбрать n способами, то пара объектов (A, B) в указанном порядке может быть выбрана m · n способами. Пример 1. Повседневный наряд девушки состоит из блузки, юбки и туфель, а вечерний - платья, шали и туфли. В гардеробе лежит 4 блузки, 5 юбок и 3 туфель; 2 платья, 1 шаль. Внимание вопрос: сколько видов повседневных нарядов может одеть девушка? Сколько всего нарядов у девушки, если вечернее платье можно одеть без шали? Решение. По принципу умножения получаем, что видов повседневных нарядов у девушки 4 · 5 · 6 = 60. Аналогично, видов вечерних нарядов 2 · 2 · 3 = 12 (вечернее платье можно одеть без шали). Таким образом, по правилу сложения получаем, что общее число нарядов у девушки равно 60 + 12 = 72. Формула включения и исключения: Пусть имеется K частично пересекающихся множеств объектов; k-е множество объединяет объекты, обладающие определенным свойством ak и имеет размерность Nk . Для решения задачи определения общего количества объектов Nany , обладающих хотя бы одним из свойств a1 . . . an используется формула включения и исключения, определяющая де-факто мощность объединения указанных множеств. Nany = N1 + N2 + . . . + NK − Na1 +a2 − . . . − Na1 +an − . . . − Nan−1 +an + + Na1 +a2 +a3 + . . . + Nan−2 +an−1 +an + . . . + (−1)n−1 Na1 +a2 +...+an . (2.1) Пример 2. Студенты факультета ВМК К(П)ФУ им. Ульянова-Ленина делятся на знающих языки программирования С++ (30 человек из выпуска), Pascal (20 человек), одновременно два языка (также 20 человек). Какое количество выпускников ВМК знает в достаточной мере хотя бы один язык программирования из вышеперечисленных? Решение. Согласно формуле включения и исключения указанное количество выпускников N = 30 + 20 − 20 = 30. 21 2.1.2 Основные формулы комбинаторики Из рассмотренных правил выводятся основные формулы перечислительной комбинаторики. Размещения Итак, рассмотрим некоторое множество X, состоящее из n элементов X = x1 , x2 , . . . , xn . Будем выбирать из этого множества различные упорядоченные подмножества Y из k элементов. В этом случае размещением из n элементов множества X по k элементам называется любой упорядоченный набор (xi1 , xi2 , . . . , xik ) элементов множества X. При этом, если выбор элементов множества Y из X происходит с возвращением (т.е. каждый элемент множества X может быть выбран несколько раз), то число размещений обозначается как Akn (количество размещений с повторениями) и определяется по следующей формуле: Akn = nk . (2.2) Если же выбор делается без возвращения, т.е. каждый элемент множества X можно выбрать только один раз, то количество размещений из n по k обозначается Akn (количество размещений без повторений) и определяется равенством: n! . (2.3) Akn = (n − k)! Пример 3. Даны шесть цифр: 1,2,3,4,5,6. Определить: сколько трехзначных чисел возможно из них составить? Решение. Если цифры могут повторяться, то количество трехзначных чисел будет равно A36 = 63 = 216. Если не могут - то A36 = 6! 3! = 6 · 5 · 4 = 120. Перестановки Частный случай размещения при n = k называется перестановкой из n Элементов. Число всех перестановок из n элементов равно: Ann = Pn = n! 22 (2.4) Пример 4. 30 книг стоят на книжной полке, из них 27 различных авторов и три книги от одного автора. Сколькими способами возможно расставить эти книги на полке так, чтобы книги одного автора стояли рядом? Решение. Будем считать три книги одного автора за одну книгу; в этом случае число перестановок будет определяться как P28 . При этом три книги возможно переставить между собой P3 способами. Таким образом, по правилу произведения получаем искомое число способов, равное P28 · P3 = 28! · 3!. Существует также понятие так называемых перестановок с повторениями. Такими перестановками из n1 элементов первого типа, n2 элементов второго типа, . . . , nk элементов k-го типа называются всевозможные комбинации из этих элементов, каждая из которых содержит ni элементов i-го вида. Комбинации отличаются друг от друга лишь порядком элементов. Число перестановок с повторениями обозначается как P (n1 , n2 , . . . , nk ) и определяется по формуле: P (n1 , n2 , . . . , nk ) = n! . n1 ! · n2 ! · . . . · nk ! (2.5) Пример 5. Сколькими способами можно поставить в ряд 3 красных, 4 синих и 5 зеленых кубиков? Решение. По формуле перестановок с повторениями получаем: 12! P (3, 4, 5) = 3!·4!·5! = 27720. Сочетания Пусть теперь из множества X выбирается неупорядоченное подмножество Y (порядок элементов в котором не важен). Сочетаниями из n элементов по k называются подмножества из k элементов, отличающиеся друг от друга хотя бы одним элементом. Общее число всех сочетаний обозначается Cnk и равно: Cnk Akn n! n(n − 1) . . . (n − k + 1) = = = . k! (n − k)!k! k! 23 (2.6) Для сочетаний справедливы следующие равенства: Cn0 = 1, Cnn = 1, Cnk = Cnn−k . Пример 6. Сколькими способами можно выбрать три краски из имеющихся пяти? Решение. В поставленной задаче порядок выбора красок не важен. Таким образом, количество способов определяется, как количество сочета5! ний C53 = 2!3! = 10. В некоторых случаях необходимо вычислить так называемые сочетания с повторениями. Сочетания с повторениями из n элементов по k - это всевозможные комбинации, составленные из элементов n видов по k элементов в каждой. Комбинации считаются различными, если они отличаются составом, но не порядком входящих в них элементов. В комбинацию могут входить элементы одного вида. Количество сочетаний с повторениями обозначается Cnk и равно: k Cnk = Cn+k−1 = (n + k − 1)! . (n − 1)!k! (2.7) Пример 7. В кондитерском магазине продаются 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных? Решение. Согласно формуле сочетаний с повторениями указанное коли10! чество равно C47 = 3!7! = 8·9·10 = 120. 6 2.1.3 Теоремы Рамсея и Ван-дер-Вардена В заключение раздела, посвященного основам комбинаторики, невозможно не упомянуть о замечательной комбинаторной теореме Рамсея, изучающей наличие регулярных структур в случайных конфигурациях элементов. Так, примером утверждения, следующего из теоремы Рамсея может служить следующее: в группе из 6 человек всегда можно найти 24 трех человек, которые либо попарно знакомы друг с другом, либо попарно незнакомы. Теорема Рамсея сформулирована в терминах теории графов, но имеет и аналогичную формулировку для натуральных чисел. Указанная формулировка и называется теоремой Ван-дер-Вардена, и определяется следующим образом: Теорема Ван-дер-Вардена Для всякого набора чисел a1 , a2 , ldots, an существует такое число W , что, как бы мы не покрасили первые W натуральных чисел в n цветов, найдется либо арифметическая прогрессия 1-го цвета длины a1 , либо арифметическая прогрессия 2-го цвета длины a2 ,. . . , либо арифметическая прогрессия n-го цвета длины an . Указанные теоремы имеют два характерных свойства: • Во-первых, они не конструктивны. Доказывается, что некоторая структура существует, но не предлагается никакого способа ее построения, кроме прямого перебора. • Во-вторых, чтобы искомые структуры существовали, требуется, чтобы объекты их содержащие, состояли из очень большого количества элементов - зависимость числа элементов объекта от размеры структуры как минимум экспоненциальна. Указанные свойства, с точки зрения автора лекций, носят достаточно философский характер и во многом отражает несколько романтичный дух теории информации в целом. 2.2 Элементы теории вероятности 2.2.1 Базовые понятия теории вероятности Теория вероятности - область математического знания, изучающая закономерности, возникающие при рассмотрении массовых однотипных случайных событий. Центральным понятием теории вероятности является понятие случайного события. Случайным событием называется событие, которое при осуществлении некоторых условий может произойти или не произойти. Пример случайного события - попадание в некоторый объект или промах при стрельбе по объекту. 25 Достоверным называется событие, если в результате испытания оно обязательно происходит. Невозможное - такое событие, которое не может произойти в результате данного испытания. Несовместными называются такие случайные события, для которых одновременное появление никаких двух из них в рамках данного испытания невозможно. Независимыми являются такие события, появление одного которых не меняют вероятности появления других. Зависимыми называются такие события, вероятность которых меняется в зависимости от появления других событий, входящих в эту группу. Полная группа - множество событий, из которых в результате данного испытания обязательно появится произвольное, но при этом только одно событие. Исходом называются события, входящие в полную группу равновозможных несовместных случайных событий. Исход называется благоприятствующим появлению события A, если появление этого исхода влечет за собой появление события A. Пример 8. В урне находится 8 пронумерованных (от 1 до 8) шаров. Шары с цифрами 1,2 и 3 – красные; остальные – черные. Каким является событие появление шара с номером 4? Решение. Появление шара с цифрой 4 есть событие (исход), благоприятствующее появлению черного шара. По результату рассмотрения элементарных терминов теории вероятности, дадим далее классическое определение вероятности: Вероятностью события A называют отношение числа m благоприятствующих этому событию исходов к общему числу n всех равновозможных несовместных элементарных исходов, образующих полную группу: m P (A) = . (2.8) n Вероятность в классическом определении обладает следующими элементарными свойствами: • textbfСвойство 1: Вероятность достоверного события равна 1. 26 • textbfСвойство 2: Вероятность невозможного события равна 0. • textbfСвойство 3: Вероятность случайного события A удовлетворяет двойному неравенству 0 ≤ P (A) ≤ 1. 2.2.2 Сложение и умножение вероятностей Событие A называется частным случаем события B, если при наступлении A наступает и B. То, что A является частным случаем B, записывается A ⊂ B. События A и B называются равными, если каждое из них является частным случаем другого. Равенство событий A и B записывается как A = B. Суммой событий A и B называется событие A + B, наступающее тогда и только тогда, когда наступает хотя бы одно из событий A или B. Теорема о сложении несовместных событий: Вероятность появления одного из двух (одного из группы) несовместных событий равна сумме вероятностей этих событий: P (A + B) = P (A) + P (B) ! n n X X P Ai = P (Ai ). i=1 (2.9) i=1 Если случайные события A1 , A2 , . . . , An образуют полную группу несовместных событий, то имеет место равенство: P (A1 ) + P (A2 ) + . . . + P (An ) = 1. (2.10) Теорема о сложении совместных событий: Вероятность суммы совместных событий вычисляется по формуле: P (A + B) = P (A) + P (B) − P (AB). (2.11) Теорема о умножении вероятностей независимых событий: Вероятность произведения независимых событий A и B равна: P (AB) = P (A) · P (B). Из данных теорем вытекает следующая: 27 (2.12) Вероятность появления хотя бы одного из событий A1 , A2 , . . . An , независимых в совокупности, равна разности между единицей и произведением вероятностей противоположных событий (P (A) = 1 − P (A) – событие, противоположной событию A): P (A) = 1 − P (A1 ) · P (A2 ) · . . . P (An ). (2.13) Если события A1 , A2 , . . . An имеют одинаковую вероятность реализации p (соответственно, противоположные события - вероятность реализации 1 − p = q, то формула 2.13 приобретает следующий вид: (2.14) P (A) = 1 − (1 − p)n = 1 − q n . 2.2.3 Условная вероятность, полная вероятность события Рассмотрим далее понятия условной вероятности и полной вероятности определенного события. Итак, случайное событие - это такое событие, которое при осуществлении совокупности условий эксперимента может произойти или не произойти. Если при вычислении вероятности события никаких других условий, кроме условий эксперимента, не налагается, то такая вероятность называется безусловной; если же налагаются и другие дополнительные условия, то вероятность события называют условной. Так, что вычисляют вероятность возникновения события B при дополнительном условии, что произошло событие A. Условной вероятностью PA (B) = P (B|A) называют вероятность события B, вычисленную в предположении, что событие A уже наступило. Вероятность совместного появления двух зависимых событий равна произведению вероятности одного из них на условную вероятность второго, вычисленную при условии, что первое событие произошло. Таким образом: P (AB) = P (B)P (A|B) = P (A)P (B|A); P (A|B) = P (AB) . P (B) (2.15) Определим далее так называемую полную вероятность события. Итак, если событие A может произойти только при выполнении одного из событий B1 , B2 , . . . , Bn , образующих полную группу несовместных событий, 28 то вероятность события A вычисляется по так называемой формуле полной вероятности: P (A) = P (B1 )P (A|B1 ) + P (B2 )P (A|B2 ) + . . . + P (Bn )P (A|Bn ). (2.16) 2.2.4 Формула Байеса Закончим лекцию на рассмотрении так называемой формулы Байеявляющейся основополагающей в теории вероятностей, математической статистике и множества областей обработки информации. Вновь рассмотрим полную группу несовместных событий B1 , B2 , . . . , Bn , вероятности появления которых P (B1 ), P (B2 ), . . . , P (Bn ). Событие A может произойти только вместе с каким-либо из событий B1 , B2 , . . . , Bn , которые будем называть гипотезами. Тогда по формуле полной вероятности получаем: са2 , P (A) = P (B1 )P (A|B1 ) + P (B2 )P (A|B2 ) + . . . + P (Bn )P (A|Bn ). Если событие A произошло, то это может изменить вероятности гипотез P (B1 ), P (B2 ), . . . , P (Bn ). Далее, по теореме умножения вероятностей: P (AB1 ) = P (B1 )P (A|B1 ) = P (A)P (B|A), откуда P (B1 )P (A|B1 ) . P (A) Формулой Байеса называется аналогичное выражение, обобщенное для всех гипотез: P (Bi )P (A|Bi ) P (Bi |A) = , i = 1, . . . , n. (2.17) P (A) В формуле Байеса вероятности гипотез P (Bi |A) называются апостериорными вероятностями 3 , тогда как P (B) - априорными вероятностями 4 . P (B1 |A) = В общем случае Байесовская теория представляет собой метод адаптации существующих вероятностей к вновь полученным экспериментальным данным. 2В честь Томаса Байеса (1702–1761), доказавшего частный случай приведенной ниже теоремы. В реальности, более общий случай теоремы Байеса был доказан Лапласом, не считавшим, однако, ее важной для развития теории вероятности. 3 a-posteriori (лат. - после опыта). 4 a-priori (лат. - до опыта). 29 На сегодняшний день Байесовы методы и Байесов анализ широко применяется в теории информации, при построении интеллектуальных семантических фильтров (например спам–фильтров), в алгоритмах анализа массивов данных, в предсказании состояний различных динамических процессов, а также во множестве алгоритмов цифрового приема и обработки сигналов. 30