15. Перестановки и сочетания с повторением.

Один из способов трактовки повторения – это думать, что повторение предполагает возвращение объекта и повторное его использование. Другой способ трактовки данного типа повторения состоит в том, что имеется столь достаточное количество объектов каждого типа, которое нельзя исчерпать. Например, в случае с номерными знаками требуется теперь только три копии каждой буквы и каждой цифры. Приведенная ниже теорема сформулирована для такого представления о повторении.

ТЕОРЕМА 8.66. Пусть S – множество, содержащее n неразличимых объектов. Тогда количество различных перестановок, образованных выбором k элементов с повторением, равно n^k.

ТЕОРЕМА 8.69. Количество различных сочетаний из k объектов по n равно

С(n + k – 1,n) =

С(n + k – 1,k – 1) =

(n+k–1)! n!(k–1)!

ТЕОРЕМА 8.72. Количество различных сочетаний из k объектов по n объектов с повторением, когда необходимо выбрать хотя бы по одному объекту каждого типа, равно

С(n –1, n – k) =

С(n – 1,k – 1) =

(n–1)! (n–k)!(k–1)!

ПРИМЕР 8.74. Найдем количество различных целочисленных решений уравнения n₁ + n₂ + n₃ + n₄ + n₅ = 25, если n₁ > 1, n₂ > 1, n₃ > 2, n₄ > 2, n₅ > 2. Представим эту задачу, как подсчет количества выборок вида n₁ a₁ + n₂а₂ + n₃a₃ + n₄а₄ + n₅а₅, где n₁ + n₂ + n₃ + n₄ + n₅ = 25,причем следует выбрать, по крайней мере, одно а₁, одно а₂, два а₃, два а₄ и два а₅. Это оставляет для выбора только 25 – 8 = 17 элементов из пяти типов, что дает

(17 + 5 – 1)! 17!

=

21! 17!

решений для n₁ + n₂ + n₃ + n₄ + n₅ = 25.

16. ПРИНЦИП ДИРИХЛЕ. Принцип клеток, известный также как принцип Дирихле, – это очень простая, но тем не менее очень мощная идея. Она особенно полезна в теории чисел. Данный раздел состоит из двух довольно простых теорем и нескольких не совсем простых примеров. Начнем с наиболее известной формы принципа клеток.

ТЕОРЕМА 8.75. Если поместить n + 1 голубей в n клеток, то, по крайней мере, в одной клетке будет находится более одного голубя.

ДОКАЗАТЕЛЬСТВО. Если в каждой клетке не более одного голубя, то голубей не может быть больше, чем клеток. Тогда во всех клетках должно быть не более, чем n голубей, что противоречит условию.

Из теоремы следует, что если т > n и требуется т голубей разместить в n клетках, то в одной клетке находится более одного голубя.

ОПРЕДЕЛЕНИЕ 4.7. Функция f : А –> В называется инъективной, или инъекцией, если из f(а) = f(a') следует а = a'. Функция f называется отображением “на”, или суръективной функцией, или суръекцией, если для каждого b  В существует некоторое а  А такое, что f(а) = b. Функция, которая является одновременно и инъективной и сюръективной, называется взаимно однозначным соответствием, или биекцией. Если А = В и f : А –> В является взаимно однозначным соответствием, то f называется перестановкой множества А.

ТЕОРЕМА 8.81. а) Пусть т> n голубей помещены в n клеток, тогда некоторая клетка содержит не менее m/n голубей. б) Пусть т = m₁ + m₂ + т₃ +… + т_n – n + 1 голубей помещены в n клеток, где m_i – положительное целое число для каждого 1 < i < n. Тогда, для некоторого i, i-ая клетка содержит не менее т_i голубей.

ДОКАЗАТЕЛЬСТВО. а) Пусть каждая клетка содержит меньше m/n голубей. Тогда, поскольку нас интересуют целые голуби, каждая клетка содержит меньше m/n голубей. Поэтому общее количество голубей меньше n x m/n = m, что противоречит условию.

