Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 275
Текст из файла (страница 275)
уравнение (Б.4)). Например, имея 28 сортов мороженого и 4 разных сиропа, можно приготовить 28 4 = 112 различных вариантов мороженого с сиропом. Строки Строкой (зптп8) на конечном множестве Я называют последовательность элементов Я. Например, вот восемь двоичных (составленных из 0 и 1) строк длиной 3: 000,001,010,011,100,101,110,111 . Иногда строки длиной /с называются й-строкомн.
Подстрокой (зпбзнтпй) а' строки з называется упорядоченная последовательность элементов з. Подстрока длиной /с называется /с-подстрокой. Например, 010 — 3-подстрока строки 01101001 (начинающаяся с четвертой позиции строки); 111 же подстрокой указанной строки не является. /с-строка на множестве Я может рассматриваться как элемент декартова произведения /с-кортежей Я", так что всего имеется ~Я~ строк длиной /с, в частности— число двоичных /с-строк равно 2й.
Интуитивно это очевидно: при построении /сстроки из множества с и элементами имеется и вариантов выбора первого элемента строки; для каждого из первых элементов имеется и вариантов выбора второго элемента строки, и так Ь раз.
Это приводит нас к /с-кратному произведению и дает общее количество /с-строк, равное и и . и = и". Перестановки Перестановкой (репппсабоп) конечного множества Я называется упорядоченная последовательность всех элементов Я, в которой каждый элемент встречается ровно один раз. Например, если 5 = (а, Ь, с), то имеется шесть перестановок Я; аЬс, асЬ, Ьас, бса, саЬ, сба Всего имеется и! перестановок множества из и элементов, поскольку первый элемент может быть выбран и способами, второй — и — 1 способом, третий — и — 2 и т.д.
й-перестановкой Я называется упорядоченная последовательность /с элементов из Я, в которой ни один элемент не встречается дважды (таким образом, обычная перестановка представляет собой и-перестановку множества из и элементов. Для множества (а, Ь, с, с/) имеется двенадцать 2-перестановок: аЬ,ас,ас/, ба, Ьс, Ы,са,сЬ,сс/,с/а,с/Ь,с/с . 'В отечественной литературе й-перествиоввв ниыяается раяммаеннен — Примеч. нер. Приложение и 1гоибиноторико и теория вероятности 1737 Количество Ь-перестановок множества из и элементов равно и! и(и — 1)(и — 2) (и — )с+ 1) = (и — lс)! (В.
1) Сочетания Сочетаниями ()с-сошЬ!пабоп) из и элементов по и называются Ь-элементные подмножества и-элементного множества. Например, имеется шесть сочетаний по два элемента из множества (а, 6, с, с(): аЬ, ас, аН, Ьс, Ы, ст! (Здесь для простоты для записи подмножества (а, Ь) использована краткая запись аЬ.) Для построения сочетания нз множества просто выбирается )с различных элементов. Порядок выбора элементов значения не имеет. Количество сочетаний можно выразить через количество размещений. Для каждого сочетания имеется !с! перестановок его элементов, каждая из которых представляет собой одно из размещений из и элементов по )с.
Таким образом, количество сочетаний из и элементов по Ь равно количеству размещений, деленному на тс!, т.е. с учетом (В.1) количество сочетаний из и элементов по lс равно и'. (В.2) )с! (и — )с)! При 1с = О эта формула дает единицу, т.е. выбрать пустое подмножество можно единственным способом (напомним, что О! = 1). Биномиальные коэффициенты Для числа сочетаний из и элементов по )с используется обозначение („)з. Из (В.2) следует, что Эта формула симметрична относительно Й и и — Й: (В.З) эн отечттвенной лнтерагуре лля этой величины принято обоэнвченне Св — Примеч.
лер поскольку имеется и способов выбора первого элемента, и — 1 — второго н так до последнего, Ь-го элемента, который можно выбрать из оставшихся и — !с + 1 элементов множества. Прилозкение В. Комбинаторика и теория вероятности Для всех целых О < й < и по индукции можно доказать (см. упр. В.1.12), что ~ и ~п ~ т и и" < ь/ — )сь(и ь)п — ь (В.б) где для удобства принято, что О = 1. Для к = Ли, где О < Л < 1, зто неравенство можно переписать как — 2П н(л) где Н(Л) = — Л18Л вЂ” (1 — Л) 18(1 — Л) (В.?) называется (двоичной) энтропийной функцией (Ыпагу епПору йщс1юп). Для удобства принято, что О 18 О = О, так что Н(О) = Н(1) = О. Упражнения В.1.1 Сколько к-подстрок имеется у и-строки? (Одинаковые подстроки, начинающиеся в разных позициях строки, считаются разными.) Сколько всего подстрок имеется у строки длиной и? В.1.3 Сколькими способами и профессоров могут разместиться на конференции за круглым столом? Варианты, отличающиеся поворотом, считаются одинаковыми.
В.1.4 Сколькими способами можно выбрать нз множества (1, 2,..., 99) три различных числа так, чтобы их сумма была четной? В.1.5 Докажите тождество (В. 8) для О < й < и. В.1.г Булава функция (Ьоо1еап йшсбоп) с и входами и т выходами — зто функция с областью определения (таин, ульзн)" и областью значений (таин, глг.зн) Сколыю всего имеется различных функций с и входами и одним выходом? С и входами и т выходами? 1240 Часть Л!1. Приеажениве матаиатичесние основы В.1.б Докажите тождество для 0 < к < п. В.1.
7 При выборе к объектов из п один из обьектов можно пометить специальным образом и отслеживать, выбран он или нет. Используя этот подход, докажите, что В.1.8 Используя результат упр. В.1.7, составьте таблицу биномиальных коэффициентов ("„) для и = 0,1,...,6 и 0 < (с < п в виде равнобедренного треугольника (в первой строке — (с), во второй — (') и (,') и т.д.). Такая таблица биномиальных коэффициентов называется вереугольником Паскаля. В.1.9 Докажите, что В.1.10 Покажите, что для любых целых чисел и > 0 и 0 < )с < и выражение Я) достигает максимального значения при (с = '(п/2) или к = ~п/21. В.1.11 * Докажите, что для любых целых чисел п > О, 1 > О, (с > 0 и у + й < и (В.9) Приведите как алгебраическое доказательство данного неравенства, так и доказательство, основанное на рассуждениях о выборе ч'+ к элементов из и.
Приведите пример, когда выполняется строгое неравенство. В.1.12 * Докажите неравенство (В.б) по индукции по всем 0 < к < и/2, а затем воспользуйтесь уравнением (В.З) для распространения результата на все 0 < 1с < и. В.1.13 * Воспользуйтесь приближением Стирлинга для доказательства того, что 1241 Притогиение В. Кимбиноторино и теория вероятности В.1.14 * Дифференцируя энтропийную функцию Н(Л), покажите, что ее максимум достигается при Л = 11'2. Чему равно значение Н(11'2)? В.1.15 * Покажите, что для любого целого и > О (В.!1) В.2.
Вероятность Вероятность является очень важным инструментом в процессе разработки и анализа вероятностных и рандомизированных алгоритмов. В этом разделе вы познакомитесь с основами теории вероятности. Мы определим вероятность с помощью нространстаа выборок (зашр!е брасе) Я, которое представляет собой множество элементарных событий (е1ешепразу ечепгб). Каждое элементарное событие может рассматриваться как возможный исход некоторого эксперимента.
Например, в случае эксперимента, состоящего в подбрасывании двух различимых монеток пространство выборок состоит из всех возможных 2-строк над множеством (О,Р) (где О обозначает выпадение орла, а Р— решки): Я = (ОО, ОР, РО, РР) Собвнние (ечепг) представляет собой подмножествоз пространства выборок Я. Например, в эксперименте с бросанием двух монет событием может быть выпадение одного орла и одной решки: (ОР, РО). Событие Я называется достоверным событием (сена(п ечепг), а событие 6 — невоэмоисным (ппН ечеп1). Мы говорим, что два события, А и В, являются взаимоисключающими (ппппа!!у ехс!пз(че), если А Р1 В = 6. Каждое элементарное событие л е В также будет рассматриваться нами как событие (л).
Все элементарные события по определению являются взаимоисключающими. зВ случае обобшенного распределения вероятностей могут иметься некоторые пслмножества пространства выборок Я, которые не рассматривазжся как события. такая сизуапия обычно возникает, когда пространство выборок несчетно бесконечное.
Главное требование, которому должны отвечать подмножества, чтобы быть событиями, заключается а том, что множество событий пространства выборок должно быть замкнуто относительно оперений дополнения к событию, объединения конечного или счетного числа событий и пересечения конечного или счетного числа событий. Большинство распределений вероятностей, с которыми нам придется иметь дело, — иал конечным нли счетным пространством выборок, так что мы в общем случае будем рассматривать все подмножества просгранспю выборок как события. Важным исключением является непрерывное равномерное распределение вероятностей, с жпорым мы вскоре встретимся. Часть УШ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
