12. Формирование перестановок и сочетаний. Лексикографический порядок.

Для начала введем понятие лексикографического порядка. Лексикографическим порядок называется потому, что он лежит в основе упорядочения слов в словаре. Например, слово able в английском словаре стоит перед словом gray, так как в алфавите буква а стоит перед буквой g.

ОПРЕДЕЛЕНИЕ 8.46. Для заданного линейно упорядоченного множества S лексикографический порядок < на строках элементов множества S определяется следующим образом: а < b, если а = а₁,a₂,a₃,…a_m, b = b₁,b₂,b₃,…b_n, и выполнено одно из условий: а) а₁ < b₁; б) а_i = b_i для всех 1 < i < k и а_k+1 < b _k+1; в) а_i = b_i для всех 1 < i < т. и т < n.

Теперь будем формировать множество всех перестановок элементов линейно упорядоченного множества. Для простоты рассмотрим только перестановки пер­вых n целых чисел, отметив, что метод справедлив и для прочих случаев. Пусть строка а₁,a₂,а₃ ...а_n обозначает перестановку

Таким образом, 51342 представляет перестановку

(	1	2	3	4	5	)
	5	1	3	4	2

Для нахождения всех перестановок необходимо иметь возможность сформи­ровать перестановку, следующую за данной согласно лексикографическому поряд­ку. .Поэтому для формирования следующей строки необходимо менять те сим­волы, которые ближе всего к концу. Предположим, что a_i > а_i+1 для т < a_i < n. Если бы это условие выполнялось для всех неотрицательных т, то мы имели бы лексикографически наибольшую строку, что означало бы завершение процесса. Поэтому допустим, что существует такое т, что а_i > а_i+1 для т < i < n, но а_т < а_m+1. Если переупорядочить все а_i, где i > m, то мы создадим строку, кото­рая будет лексикографически меньше

Таким образом, приходим к следующей процедуре:

Процедура Формирование перестановки (а₁ ,..., a_n) Найти т такое, что а_i > а_{i + 1} для т < i < n, но а_т < а_m+1; Выбрать наименьшую цифру а_i, такую что i > m и а_т < а_i; Поменять местами a_m и а_i; Переупорядочить все а_i, стоящие после нового а_т, в возрастающем порядке; Конец процедуры.

Теперь рассмотрим метод формирования всевозможных сочетаний из n эле­ментов множества S. Мы не будем использовать лексикографический порядок элементов множества S, а воспользуемся лексикографическим порядком на стро­ках бинарных чисел. Напомним, что любому сочетанию элементов из n элемен­тов соответствует бинарная строка длины n. Если множество S задано в виде {а₁, а₂, а₃, … а_n}. то единица на месте k:-го бита в бинарной строке показывает, что а_k присутствует в выбранном подмножестве, в то время как 0 в том же ме­сте бинарной строки показывает, что а_k.– не включено в выбранное подмножество. Например, если множество S представляет собой {а₁, а₂, а₃, а₄, а₅}, то 10110 со­ответствует выбору подмножества {а₁, а₃, a₄}, а 10001 – выбору подмножества { а₁, а₅}. Таким образом, для формирования всех сочетаний из множества n эле­ментов достаточно сформировать все бинарные строки длины n. С этой целью проще всего сосчитать от 0 до 2ⁿ – 1, используя бинарные строки длины n.

Эквивалентный метод состоит в том, чтобы показать, как по данной бинар­ной строке длины n построить следующую бинарную строку такой же длины. Для этого достаточно найти в строке первый 0 справа, заменить его на 1, а все элемен­ты справа от новой единицы заменить на 0. Как говорилось ранее, формирование сочетаний не является лексикографическим упорядочением объектов множества, а представляет собой лексикографическое упорядочение бинарных строк.

13. Приложения комбинаторики к задачам теории вероятности в случае равновозможности всех исходов эксперимента.