б) Пусть i-ая клетка содержит меньше, чем m_i голубей. Тогда количество голубей в i-ой клетке меньше или равно т_i – 1. Просуммировав по всем клеткам, получаем, что всего голубей не более, чем (m₁ – 1) + (m₂ – 1) + (m₃ – 1) + … + (m_n – 1) = m_1: + m₂ + m₃ + … +m_n – n, что противоречит условию.

ПРИМЕР 8.82. Пусть в урне находятся 10 красных, 10 синих и 10 зеленых ша­ров. Сколько шаров нужно взять из урны, чтобы с уверенностью иметь хотя бы 4 красных или 5 синих, или 6 зеленых шаров? Мы знаем, что 12 шаров недостаточно, поскольку можно выбрать 3 красных, 4 синих и 5 зеленых шаров. Если отождествить шары одного цвета с голубями, находящимися в одной клетке, то, согласно части (б) сильной формы принципа клеток, имеем n = 3, т₁ = 4, m₂ = 5 и m₃ = 5. Поэтому искомое количество шаров равно m = т₁ + m₂ + m₃ + … + т_n – n + 1 = 4 + 5 + 6 – 3 + 1 = 13.

17. Пояснение теории Рамсея на примере полного графа с раскрашенными ребрами. Предположим, что в комнате находятся шесть человек, и каждые два из них либо друзья, либо враги. Тогда есть три человека, которые дружат между собой, или есть три человека, которые враждуют между собой. Выберем одного человека, назовем его А и поставим в середине комнаты. Разместим всех его врагов вдоль южной стены, а всех друзей – вдоль северной стены. Согласно части (а) сильной формы принципа клеток либо не менее трех человек стоят вдоль южной стены, либо не менее трех человек стоят у северной стены. Если у южной стены стоит не менее трех человек, то или трое из них – взаимные друзья, что и требовалось доказать, или двое из них – враги. Тогда эти люди вместе с А ~ трое взаимных врагов. Аналогично, если не менее трех человек стоят у северной стены, то или трое из них – взаимные враги, что и требовалось доказать, или двое из них – друзья. Тогда они вместе с А – трое взаимных друзей.

Рассмотренный выше пример является характерным, хотя и довольно про­стым примером задач из раздела комбинаторики, который носит название теория Рамсея. Можно считать, что нам повезло, поскольку в теории Рамсея очень мало простых примеров. Почти все ее проблемы по сей день не решены. Поясним тео­рию Рамсея на примере полного графа с раскрашенными ребрами. Предположим, что в предыдущем примере вершины графа – аналоги людей. Образуем граф сле­дующим образом: если двое людей – друзья, то соответствующие им вершины соединяет красное ребро. Если двое людей – враги, то соответствующие вершины соединяет синее ребро. Поскольку каждые двое – либо друзья, либо враги, то ребро существует между двумя любыми вершинами графа. Следовательно, этот граф – граф K₆, полный граф с шестью вершинами.

В рассмотренном выше примере, утверждалось, что если все ребра графа К₆ раскрашены либо красным, либо синим цветом, то в графе К₆ имеется ли­бо красный треугольник, либо синий треугольник, каждый из которых является подграфом графа K₆, по сути, просто графом К₃. Граф К₅ не обладает таким свойством, что если его ребра раскрашены либо красным, либо синим цветом, то он содержит красный или синий подграф К₃. Это доказывает граф, изображенный на рис. 8.13, где пунктиром изображены красные ребра, а сплошной линией – синие ребра. Теперь дадим определение свойства Рамсея для двух цветов на примере графов. Существует обобщение свойства Рамсея для произвольного числа цветов.

ОПРЕДЕЛЕНИЕ 8.85. Полный граф К_n обладает (р, q) свойством Рамсея, если в случае, когда он раскрашен двумя цветами, например, красным и синим, он содержит либо подграф К_р с красными ребрами, либо подграф K_q с синими ребрами.

18. Число Рамсея. Теорема Эрдоша и Шекереса о числе Рамсея. Число Рамсея, R(p,q) – это наименьшее число n такое, что граф К_n имеет (р, q) свойство Рамсея.

