Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 61
Текст из файла (страница 61)
Таким образом, для формирования всех сочетаний из множества п элементов достаточно сформировать все бинарные строки длины и. С этой целью проще всего сосчитать от 0 до 2" — 1, используя бинарные строки длины п. Эквивалентный метод состоит в том, чтобы показать, как по данной бинарной строке длины и построить следующую бинарную строку такой же длины.
Для этого достаточно найти в строке первый 0 справа, заменить его на 1, а все элементы справа от новой единицы заменить на О. Как говорилось ранее, формирование сочетаний не является лексикографическим упорядочением объектов множества, а представляет собой лексикографическое упорядочение бинарных строк. ПРИМЕР 8.47. Пусть о = 1а,6, с, Н, е).
Найдем сочетание, следующее за 1а,г1, е). Поскольку сочетанию (а, Н,е) соответствует бинарная строка 10011, следующей строкой будет 10100. Поэтому следующим сочетанием будет 1а,с). С) Рассмотрим, наконец, как сформировать все сочетания по т элементов, выбранных из элементов линейно упорядоченного множества Я. Снова воспользуемся лексикографическим упорядочением элементов множества Я. Как и ранее, не ограничивая общности, можем положить Я = 11,2, 3,... п).
Будем предполагать, что сочетания перечислены в возрастающем порядке. Как и для перестановок, покажем, как по данному сочетанию найти следующее согласно лексикографическому порядку. Предположим, что и = 5 и г = 3. Если можно увеличить последнюю цифру, то так и будем делать. Поэтому, если имеем число 123, то его можно заменить на 124. Если имеем 125, то последнюю цифру увеличивать нельзя. Отсюда переходим к следующей цифре и смотрим, можно ли ее увеличить.
В данном случае это можно сделать, поменяв 2 на 3. Однако мы стремимся построить наименьшее число из тех, которые больше 125. Поэтому увеличиваем последнюю цифру на 1. Имеем первые две две цифры 1 и 3, значит, следующее число — 134. Предположим, что имеется число 145. Последнюю и предпоследнюю цифры нельзя увеличивать. Однако, 1-ю цифру увеличить можно, поэтому 1 увеличиваем до 2. Чтобы сделать число минимальным, в качестве последних цифр возьмем 3 и 4, В результате получаем число 234. Если начинать справа, то значение последней цифры будет наибольшим возможным, если оно равно п = и — т + г. Если последняя цифра — наибольшая возможная, то предыдущая цифра будет наибольшей возможной, если она равна и — г+ (г — 1) или и — г+ г, где 1 = г — 1 — позиция предыдущей цифры.
В общем случае, значение каждой г-ой цифры будет наибольшим возможным, если цифры справа — наибольшие возможные, и это значение равно п — т + 1. Для формирования максимальной перестановки идем справа налево и проверяем, равно ли значение 1-го элемента величине и — т + г, Первое значение, которое не удовлетворяет этому условию, можно увеличить. Например, это эначение т на 1-ом месте. Увеличиваем гп на 1 и затем увеличиваем значение каждого элемента, стоящего после 1-го, на 1 значения предыдущего элемента.
В результате 346 ГЛЯВА 8. Комбинаторика и вероятность приходим к следующей процедуре: Процедура г-сочетание (тз, г) Начиная справа, найти первую цифру со значением а,, таким что сч ф п — г+ 1; Прибавить единицу к этому значению а;; Начиная с а,~ы увеличиваем его значение на 1; Конец процедуры. ° УПРАЖНЕНИЯ 1. Определите перестановку, следующую за 21435. 2. Определите перестановку, следующую за 621435. 3. Определите перестановку, следующую за 21453. 4. Определите перестановку, следующую за 416532. 5.
Пусть Ь' = (а,Ь,с, Н,е). Определите сочетание, следующее за (а,с, Н). 6. Пусть Ь' = (а, Ь, с, Н, е), Определите сочетание, следующее за (а,с,Ы,е). 7. Пусть 8 = (1,2,3,4,5). Определите сочетание, следующее за (1,4,5). 8. Пусть о = (1,2,3,4,5,6). Определите сочетание, следующее за (1,3,5,6). 9. Пусть 8 = (1,2,3,4,5,6). Определите сочетание, следующее за (1,6). 10. Пусть о = (1, 2, 3, 4, 5, 6). Определите трехэлементное сочетание, следующее за (1,5,6).
11. Пусть о = (1, 2,3,4, 5,6). Определите трехэлементное сочетание, следующее за (1,4,6). 12. Пусть о = (1,2,3,4,5,6). Определите четырехэлементное сочетание, следующее за (1,4,5,6). 13. Пусть о = (1,2,3,4,5,6). Определите четырехэлементное сочетание, следующее за (1,3,4,5). 14. Перечислите все перестановки 1,2,3,4 в лексикографическом порядке. 16. Перечислите все перестановки х,у, з в лексикографическом порядке.
16. Сформируйте все трехэлементные подмножества множества (1,2, 3,4,5). 17. Сформируйте все трехэлементные подмножества множества (а, Ь,с, Н, е). 18. Найдите первый и последний элементы в списке перестановок целых чисел (1,2,3,4,5,6,7). 19. Найдите первый и последний элементы в списке перестановок букв английского алфавита. 20. Найдите первый и последний элементы в списке трехэлементных подмножеств множества целых чисел (0,1,2,3,4,5,6,7,8,9). 21. Найдите первый и последний элементы в списке пятиэлементных подмножеств множества букв английского алфавита. 22. Найдите первый и последний элементы в списке пятиэлементных подмножеств множества букв английского алфавита.
23. Используя алгоритмы данного раздела, разработайте алгоритм формирования Р(п, г) всех перестановок г из п элементов. 24. Используя алгоритмы предыдущего упражнения, сформируйте перестановки трехэлементных подмножеств множества (а,Ь,с,д,е). РАЗДЕЛ 5.5. Введение вероятности 347 8.5. ВВЕДЕНИЕ ВЕРОЯТНОСТИ Много лет назад студент Стэнфордского университета послал письмо в бюро погоды города Сан-Франциско с вопросом, что они имели в виду, прогнозируя выпадения дождя с вероятностью 60%.
Означает ли это, что дождь будет идти на 60% всей плошади? Означает ли это, что дождь будет идти 60% времени? "Это означает, — ответило бюро, — что из десяти сотрудников шесть человек утверждали, что пойдет дождь'*. Вскоре мы увидим, что все на самом деле зависит от выборочного пространства. Многие задачи теории вероятностей и комбинаторики сконцентрированы вокруг азартных игр. Одна из причин заключается в том, что математики, разработавшие значительную часть данной теории, были наняты компаниями, контролировавшими игорный бизнес, для расчетов вероятностей выигрыша или проигрыша в тех или иных азартных играх. Многие из этих игр служат замечательным примером использования вероятности.
Вероятность позволит читателю оценить, как много он может потерять, если будет неверно выполнять свое домашнее задание. Наша концепция вероятности будет зависеть от того, что мы понимаем под экспериментом. Оставив термин "эксперимент" неопределенным, зададимся целью, чтобы он отвечал следующим условиям: а) эксперимент дает более одного исхода; б) исход точно не известен; в) конечное множество всех исходов может быть определено до начала эксперимента; г) эксперимент можно повторить при тех же условиях. Примером эксперимента является подбрасывание двух монет.
В этом случае множество исходов Я = ((Н, Н), (Н, Т), (Т, Н), (Т, Т)), где Н обозначает падение монеты вверх "орлом", а Т вЂ” падение монеты "решкой" вверх. Другим примером эксперимента служит подбрасывание монеты и игральной кости. В этом случае множество результатов Я = ((Н, 1), (Н, 2), (Н, 3), (Н, 4), (Н, 5), (Н, 6), (Т, 1), (Т, 2), (Т, 3), (Т,4), (Т, 5), (Т,6)), где за результатом выпадения монеты обозначен результат выпадения кости. ОПРЕДЕЛЕНИЕ 8.48. Выборочное пространство, или множество элементарных событий — это множество всех исходов эксперимента.
Событие— подмножество выборочного пространства. Таким образом, в каждом из приведенных выше примеров множество В— это выборочное пространство. На языке теории множеств выборочное пространство о' является универсом. 348 ГПКВА а, комбинвторинв и вероятность Интуитивно, вероятность события — это вероятность того, что событие наступит. Если эксперимент повторяется несколько раз, то вероятность события— это частота наступления события. В этом и следующих разделах будем предполагать, что все исходы эксперимента равновозможны.
Заметим, что это вовсе не означает, что все события в мире равновозможны. Просто такое предположение дает нам возможность использовать комбинаторные принципы, поскольку вероятность — одно из основных приложений комбинаторики. С учетом этого предположения сформулируем определение вероятности. ПРИМЕР 8.50.
Пусть Я вЂ” множество всех исходов подбрасывания двух костей. Пусть А — множество всех исходов, при которых сумма показаний двух костей равна 6. Таким образом, А = ((1, 5), (2, 4), (3, 3), (4, 2), (5, 1)). так что (А! = 5. Как было показано выше, если существуют шесть возможных исходов выпадений для первой кости и шесть возможных исходов выпадений для второй кости, то множество Я содержит 6 х 6 возможных исходов. Поэтому Р(А) = — = —.
)А( 5 )Я! 36 ПРИМЕР 8.51. Пусть  — множество всех исходов при подбрасывании двух монет. Пусть А — множество исходов, когда обе монеты выпадают одинаково. Таким образом, А = ((Н, Н), (Т, Т)), Я = ((Н, Н), (Н, Т), (Т, Н), (Т, Т)) и )А( 2 1 Р(А) = — = — = —. )В! 4 2 Означает ли это, что если мы подбросим две монеты четыре раза, то на двух монетах выпадут одновременно "орлы" или "решки" точно два раза? Конечно, нет. Однако, если мы подбросим две монеты 400 раз, то можно ожидать, что монеты выпадут надлежащим образом порядка 200 раз. Предположив опять, что все исходы равновозможны, и воспользовавшись приемами комбинаторики, можем доказать приведенные ниже теоремы.
ТЕОРЕМА 8.52. Если А и  — непересекающиеся множества исходов эксперимента, то Р(А О В) = Р(А) + Р(В). РАЭДсЛ 8.5. Введение вероятности 349 ДОКАЗАТЕЛЬСТВО. Используя принцип сложения, имеем Р(А иВ) = ! !В! !А!+ !В! !В! !А! !В! = — + — = !Я !В! = Р(А) + Р(В). Следующая теорема определяет некоторые из свойств вероятности события. ТЕОРЕМА 8.53. Если Я вЂ” выборочное пространство, А' — дополнение множества А до множества 5 как универса, то а) Р(Б) = 1. б) Р(А') = 1 — Р(А). в) Р(и) = О. г) Для каждого события А имеем Р(А) ) О.
д) Если А С В, то Р(А) < Р(В). е) Для каждого события А имеем О < Р(А) < 1. ДОКАЗАТЕЛЬСТВО. а) Р($) = — = 1. !В! Ф! б) Согласно пункту (а) и предыдущей теореме имеем 1 = Р(Б) = Р(А и А') = Р(А) + Р(А'). Поэтому Р(А') = 1 — Р(А). в) Согласно пункту (б) имеем Р(ю) = 1 — Р(й") = 1 — РЯ = 1 — 1 = О. г) Поскольку должно существовать не менее двух исходов, то !5! ) О. Кроме того, !А! ) О, учитывая, что множество А содержит некоторое число элементов. Следовательно, Р(А) = — ) О. !А! !В! д) Если А С В, то В = А+ ( — А).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