Наша концепция вероятности будет зависеть от того, что мы понимаем под экспериментом. Оставив термин "эксперимент" неопределенным, зададимся це­лью, чтобы он отвечал следующим условиям: а) эксперимент дает более одного исхода; б)исход точно не известен; в) конечное множество всех исходов может быть определено до начала эксперимента; г) эксперимент можно повторить при тех же условиях. Примером эксперимента является подбрасывание двух монет. В этом случае множество исходов S = {(H,H), (H, T), (T, H), (T, T)}, где H обозначает падение монеты вверх "орлом", а Т – падение монеты "решкой" вверх.

ОПРЕДЕЛЕНИЕ 8.48. Выборочное пространство, или множество элемен­тарных событий – это множество всех исходов эксперимента. Событие – подмножество выборочного пространства.

Таким образом, множество S – это выборочное пространство. На языке теории множеств выборочное пространство S является универсом.

имеем

Интуитивно, вероятность события – это вероятность того, что событие на­ступит. Если эксперимент повторяется несколько раз, то вероятность события – это частота наступления события. В этом и следующих разделах будем предполагать, что все исходы эксперимента равновозможны. Заметим, что это вовсе не означает, что все события в мире равновозможны. Просто такое предположение дает нам возможность использовать комбинаторные принципы, поскольку вероятность – одно из основных приложений комбинаторики. С учетом этого предположения сформулируем определение вероятности. ОПРЕДЕЛЕНИЕ 8.49. Пусть S – множество всех возможных исходов экспе­римента. Вероятность Р(А) наступления события А определяется как отношение

P(A)

=

|A| |S|

ТЕОРЕМА 8.52. Если A и В – непересекающиеся множества исходов экспери­мента, то Р(A  B) = P(A) + P(B)

ДОКАЗАТЕЛЬСТВО. Используя принцип сложения,

ТЕОРЕМА 8.53. Если S – выборочное пространство, А' - дополнение множества А до множества S как универса, то а) P(S) = 1. б) Р(А') = 1 – Р(А). в) Р() = 0. г)Для каждого события А имеем Р(А) > 0. д)Если А  В, то Р(А) < Р(В). е)Для каждого события А имеем 0 < Р(А) < 1.

ДОКАЗАТЕЛЬСТВО, a) P(S) = |S|/|S| = 1. б) Согласно пункту (а) и предыдущей теореме имеем 1 = P(S) = Р(А  А') = Р(А) + Р(А'). Поэтому Р(А') = 1 – Р(А).

в)Согласно пункту (б) имеем Р() = 1 – Р(') = 1 – P(S) = 1– 1 = 0.

г)Поскольку должно существовать не менее одного исхода, то |S| > 0. Кроме того, |А| > 0, учитывая, что множество А содержит некоторое число элементов. Следовательно,

д) Если А  В, то В = А+(В – А). Поэтому Р(B) = Р(А + (В – А)) = Р(А) + Р(В – А) и Р(В) – Р(А) = Р(В – А), Однако, согласно пункту (г), P(B – A) > 0

Поэтому Р(В) – Р(А) > 0 и P(A)  P(B) е) Поскольку А  S, то Р(А) < Р(S) = 1. Объединяя с пунктом (г), получаем 0 < P(A) < 1

ТЕОРЕМА 8.56. Если А и В – множества исходов эксперимента, то Р(А  В) = Р(А) + Р(В) – Р(А  В).

ДОКАЗАТЕЛЬСТВО. На рис. 8.12 показано, что А = (А – В)  (А  В), В = {В – A)  (А  В), и A  В = (А – В)  (А  В)  (В – А), где (А – В), (А  В) и (В – А) – попарно непересекающиеся множества.

Поэтому, по теореме 8.6 имеем Р(А) = Р((А – B)  (A  В)) = Р(А – В) + Р(А  В), Р(В) = Р((В – A)  (А  В)) = Р(В – А) + Р(А  В), и Р(А В) = Р((А – В)  (A  В)  (В – А)) = Р(А – В) + Р(А  В) + Р(В – А).

Следовательно, Р(А) + Р(В) = (Р(А – В) + Р(А  В)) + (Р(В –А) + Р(А  В)) = (Р(А – В)+Р(А  В) + (Р(В – А)) + Р(А  В) = Р(А  В)+Р(А  В), так что Р(А  B) = Р(А) + Р(В) – Р(А  В).