Вполне очевидно, что R(p,q) = R(q,p), поскольку можно заменить красный цвет на синий, а синий – на красный. Также, если т > R(p,q) = n, то, поскольку K_n – подграф графа К_т, граф К_т также обладает свойством Рамсея.

Относительно чисел Рамсея будут доказаны только две теоремы. Эти теоремы интересны сами по себе, но более важным является то, что они доказывают существование чисел Рамсея.

ТЕОРЕМА 8.87. Для всех р > 2 R(p, 2) = R(2,p) = p.

ДОКАЗАТЕЛЬСТВО. Рассмотрим граф К_р. Если одно ребро раскрашено красным (или синим) цветом, то существует красный (или синий) граф К₂. Если нет, тогда все ребра раскрашены синим (красным ) цветом, и мы получаем синий (красный) граф К_Р.

ТЕОРЕМА 8.88. (Эрдош и Шекерес) Для всех p,q > 3 R(p,q) < R(p – 1,q) + R(p,q – 1).

ДОКАЗАТЕЛЬСТВО. Предположим, что К – полный граф, имеющий R(p–l,q) + R(p,q – 1) вершин, ребра которого раскрашены в красный или синий цвет. Пусть v – выбранная вершина графа К. Пусть N – полный подграф графа К, вершины которого V_N связаны с вершиной v красным ребром. Пусть S – полный подграф графа К, вершины которого V_S связаны с вершиной v синим ребром. Поскольку V_N  V_S содержит R(p – 1,q)+R(p,q – 1) – 1 = R(p – 1,q)+R(p,q – 1) – 2 + 1 вершин, разделенных на n = 2 множества, то либо V_N имеет R(p – 1, q) вершин, либо V_S имеет R(p,q – 1) вершин. Поэтому, либо N – полный граф, имеющий R(p – 1,q) вершин, либо S – полный граф, имеющий R(p,q – 1) вершин. Если N – полный граф, имеющий R(p –1l,q) вершин, то он содержит либо подграф K_p–1 со всеми красными ребрами, либо подграф K_q со всеми синими ребрами. Если он содержит граф К_q со всеми синими ребрами, то доказательство завершено. Если он содержит граф K_p–1 со всеми красными ребрами, то, добавив вершину v и все красные ребра из v в вершины подграфа К_р–1, получим полный граф К_р со всеми красными ребрами, что и требовалось доказать.

Аналогично, если S – полный граф, имеющий R(p,q - 1) вершин, то он содержит либо подграф К_р со всеми красными ребрами, либо подграф K_q–1 сo всеми синими ребрами. Если он содержит граф К_р со всеми красными ребрами, то доказательство завершено. Если он содержит граф К_q–1 со всеми синими ребрами, то если добавить вершину v и все синие ребра из вершины v во все вершины подграфа K_q–1, получим полный граф K_q с синими ребрами, что и требовалось доказать.

Основываясь на результатах двух приведенных выше теорем и используя индукцию или принцип полного упорядочения для положительных целых чисел а также технику доказательства второй теоремы, можно доказать еще один результат, сформулированный в виде следующей теоремы

ТЕОРЕМА 8.89. (Рамсей). Если целые числа р и q больше единицы, то число Рамсея, R(p,q), существует.

19. Приложения комбинаторики к задачам теории вероятности в случае, когда не обязательно все исходы эксперимента равновозможны. Вероятность дополнения, суммы, попарно непересекающихся и пересекающихся событий. В предыдущем рассмотрении вероятности предполагалось, что все результаты эксперимента равновозможны. Теперь мы снимем это ограничение и дадим более общее понятие вероятности, для чего наш подход должен быть более аксиомати­ческим; при этом некоторые теоремы станут аксиомами и определениями.

ОПРЕДЕЛЕНИЕ 8.90. Вероятностной функцией на выборочном пространстве (множестве элементарных событий) S называется такая функция Р из подмно­жеств множества S на действительную числовую ось, что 1. Р(A) > 0 для всех A  S.

