Дискретно-непрерывная математика (стр. 39 )

Количество чисел, которые не превышают N и которые не делятся ни на одно из чисел а1,…,ап, равно

(5.37)

Пример 3. Пусть п — натуральное число, разложение которого на простые множители имеет вид

(р1,…,рk— простые числа), а φ(п) - число составленных натуральных чисел, которые не превышают п и взаимно простых с п. Доказать, что

(Функция φ(п) называется функцией Эйлера).

Числа, взаимно простые с п, не делятся ни на одно из чисел р1,…,рk. Поэтому в силу (5.37)

Рассмотрим теперь еще один способ применения метода включения и исключение.

Теорема. Пусть число элементов, входящих ровно в m множеств с А1, ..., Ап.

Тогда

(5.38)

Доказательство. Пусть а — произвольный элемент, который входит в k множеств из множеств А1, ..., Ап. Для доказательства теоремы достаточно показать, что элемент а учитывается в правой части равенства (5.38) один раз, если k = m, и не учитывается ни разу, если k ≠ m. Если k < m, то а не учитывается в сумме (5.38) ни разу; если k = m, то а учитывается в (5.38) один раз, так как а входит лишь в одно из множеств вида

Пусть теперь k > m. Элемент а учитывается Сmk раз в сумме

Сm+1k раз в сумме

и т. д. Сkk раз в сумме

В остальных суммах в правой части (5.38) элемент а не учитывается, так как он входит лишь в k множеств. Таким образом, а учитывается в (5.38),

(5.39)

раз. Остается доказать, что эта сумма равна нулю. Действительно, поскольку

это сумма (5.39) при k > m равно

5.12. Метод траекторий

Для многих комбинаторных задач можно указать такую геометрическую интерпретацию, которая сводит задачу к подсчету числа путей (траекторий), обладающих определенным свойством. В этом и составляется метод траекторий. В п. 5.3 мы пользовались методом траекторий при доказательства некоторых биномиальных тождеств. Преимуществом этого метода является чрезвычайная наглядность.

Задача 1. Возле кассы собралось m+п человек, причем п из них имеют монеты стоимостью 50 коп., а другие m имеют лишь по рублю. Сначала в кассе нет денег, билет стоит 50 коп. Сколько всего меется испособов размещения m + n покупателей в очереди так, чтобы ни один покупатель не ждал сдачи (m ≤ п)?

Допустим, что покупатели расположены в очереди некоторым образом. Пусть

Рассмотрим

Вдумчивый читатель уже заметил, что sk является разностью между количеством 50-копеечных монет и количеством рублей, которые поданы в кассу первыми k покупателями.

Рассмотрим теперь систему координат XOY. Построим в ней точки

Ak = (k; sk) (k=1, ..., т +п) и рассмотрим ламаную, которая соединяет точку О =(0; 0) с точкой Ап+т = (т + п; п — т) и которая проходит через точки A1,..., Ат+п-п. (рис. 5.8).

Рис. 5.8

Будем называть такую ламаную траекторией, соответствующей данному способу размещения покупателей в очереди. Каждая траектория состоит из т + n отрезков, п из которых направлены вверх, а т направлены вниз. Если указать номера тех отрезков, которые направлены вверх, то тем самым траектория будет полностью определена. Следовательно, общее число траекторий равно Сп+т.

Траектории, соответствующие тем способам размещения покупателей, при которых ни один покупатель не ждет сдачи, не пересекают прямую у =—1. Действительно, если для некоторого k sk-1 = 0, sk = —1, то это означает, что первые k—1 покупателей подали в кассу одинаковое количество полтинников и рублей, а k-й покупатель подал рубль и вынужден ожидать сдачу.

Определим число траекторий, которые пересекают прямую у=—1. Поставим в соответствие каждой траектории Т, что пересекает прямую у = — 1 или имеющей с ней общую точку, новую траекторию Т' по следующему правилу: до первой точки пересечения с прямой у=— 1 траектория Т' совпадает с Т, а далее Т' является симметричным отображением траектории Т относительно прямой у = — 1 (на рис. 4.8 траектория Т' обозначена пунктирной линией). Все траектории Т' заканчиваются в точке А'т+п =(т + п; т — п — 2), являющейся симметричным отображением точки Ат+п относительно прямой у= — 1. Установленное соответствие является взаимно однозначным, поэтому число траекторий, которые пересекают прямую у =—1, равно числу ламаных, которые соединяют точки О и А'т+п. Это число легко подсчитать: если ламаная состоит из у отрезков, направленных вниз, и х отрезков, направленных вверх, то

х + у=т+п, у - х = п + 2 - т,

откуда у = п+1. Таким образом, число траекторий, которые пересекают прямую у= —1, равно Сп+1т+п. Искомое число траекторий равно

(5.40)

Рассмотренная задача имеет важное значение в математической статистике, в частности в теории статистического контроля качества продукции. С ней также тесно связана так называемая задача о баллотировании, которую еще в 1887 г. рассматривал известный французский математик Бертран. Эта задача имеет интересные применения при изучении некоторых случайных процессов.

Задача 2. (Задача о баллотировании). Кандидат А собрал на выборах а голосов, кандидат В собрал b голосов (а>b). Избиратели голосовали последовательно. Сколько существует таких способов подачи голосов, при которых А всегда будет впереди В по количеству поданных за него голосов?

Пусть εi = +1, если i-й голос подан за А, и εi = = —1, если i-й голос подан за В. Возьмем sk = ε1+ ... + εk и рассмотрим в системе координат XOY ломаную, которая соединяет точки О, (l;s1),..., (k;sk), ..., (a + b;sa+b) (рис. 5.9).

Рис. 5.9

Очевидно, sa+b = a — b. Каждому способа подачи голосов соответствует определенная ломаная линия (траектория), соединяющая точки О и (а + b; а — b). Траектория состоит из а + b отрезков, причем а из них направлены вверх. Поэтому общее число траекторий равно Саа+b. Кандидат А всегда будет впереди В, если соответствующая траектория проходит через точку (1; 1) (первый голос должен быть подан за А) и не пересекает ось ОХ. Число таких траекторий может быть подсчитано по формуле (5.40), где следует взять п =a — 1, m = b. Следовательно, искомое число способов подачи голосов равно

(5.41)

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

Пусть х>0 и у— целые числа. Траекторией из начала координат в точку (х; у) будем называть ламаную, которая соединяет точки О,

(l; s1), ..., (k; sk), .., .... (х; sx), где

(5.42)

Пусть Nх, у - число всех траекторий, которые соединяют точку (0; 0) с точкой (х; у). Имеют место следующие теоремы.

Теорема 1,

если числа х и у - одинаковой четности, и

Nх, у=0,

если х и у — разной четности.

Доказательство. Предположим, что траектория состоит из р отрезков, направленных вверх, и q отрезков, направленных вниз (это означает, что среди чисел ε1 + ... + εх р чисел равны +1, a q чисел равны — 1). Тогда

p + q =х, p — q=y,

откуда

(поскольку р и q — целые числа, х и у должны быть числами одинаковой четности). Так как траектория полностью определяется, если указать, какие отрезки направлены вверх, общее число траекторий из точки О в точку (х; у) равно