Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 255
Текст из файла (страница 255)
и.' (В.2) к! (и — к)! При /с = О эта формула дает 1, т.е. выбрать пустое подмножество можно един- ственным способом (напомним, что О! = 1). 'Н отечественной интературе !с-перестановка называется размещением. — Прим. ред. (Здесь для простоты для записи подмножества (а, Ь) мы использовали краткую запись а6). Для построения сочетания из множества просто выбирается /с различных элементов. Количество сочетаний можно выразить через количество размещений.
Для каждого сочетания имеется к! перестановок его элементов, каждая из которых представляет собой одно из размещений из и элементов по и. Таким образом, количество сочетаний из и элементов по Й равно количеству размещений, деленному на !с1, т.е. с учетом (В.1) количество сочетаний из п элементов по !с равно Приложение В.
Комбинаторика и теория вероятности 1229 Биномиальные коэффициенты Для числа сочетаний из п элементов по 1с используется обозначение ('ь) (в отечественной литературе для этой величины принято обозначение Сь). Из (В.2) следует, что и! к/ й! (и — к)!' Эта формула симметрична относительно !с и п — Й: (') =(.— ) (В.З) Этн числа известны также как бнномнальные коэффициенты, поскольку они участвуют в биноме Ньютона: (В.4) В частном случае х = у = 1 мы получаем ( ) = 2". Оценки биномиальных коэффициентои В некоторых случаях нам может потребоваться оценить величину биномиальных коэффициентов и указать их границы.
Нижняя граница для 1 < lс < п может быть оценена следующим образом: () ( — Ц" ( — й<-Ц ( )( — 1) ( — 1+1) ( ) Используя неравенство И > (/с/е)~, являющееся следствием из формулы Стнрлинга (3.!7), мы можем получить оценку верхней границы биномиальных коэффициентов: п п(и — 1) ° ° ° (и — 1+1) и" лепта ( — ( ~ — ) 1с lс(/с — 1). 1 Г! 1/ ) (В.5) Комбинаторный смысл этой формулы заключается в подсчете количества двоичных строк длины и (число которых равно 2") как суммы количества строк с разным числом единиц (имеется ("„) двоичных строк длины и с !с единицами, т.к.
(",) — количество способов выбрать !с позиций для единиц в строке длины и). Имеется масса различных тождеств, в которых принимают участие биномиальные коэффициенты (с неюторыми из них вы познаюмитесь в упражнениях к данному разделу). Часть ЧП1. Приложения: математические основы 1230 Для всех 0 < lс < п по индукции можно доказать (см.
упражнение В.1-12), что и" < й)п-ь ' (В.б) где для удобства принято, что Оо = 1. Для и = Лп, где 0 < Л < 1, это неравенство можно переписать как и / л г х1" Лп (Лп)хп «1 Л) п)(1 х) ~ Л 1 Л ) где Н (Л) = -Л 18Л - (1 - Л) 18(1 - Л) (В.?) Упражнения В.1-1. Сколько имеется lс-подстрок у и-строки? (Одинаковые подстроки, начинающиеся в разных позициях строки, считаются разными.) Сколько всего подстрок имеется у строки длиной и? В.1-2. Булева функция (Ьоо1еап йщс11оп) с п входами и т выходами — это функция с областью определения (ТК()Е, РА1.БЕ)" и областью значений (ТЮЗЕ, РА(.БЕ)~.
Сколько всего имеется различных функций с п входами и 1 выходом? С и входами и т выходами? В.1-3. Сколькими способами и профессоров могут разместиться на конференции за круглым столом? Варианты, отличающиеся поворотом, считаются одинаковыми. В.1-4. Сколькими способами можно выбрать из множества (1, 2,..., 100) три различных числа так, чтобы их сумма была четной? В.1-5. Докажите тождество для 0 < /с < и.
(В.8) В.1-6. Докажите тождество — для 0 < и < п. называется (двоичной) энтропийной функцией (Ь1пагу еппору йпсбоп). Для удобства принято, что 0 18 0 = О, так что Н (0) = Н (1) = О. Приложение В. Комбинаторика и теория вероятности 1231 В.1-8. Используя результат упражнения В.1-7, составьте таблицу биномиальных коэффициентов (",) для п = О, 1,..., 6 и 0 < lс < п в виде равнобедренного треугольника (в первой строке — (~~), во второй — (') и (',) и т.д.).
Такая таблица биномиальных коэффициентов называется треугольникам Паскаля. В.1-9. Докажите, что В.1-10. Покажите, что для любого п > 0 и 0 < lс < п максимальное значение 1ь) достигается при )с = 1п/2) или lс = ~п/21. Докажите, что для любых и, )с, 7' > 0 и 7'+й < и выполняется неравенство * В.1-11. (В.9) Приведите как алгебраическое доказательство данного неравенства, так и доказательство, основанное на рассуждениях о выборе з + й элементов из п. Когда данное неравенство превращается в равенство? Докажите неравенство (В.б) по индукции для )с < и/2, а затем воспользуйтесь уравнением (В.З) для распространения результата на все )с < и.
Воспользуйтесь приближением Стирлинга для доказательства того, что * В.1-12. * В.1-13. (1 + О (1/и)). (В.10) Дифференцируя энтропийную функцию Н (Л), покажите, что ее макси- мум достигается при Л = 1/2. Чему равно значение Н (1/2)? Покажите, что для любого натурального и * В.1-14. * В.1-15. ( )Й= 2" (В.11) В.!-7. При выборе )с объектов из и один из объектов можно пометить специальным образом и следить, выбран он или нет. Используя этот подход, докажите, что Часть Ч11!. Приложения: математические основы 1232 В.2 Вероятность Вероятность является очень важным инструментом при разработке и анализе вероятностных и ранцомизированных алгоритмов.
В этом разделе вы познакомитесь с основами теории вероятности. Мы определим вероятность с помощью пространства событий (зашр1е зрасе) Я, которое представляет собой множество элементарных событий (е!ешепга~у ечеп!з). Каждое элементарное событие может рассматриваться как возможный исход некоторого эксперимента. Например, в случае эксперимента, состоящего в подбрасывании двух различимых монеток пространство событий состоит из всех возможных 2-строк над множеством (О,Р) (где о обозначает выпадение орла, а р-решкн: Я = (ОО,ОР,РО,РР). Событие (ечепг) представляет собой подмножество пространства событий Б.
Например, в эксперименте с бросанием двух монет событием может быть выпадение одного орла и одной решки: (ОР, РО). Событие Я называется достоверным событием (сенаш ечеп1), а событие И вЂ” невохионсным (пн11 ечепг). Мы говорим, что два события А и В являются взаимоисключающими (пшшайу ехс1пз(че), если А О В = 9.
Каждое элементарное событие в е Я также будет рассматриваться нами как событие (в). Все элементарные события по определению являются взаимоисключающими. Аксиомы вероятности Распределение вероятностей (ргоЬаЬ!11!у д(зпзЬщ(оп) Рг () на пространстве событий Я отображает события на действительные числа, удовлетворяя при этом аксиомам вероятности: !. Для любого события А Рг (А) > О. 2. Рг(Я) = 1.
3. Для любых двух взаимоисключающих событий А и В Рг(АОВ) = Рг(А)+ + Рг(В). В общем случае для любой (конечной нлн бесконечной счетной) последовательности попарно взаимоисключающих событий Аы Аз,... Рг Ц А; = ~> Рг (Аз). Мы называем Рг(А) вероятностью (ргоЬаЬ1!1гу) события А. Заметим, что аксиома 2 выполняет нормализующее действие: нет никаких фундаментальных оснований в выборе в качестве вероятности достоверного события именно 1; просто такое значение наиболее естественное и удобное. Приложение В. Комбинаторика и теория вероятности 1233 Некоторые результаты следуют непосредственно из приведенных аксиом и основ теории множеств (см.
раздел Б.1). Невозможное событие имеет вероятность Рг (9) = О. Если А С В, то Рг (А) < Рг (В). Используя запись А для обозначения события Я вЂ” А (дополнения (сошр!ешепг) А), получим Рг (А) = 1 — Рг (А). Для любых двух событий А и В Рг(АОВ) = Рг(А)+Рг(В) — Рг(АПВ) < < Рг (А) + Рг (В) (В.12) (В.13) Предположим, что в нашем примере с бросанием монет вероятность каждого из четырех элементарных событий равна 1/4. Тогда вероятность получить как минимум одного орла равна Рг(ОО,ОР, РО) =- Рг(00) + Рг(ОР) + Рг(РО) =- 3/4. Другой способ получить эту вероятность — это заметить, что единственный способ получить при броске меньше одного орла — это выпадение двух решек, вероятность чего равна Рг (РР) = 1/4, так что вероятность получить по крайней мере одного орла равна 1 — 1/4 = 3/4.
Дискретные распределения вероятностей Рг (А) = ,'> Рг (з), зеА поскольку элементарные события, составляющие А, являются взаимоисключающими. Если Я конечно и каждое элементарное событие з е Я имеет вероятность Рг(з) = 1/!5), то мы имеем дело с равномерным распределением веронгнностей (пп!гопп ргоЬ- аЬ11!гу г!1зп!Ьш!оп) на Я. В таком случае эксперимент часто описывается словами "выберем случайным образом элемент Я".
В качестве примера рассмотрим бросание симмегнричной монеты ((а!г сош), для которой вероятность выпадения орла равна вероятности выпадения решки и составляет 1/2. Если мы бросаем монету и раз, то получим равномерное распределение вероятностей на пространстве событий Я = (О,Р)" (которое представляет собой множество размером 2"). Каждое элементарное событие Я может Распределение вероятностей называется дискрегнным (йзсгеге), если оно определено на конечном или бесконечном счетном пространстве событий. Пусть 5— пространство событий, Тогда для любого события А Часть ЧП!. Приложения: математические основы 1234 быть представлено строкой длиной п на множестве (О,Р), и вероятность каждого элементарного события равна 1/2".
Событие А = (Выпало ровно )с орлов и и — й решек) представляет собой подмножество Я размером ]А[ = (ь), поскольку имеется ровно (",) строк длиной и на множестве (О,Р), содержащих lс О. Вероятность события А, таким образом, равна ("„)/2". Непрерывное равномерное распределение вероятности Непрерывное равномерное распределение вероятности представляет собой пример распределения вероятности, в котором не все подмножества пространства событий рассматриваются как события. Непрерывное равномерное распределение вероятности определено на закрытом отрезке [а, 6] действительных чисел (а < 6).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