2. P(S) = 1.

3. Если А, В  S не имеют общих исходов, то Р(А  В) = Р(А) + Р(В). Доказательства приведенных ниже теорем аналогичны тем, которые даны в разделе 8.2. Единственное отличие состоит в том, что три сформулированных выше условия для вероятностной функции были доказаны в теореме 8.53 в предположении, что все исходы эксперимента равновозможны. Необходимо соблюдать осторожность при использовании такой комбинаторной техники, как подсчет числа сочетаний и перестановок, чтобы не допустить по умолчанию равновозможность исходов эксперимента.

ТЕОРЕМА 8.91. Пусть S – множество исходов, множество S также будет универсом. Пусть А' – дополнение множества А, тогда а) Р(А') = 1 – Р(А); б) Р() = 0; в) для любого события А имеем Р(А) > 0; г) если А  В, то Р(А) < Р(В); д) для любого события А имеем 0 < Р(А) < 1. Читателю предлагается доказать следующую теорему, используя принцип индукции.

ТЕОРЕМА 8.92. Пусть А₁, А₂, А₃,..., А_т – попарно непересекающиеся события. Тогда P(A₁  A₂  А₃  …  A_m) = Р(А₁) + Р(А₂) + Р(А₃) + … + Р(А_т). Доказательство следующей теоремы аналогично доказательству соответству­ющей теоремы 8.56.

ТЕОРЕМА 8.93. Для событий A,В  S имеем Р(АВ) – Р(А)+Р(В)–Р(АВ). Мы имели возможность убедиться, что для вероятности существует теоре­ма, аналогичная комбинаторному принципу сложения. Представляется разумным задать вопрос, существует ли для вероятности теорема, аналогичная комбина­торному принципу умножения. Так оно и есть, но сначала необходимо тщатель­но разобраться в формулировке комбинаторного принципа умножения. Принцип гласит: "Пусть задана последовательность событий Е₁,Е₂, Е₃,..., Е_т таких, что событие E₁ осуществляется n₁ способами, и если события Е₁,Е₂, Е₃,..., Е_k–1 осуществились, то событие E_k может осуществиться n_k способами. Тогда суще­ствуют n₁  n₂  n₃  …  n_k способов осуществления всей последовательности событий". Количество способов осуществления события Е_k зависит от того, про­изошли ли события Е₁,Е₂, Е₃,...,E_k-1. Таким образом, может оказаться, что число способов осуществления события E_k не реализуется само по себе и может зависеть от предыдущих событий.

Сходным образом дадим определение условной вероятности. Предположим, что имеются два события А и В. Требуется определить вероятность того, что событие В произойдет, если событие А произошло или наверняка произойдет. Сокращенно будем называть это вероятностью события В при условии А или относительно события А. Интуитивно понятно, что предположение о том, что событие А произошло или наверняка произойдет, ограничивает выборочное пространство до А, как показано на рис. 8.14, поэтому событие В ограничено теперь исходами из А  В, и вместо Р(В) = P(B)/P(S) , получаем P(AB)/P(A) .

ОПРЕДЕЛЕНИЕ 8.94. Вероятность В при условии А, обозначаемая Р(В|А), равна P(AB)/P(A) . Это можно также записать в виде Р(АВ) = Р(А)Р(В\А).

ОПРЕДЕЛЕНИЕ 8.98. Если Р(В) = Р(В|А), то событие В называется независи­мым от события А. Поскольку Р(АВ) = Р(А)Р(В|А), то для случая Р(В|А) = Р(В) получаем следующую теорему.

ТЕОРЕМА 8.99. Если событие В независимо от события А, то Р(АВ) = Р(А)Р(В).

ТЕОРЕМА 8.101. В эксперименте с n независимыми испытаниями, называемыми испытаниями Бернулли, где каждое имеет два исхода, успех с вероятностью р и неудачу с вероятностью q = 1 – р, вероятность осуществления k успехов равна p^kq^n–k.

Говорят, что такой эксперимент имеет биномиальное распределение по­скольку