Алгоритмы - построение и анализ (1021735), страница 254
Текст из файла (страница 254)
В.1 Основы комбинаторики Комбинаторика пытается ответить на вопрос "Сколько?", не выполняя перечисления. Например, вы можете спросить "Сколько всего имеется различных и- битовых чисел?" или "Сколькими способами можно упорядочить и различных чисел?" Здесь мы познакомимся с азами комбинаторики, которые предполагают знание основ теории множеств, так что, надеемся, вы основательно проработали предыдущее приложение. Приложение В. Комбинаторика и теория вероятности 1227 Правила суммы и произведения Множество, количество элементов которого мы хотим подсчитать, иногда можно выразить как объединение непересекающихся множеств или как декартово произведение множеств.
Правило суммы гласит, что количество способов, которыми можно выбрать элемент из одного из двух непересекающихся множеств, равно сумме мощностей этих множеств. То есть, если А и  — два конечных множества без общих членов, то )А 1.1 В1 = )А) + (В(, что следует из уравнения (Б.З). Например, если каждый символ в номере машины должен быть либо латинской буквой, либо цифрой, то всего имеется 2б+ 10 = 36 различных вариантов выбора этого символа, т.к. всего имеется 26 вариантов выбора буквы и 10 — цифры.
Правило произведения гласит, что количество способов, которыми можно выбрать упорядоченную пару, равно количеству вариантов выбора первого элемента, умноженному на количество вариантов выбора второго элемента. То есть, если А и  — конечные множества, то )А х В) = )А!.1В~ (см. уравнение (Б.4)). Например, имея 28 сортов мороженого и 4 разных сиропа, можно приготовить 28 4 = 112 различных вариантов мороженого с сиропом. Строки Сюирокой (мпп8) на конечном множестве Я называют последовательность элементов Я.
Например, вот восемь двоичных (составленных из 0 и 1) строк длины 3: 000, 001, 010, 011, 100, 101, 110, 111. Иногда строки длиной к называются й-сюро«ами. Подстрокой (зпЬз1г1п8) в' строки в называется упорядоченная последовательность элементов в. Подстрока длиной /с называется к-подстрокой. Например, 010 — 3-подстрока строки 01101001 (начинающаяся с 4 позиции строки); 111 же подстрокой указанной строки не является.
й-сюирока на множестве Я может рассматриваться как элемент декартова произведения Я", так что всего имеется 15~ строк длины 1с, в частности, число двоичных к-строк равно 2 . Интуитивно это очевидно — при построении к-строки ь из множества с и элементами у нас имеется и вариантов выбора первого элемента строки; для каждого из первых элементов у нас имеется и вариантов выбора второго элемента строки, и так /с раз. Это дает нам общее количество /с-строк, равное п и.... п=п". Перестановки Пересюиановкой (реппп1абоп) конечного множества 5 называется упорядоченная последовательность всех элементов Я, в которой каждый элемент встречается ровно один раз.
Например, если Я = (а, Ь, с), то имеется шесть перестановок Я: аЬс, асЬ, Ьас, Ьса, саЬ, сЬа. Часть Ч1П. Приложения: математические основы 1228 Всего имеется и! перестановок множества из п элементов, поскольку первый элемент может быть выбран п способами, второй — п — 1 способом, третий— и — 2 и т.д. и-нерестановкой' Я называется упорядоченная последовательность lс элементов из Я, в которой ни один элемент не встречается дважды (таким образом, обычная перестановка представляет собой и-перестановку множества из и элементов. Для множества Я = (а, Ь, с, с!) имеется двенадцать 2-перестановок: аЬ, ас, ас1, Ьа, Ьс, Ы, са, сЬ, сс1, с!а, с1Ь, с!с. Количество Й-перестановок множества из и элементов равно и! п(п — 1) (и — 2) (и — 1с+ 1) = (и — !с)! (В.1) поскольку имеется п способов выбора первого элемента, п — 1 — второго и т.д., до последнего, !с-го элемента, который можно выбрать из оставшихся и — и + 1 элементов множества.
Сочетания Сочетаниями (к-сошЬ(папоп) из п элементов по !с называются к-элементные подмножества п-элементного множества. Например, имеется шесть сочетаний по 2 элемента из множества Я = (а, Ь, с, с1): аЬ, ас, ас(, Ьс, Ы, сд. и.' (В.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") как суммы количества строк с разным числом единиц (имеется ("„) двоичных строк длины и с !с единицами, т.к.
(",) — количество способов выбрать !с позиций для единиц в строке длины и). Имеется масса различных тождеств, в которых принимают участие биномиальные коэффициенты (с неюторыми из них вы познаюмитесь в упражнениях к данному разделу). 1230 Часть ЧП1. Приложения: математические основы Для всех 0 < lс < п по индукции можно доказать (см. упражнение В.1-12), что (В.б) где для удобства принято, что Оо = 1. Для и = Лп, где 0 < Л < 1, это неравенство можно переписать как и / л г х1" Лп (Лп)хп «1 Л) п)(1 х) ~ Л 1 Л ) где Н (Л) = -Л 18Л - (1 - Л) 18(1 - Л) (В.?) называется (двоичной) энтропийной функцией (Ь1пагу еппору йпсбоп). Для удобства принято, что 0 18 0 = О, так что Н (0) = Н (1) = О. Упражнения В.1-1. Сколько имеется lс-подстрок у и-строки? (Одинаковые подстроки, начинающиеся в разных позициях строки, считаются разными.) Сколько всего подстрок имеется у строки длиной и? В.1-2.
Булева функция (Ьоо1еап йщс11оп) с п входами и т выходами — это функция с областью определения (ТК()Е, РА1.БЕ)" и областью значений (ТЮЗЕ, РА(.БЕ)~. Сколько всего имеется различных функций с п входами и 1 выходом? С и входами и т выходами? В.1-3. Сколькими способами и профессоров могут разместиться на конференции за круглым столом? Варианты, отличающиеся поворотом, считаются одинаковыми. В.1-4. Сколькими способами можно выбрать из множества (1, 2,..., 100) три различных числа так, чтобы их сумма была четной? В.1-5. Докажите тождество для 0 < /с < и.
(В.8) В.1-6. Докажите тождество — для 0 < и < п. Приложение В. Комбинаторика и теория вероятности 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 Вероятность Вероятность является очень важным инструментом при разработке и анализе вероятностных и ранцомизированных алгоритмов. В этом разделе вы познакомитесь с основами теории вероятности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
