авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 3 | 4 ||

«Учебник по математике Роман Добровенский heller 2012–2014, Москва Оглавление Введение ...»

-- [ Страница 5 ] --

Пример 3.14. Числами Ферма называются числа = 22 + 3.6 Принцип индукции Если записать первые числа Ферма 3, 5, 17, 257, 65537, то можно увидеть закономерность = + 2 (3.7) = Давайте докажем это по индукции. Как обычно предполо жим, что для формула верна для и докажем из этого её пра вильность для +1, переписав на этот раз правда выражение несколько в другой форме:

) = (1 2) = ( =0 = 2 1)(22 + 1) = 22·2 = ( + = 22 1 = +1 Что и требовалось доказать.

Числа Ферма имеют интересную историю. Ферма их придумал в 1640-ом году и выдвинул гипотезу, что все такие числа простые.

Действительно: они на вид похожи на простые. Однако в году Леонард Эйлер сумел разложить четвертое число Ферма на множители:

5 = 4294967297 = 641 · На это потребовалось почти сто лет! Интересно, что до сих пор не известно существует ли хоть одно простое число Ферма боль шее 4 — до сих пор все числа Ферма оказывались составными, однако исследована лишь малая доля таких чисел. Например, доказано, что число 20 не является простым, хотя сами его мно жители не известны — это уже слишком большое число, чтобы для него можно было найти хотя бы один делитель.

Тем не менее числа Ферма с простыми числами явно связаны.

Например, легко видеть из (3.7) и теоремы 3.14, что число не 3 Натуральные числа имеет общих множителей с числами при. Другими сло вами это значит, что все числа Ферма взаимопросты. Отсюда в частности следует, что простых чисел бесконечно много: если бы их было конечное число, мы не могли бы иметь бесконечную по следовательность взаимопростых чисел. Мы таким образом еще раз доказали теорему Евклида, но уже другим способом.

Напоследок рассмотрим два классических примера неправиль ного применения индукции.

Пример 3.15. Докажем, что все лошади одного цвета. Пусть — множество из лошадей, индукцию будем проводить по относительно уствержения «в любом множестве все лоша ди имеют одинаковый цвет». Для 1 утвержедение очевидно.

Предположим, что утверждение верно для при, и в этом предположении докажем верность утверждения для.

Разобьём множество на непустые непересекающиеся подмно жества {}, где — одна отдельно взятая лошадь. По предположению индукции во множествах {} все лошади имеют один цвет, то же самое касается множества {}. По скольку в оба последних множества входит один и тот же, то цвет лошадей в обоих множествах совпадает. Отсюда по индук ции следует, что для любого цвет лошадей в этом множестве будет одинаковым. Что и требовалось доказать.

Рассуждение, очевидно, ошибочно, но обычно в подобных до казательствах не сразу понятно в чем ошибка. Проблема кроется в том, что когда мы предположили верность утверждения для мы забили о том, что в том числе может быть равно двойке. В то же время никакое множество 2 невозможно раз бить на непустые непересекающиеся {}. Поэтому наше доказательство некорректно, хоть и поучительно: всегда надо держать в голове крайние случаи, так как они часто приводят к проблемам.

Упражнение 3.45. Докажем, что мы можем поднять любую гору песка. Будем проводить индукцию по количеству песчи нок. Очевидно, что мы можем поднять одну песчинку. Но если 3.7 Перестановки предположить, что мы можем поднять песчинок, то и + песчинку тоже поднять сможем, потому что каждая отдельная песчинка ничего почти не весит. А отсюда по индукции мы мо жем поднять вообще любое количетсво песчинок. Как считаете, почему это доказательство некорректно?

3.7 Перестановки Мы часто переставляем физические предметы местами: тасуем карты, перекладываем деньги в кошельке, сортируем данные в компьютере, ставим книги на полке, меняем жизненные прио ритеты. Эти действия отражены в математическом понятии пе рестановок, которым мы и займёмся. Чтобы не было путаницы, мы более не будем придерживаться аксиоматического задания натуральных чисел (если не оговорено обратное), и в этом и по следующих параграфах будем использовать обозначение [] для множества чисел от 1 до.

Определение 3.28. -элементной перестановкой называется биекция [] []. Множество всех -элементных перестановок будем обозначать как.

Перестановку удобно записывать в виде строки. Например:

= 35124 5. Эта запись означает, что на первой позиции оказался элемент, который раньше стоял на третьей позиции, вслед за ним идёт элемент, которые ранее стоял пятым и т.д.

Как и для любых функций, для перестановок можно рассмат ривать их композицию (в случае перестановок её часто называют умножением). Пусть, например, перестановка задана как вы ше и дана перестановка = 45231. В этом случае мы получаем = 21534. Для понимания этого примера важно помнить, что ( )() = (()), то есть для того, чтобы получить пози цию элемента, надо вначале применить перестановку, а затем только. Такой «обратный порядок» применения перестановок может показаться непривычным, но это стандартная форма за писи функций, как мы узнали во второй главе. Вот так например можно получить позицию единицы в искомой перестановке:

3 Натуральные числа ( )(1) = ((1)) = (5) = Хотя для композиции функций принято обозначение, для умножения перестановок мы будем опускать символ и писать просто.

Из того, что перестановка — это функция, сразу следует ассо циативность перемножения перестановок (см. §2.4): для любых,, мы имеем тождество () = () = Упражнение 3.46. Покажите, что умножение перестановок не коммутативно, то есть что в общем случае = Упражнение 3.47. Придумайте сами каких-нибудь перестано вок и поэкспериментируйте с ними.

Теорема 3.16. ()1 = 1 Доказательство.

()( 1 1 ) = ( 1 )1 = 1 = 1[] Если вам здесь что-то стало не очень понятно или сложно — перечитайте §2.4, все обозначения и термины являются непосред ственным отражением того, что обсуждалось когда мы говорили об обыкновенных функциях.

Подсчитаем мощность множества. На первую позицию мы можем поставить один из доступных нам элементов. На вторую позицию мы можем выбрать один из оставшихся 1 элементов (итого способов расставить первые два элемента ( 1)). Затем на третью позицию мы можем поставить один из 2 элемен тов (итого имеем ( 1)( 2) расстановок). Продолжая так до конца, на последнюю -ю позицию мы ставим один оставший ся элемент. Для формулировки полученного результата полезно следующее обозначение:

3.7 Перестановки Определение 3.29. Факториалом ! называется величина ( 1)( 2)... 2 · Так же считаем, что 0! = 1.

Значение для 0! оправдано с той точки зрения, что на пустом множестве формально можно задать единственную функцию, которая так же будет биекцией (хоть она ничего и не отобра жает, формально она есть;

см. аналогию с 0 в §1).

Рассуждения, приведенные выше, теперь можно сформулиро вать таким образом:

Теорема 3.17. | | = !

Упражнение 3.48. Докажите, что при разложении на простые множители значения !, множитель встретится ровно = раз, где как обычно через обозначается целая часть от деле ния на.

Помимо представления перестановки в виде строки, их удобно рассматривать в виде циклов. Рассмотрим опять перестановку = 45231. Мы видим, что при этой перестановке 1 переходит на позицию 5, 5 переходит на позицию 2, 2 на позицию 3, 3 на 4, которая переходит опять на позицию 1. Эти переходы записы ваются строкой чисел в круглых скобках: = (15234). Здесь за каждым числом следует число (). Последнее значение пере ходит на позицию, обозначенную первым числом, что замыкает цикл.

Рассмотрим теперь перестановку = 35124. Здесь (1) = 3 и (3) = 1, что даёт цикл (13). Сюда, однако, вошли не все эле менты множества. Рассмотрим оставшиеся элементы: (2) = 4, (4) = 5, (5) = 2, что даёт цикл (245). Итого перестановка представляется в виде произведения двух циклов: = (13)(245).

3 Натуральные числа Количество элементов в цикле мы будем называть его длиной.

Если какой-то элемент отображается сам в себя (то есть () = ), то мы будем говорить, что перестановка имеет цикл длины ().

Упражнение 3.49. Пусть — некоторая перестановка и (... ) — некоторый цикл. Докажите, что (... ) 1 = (... ) (Подсказка: рассмотрите как эта перестановка действует на эле мент ).

Определение 3.30. Типом перестановки называется набор (1, 2,..., ) где — количество циклов длины заданной перестановки.

Определение 3.31. Циклической перестановкой [] называет ся перестановка типа (0, 0,..., 0, 1), то есть перестановка, состо ящая из единственного цикла, сдвигающего все элементы.

Пример 3.16. Типом перестановки, используемой выше, бу дет (0, 1, 1, 0, 0), типом перестановки — (0, 0, 0, 0, 1). Тривиаль ная перестановка 1[], которая оставляет все элементы на месте, имеет тип (, 0, 0, 0, 0), то есть она состоит из циклов вида ().

Упражнение 3.50. Покажите, что для любого типа (1, 2,..., ) всегда выполнено соотношение = = Теорема 3.18. Существует !

1 !2 !... !11 22...

перестановок типа (1, 2,..., ) 3.7 Перестановки Доказательство. В качестве рабочего примера будем считать, что мы ищем все перестановки типа (1, 2, 1, 0, 0, 0, 0, 0) множества [8].

Вначале выпишем произвольную строку чисел, являющуюся перестановкой [] (например, 18356724), способов сделать это !.

Расставим теперь в этой записи круглые скобки по очереди: вна чале 1 скобок с одним элементом внутри, затем 2 скобок с дву мя элементами внутри, потом 3 с тремя элементами внутри и так далее. Для нашего примера получится запись (1)(83)(56)(724) Таким образом мы получаем одну из возможных перестановок требуемого типа. Однако, не только первоначально выписанная перестановка даёт нам такое циклическое представление. Во первых, если мы поменяем местами любые два цикла длины, то мы получим отличное представление той же самой перестанов ки. Например, мы можем поменять местами две перестановки длины 2:

(1)(56)(83)(724) Это ровно та же самая перестановка, но получающаяся из дру гой строки. Таким образом, поскольку у нас имеется циклов длины, нам необходимо поделить общее количество первона чальных перестановок на !.

Во-вторых, каждая из перестановок может быть циклически сдвинута на k элементов. Например, мы так могли бы сдвинуть наш пример, получив тот же результат:

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

Следствие 3. Существует ( 1)! циклических перестановок множества [].

3 Натуральные числа Доказательство. В качестве упражнения.

Упражнение 3.51. Порядком перестановки || называется та кое число, что = 1[] (то есть под () = подразумева ется -кратное применение перестановки ). Докажите, что для перестановки типа (1,..., ) выполняется соотношение || = lcm{ } Определение 3.32. Транспозицией называется перестановка типа ( 2, 1, 0,..., 0), то есть это перестановка, меняющая ме стами лишь два элемента.

Упражнение 3.52. Докажите, что любая перестановка может быть представлена композицией транспозиций.

Ясно, что представление в виде транспозиций неоднозначно, причём может отличаться даже количество транспозиций, ис пользуемых для представления перестановки, например:

(13)(34) = (23)(14)(24)(23) Интересно, однако, что количество транспозиций для любой заданной перестановки всегда либо чётное, либо нечётное. Это не совсем очевидно и требует доказательства, которое предсталено следующим определением с прилагающимися упражнениями.

Определение 3.33. Инверсией перестановки называется такая пара, что () ().

Инверсии — это такие пары элементов, которые при примене нии перестановки меняют свой относительный порядок. Напри мер, для перестановки 35124 имеется 5 инверсий: 3 и 1, 3 и 2, и 1, 5 и 2, 5 и 4. Инверсии имеют важное значение при анализе быстродействия компьютерных алгоритмов, однако нас само ко личество инверсий интересовать не будет, нас будет интересовать лишь то, чётное это количество или нет.

3.7 Перестановки Определение 3.34. Перестановка называется чётной (нечёт­ ной), если она имеет чётное (соответственно нечётное) число инверсий.

Упражнение 3.53. Докажите, что любая транспозиция — это нечётная перестановка.

Упражнение 3.54. Докажите, что произведение чётных пере становок даёт чётную перестановку, произведение нечётных — тоже чётную, а произведениче чётной и нечётной перестанов ки — нечётную перестановку.

Тривиальная перестановка, которая оставляет все элементы на месте, чётная. Если умножить её на транспозицию — получа ем нечётную перестановку. Умножная её на транспозицию ещё раз — опять получаем чётную перестановку. Поскольку любая перестановка однозначно либо чётная либо нечётная, то, рассуж дая по индукции, приходим к ожидаемому: любая перестановка всегда представлена в виде транспозиций либо чётным их чис лом, либо нечётным.

Упражнение 3.55. Докажите, что для любого 1 количе ство чётных и нечётных перестановок на [] одинаково.

Пока мы рассмотрели понятие чётности перестановок лишь в качестве упражнения, но довольно скоро вы увидите, что оно играет весьма важную теоретическую роль.

Упражнение 3.56. Докажите, что любая чётная перестановка может быть представлена в виде произведения циклов длины 3.

Упражнение 3.57. Докажите, что с помощью перестановок (12) и (12... ) возможно представить любую перестановку мно жетва [].

Определение 3.35. Беззнаковым числом Стирлинга первого рода называется количество перестановок множества [], со [ ] держащих ровно циклов.

3 Натуральные числа Слово «беззнаковый» мы будем опускать, поскольку пока оно не имеет для нас никакого смысла (он проявится позже). Прямо из определения следует такое простое соотношение:

Теорема 3.19.

[] = !

= Доказательство. В качестве упражнения.

Выше мы уже фактически доказали, что = ( 1)!. Так [ ] [] же очевидно, что = 1. Для вычисления остальных значений поможет следующая рекурсивная формула.

Теорема 3.20.

[ ] [ ] [ ] 1 + ( 1) = Доказательство. Рассмотрим какой-нибудь один отдельно взя тый элемент множества []. Под действием перестановки с циклами может либо оставаться на месте, либо куда-то [ пере двигаться. Перестановок, когда остаётся на месте, ровно ] штук. Если же куда-то передвигается, то мы можем рассмот реть перестановку множества [ 1] с 1 циклами: в эту пере становку, записанную в виде циклов, достаточно лишь вставить элемент после какого-нибудь другого элемента. Всего нам до ступно 1 позиций для вставки.

По этой формуле с помощью компьютера можно сравнитель но легко находить числа Стирлинга. Конечно, сами по себе они мало интересны и вряд ли вам придётся когда-либо их вычис лять. Интреснее то, как они сочетаются с другими объектами математики, к чему мы вернёмся в последующих главах нашей книги.

Упражнение 3.58. Посадил злой вертухай сотню гномиков в тюрьму, каждого пронумеровал и поставил условия:

3.8 Сочетания — Завтра каждый из вас по одному будет заходить в специаль ную камеру, где будет лежать сотня пронумерованных конвер тов. В каждом конверте — какой-то номер (просто все цифры от одного до ста, разложенные по конвертам случайным образом).

Каждый из вас будет иметь право открыть ровно 50 конвертов, чтобы найти свой номер. Если все вы найдете свои номера — освобожу. Если хотя бы один ошибется — казню всех.

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

Гномикам надо придумать стратегию как искать свой номер, чтобы найти. Если открыть просто наугад 50 из 100 конвертов, то вероятность найти свой номер весьма мала (пополам на по полам). Учитывая, что гномиков сто штук, то их общие шансы при случайной стратегии оказываются вообще ничтожны. На до поэтому придумать какую-то альтернативную стратегию. (По хорошему в этой задаче еще надо проанализировать в конце по лученное решение, но этого пока я от читателя не требую, по скольку я не рассказывал методов, которые позволяют это де лать;

впрочем, вы можете попытаться дать грубые оценки).

3.8 Сочетания «-сочетание» — это просто другое название для термина « элементное подмножество», которое по историческим причинам (хотя многие считают, что так удобнее) принято в комбинато рике. Нас будет интересовать количество -сочетаний взятых из множества [].

Определение 3.36. Биномиальным коэффициентом назы ( ) вается число сочетаний из [] по.

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

Значения = и = 1 очевидны. Так же удобно полагать, ( ) ( ) 1 () что 0 = 1 (пустое множество всего одно, соответственно есть лишь один способ его выбрать).

Упражнение 3.59. На листочке в клетку начерчен прямоуголь ник со сторонами и. Мы двигаемся из левого нижнего угла прямоугольника в правый верхний, сдвигаясь за шаг либо на одну клетку вверх, либо на одну клетку вправо. Сколько всего существует таких путей? Сведите задачу к вычислению количе ства сочетаний, как их считать я расскажу ниже.

Упражнение 3.60. Будем считать, что в условиях прошлой задачи =. Сколько существует путей из левого нижнего уг ла в правый верхний таких, что они не пересекают диагонали квадрата? (Подсказка: возьмите путь, пересекающий диагональ, и отразите его начало до пересечения относительно этой диаго нали).

Теорема 3.21.

() = = Доказательство. В левой части этого выражения строит общее количество всех подмножеств множества []. В правой части на самом деле написано то же самое: 2 есть мощность булеана, как вы видели в § 3.1.

Теорема 3.22. ( ) ( ) = Доказательство. Выбрать элементов из множества [] это всё равно что выбрать элементов, которые мы оставим в мно жестве.

3.8 Сочетания Теорема 3.23.

( ) ( ) ( ) 1 = + Доказательство. Рассмотрим все -сочетания из множества [].

Сам элемент может либо принадлежать выбранному подмно жеству, либо не принадлежать. В первом случае количество со четаний будет равно 1, во втором случае, поскольку один ( ) элемент сочетания уже фиксирован, это будет величина 1.

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

Определение 3.37. -размещением мы назовём некоторый упо рядоченный набор, состоящий из некоторых элементов множе ства []. Количество размещений из по будем обозначать как.

Теорема 3.24.

!

= ( )!

Доказательство. Доказательство практически дублирует дока зательство для количества перестановок. На первую позицию мы можем поставить один из элементов. На вторую позицию один из оставшихся 1 элементов. На третью —один из 2 эле ментов. Однако в отличии от перестановок, теперь нам надо раз местить лишь элементов, а не все, поэтому мы этот процесс оборвём на -том шаге. В итоге получаем выражение = ( 1)( 2)... ( + 1) Если это выражение умножить и разделить на ( )!, получим утверждение теоремы.

3 Натуральные числа Само обозначение на самом деле почти всегда использу ется просто для обозначения произведения подряд убывающих чисел. Эту величину часто называют убывающим факториалом.

В полной аналогии вводится и возрастающий факториал:

= ( + 1)( + 2)... ( + 1) Упражнение 3.61. Покажите, что = ( + 1) Теорема 3.25. ( ) !

= !( )!

Доказательство. -расстановку мы можем получить, вначале выбрав -элементное подмножество [], а затем упорядочив его.

Всего существует способов выбрать такое подмножество. Спо ( ) собов упорядочить выбранное — !. Таким образом получаем со отношение ( ) = !

Поделив обе части на ! и подставив выражение для, полу чаем утверждение теоремы.

Упражнение 3.62. Теоремы 3.22 и 3.23 можно доказать, поль зуясь явным представлением биномиального коэффициента, по лученным в 3.25. Сделайте это.

Упражнение 3.63. Чему равно ( ) = Упражнение 3.64. Докажите, что ( )( ) ( )( ) = 3.8 Сочетания Упражнение 3.65. Докажите, что ( )( ) ( )( ) 1 + 1 Теорема 3.26.

() ( + ) = = Доказательство. Давайте вначале для наглядности распишем степень подробно:

( + )( + )... ( + ) Раскроем все скобки (если пока не понятно как, то потренируй тесь на каких-то частных случаях типа = 3). Раскрытие скобок можно интерпретировать так, что из каждой скобки мы выби раем либо, либо. Все слагаемые в полученной сумме будут иметь вид, + = с каким-то коэффициентом, появляю щимся за счёт того, что некоторые слагаемые вида появля ются несколько раз.

Слагаемое появится лишь один раз в случае, если из всех скобок мы выберем. Слагаемое 1 появляется, если мы вы бираем из всех скобок, кроме одной. Эту одну скобку, из кото рой мы выбираем, мы можем выбрать одним из способов. По аналогии 2 2 появится раз, поскольку мы выбираем уже ( ) две скобки, из которых мы возьмём. Продолжая по аналогии приходим к утверждению теоремы.

Упражнение 3.66. Приведённую теорему можно доказать по индукции. Будет полезным проделать это самостоятельно.

Приведённая теорема даёт нам ещё один способ подсчитать количество подмножеств множества []:

() () 1 1 = (1 + 1) = = =0 = 3 Натуральные числа Упражнение 3.67. Докажите равенство ( ) 3 = = Последняя задача в свете теоремы 3.26 решается элементарно, однако я замечу, что такие задачи часто даются на олимпиадах для тех школьников, которые ещё по возрасту не могут знать таких теорем. Предполагается, что школьники могут доказать утверждение по индукции (и некоторые действительно могут).

Это одна из причин по которой автор ненавидит олимпиадные задачки и «задачки на логику», которые часто дают на собесе дованиях — большинство таких задач изначально появляются как тривиальные следствия каких-то более общих результатов, а потом уже задним числом оказывается, что задачу в общем-то можно было бы решить и пользуясь лишь школьной математи кой. Однако если сравнивать пользу от решения такой задачи по индукции с пользой от изучения общей теоремы, то послед нее явно выигрывает, хотя и не помогает на собеседованиях и олимпиадах.

Сочетания часто используются так же вот в каком ключе.

Предположим, мама нам сказала: «Пойди в магазин и купи каких-нибудь пирожков». Мы приходим в магазин, а там про даётся наименований пирожков. Сколько всего способов у нас есть удовлетворить мамин запрос? Задача в такой постановке приводит нас к понятию сочетаний с повторениями, поскольку искомые наборы могут содержать повторяющиеся элементы.

Для решения задачи предположим, что пирожки разного ви да мы разложили по разным пакетам (я видел, что в ларьках у метро именно так часто и делают). Схематически мы будем раз делять пакеты вертикальной чертой |, а пирожки (или, более об що, элементы множества), кружочками. Для примера давайте считать, что у нас всего имеется = 5 видов пирожков, а купили мы = 6 пирожков, причём из них было два пирожка первого вида, три третьего и один четвёртого. Остальных пирожков мы 3.9 Разбиения множеств не покупали. На схеме это будет выглядеть как | || | || Теперь мы можем догадаться, как подсчитать общее количество различных сочетаний с повторениями: достаточно просто под считать общее количество возможных схем такого вида. В схе ме, приведённой выше, если отбросить крайние чёрточки |, по лучится + 1 различных позиций, на которых могут стоять чёрточки либо кружки. Причём мы точно знаем, что кружков всего будет штук, а чёрточек 1. Чтобы получить какую-то конкретную схему, нам надо выбрать позиций под кружки, а остальные позиции мы занимаем чёрточками. Итого для коли чества сочетаний с повторениями мы имеем выражение ( ) ( ) + 1 + = Упражнение 3.68. Докажите, что существует 21 способов представить число в виде суммы ненулевых слагаемых. Зада ча довольно сложная, поэтому дам некоторые наводки. Внача ле следует разобрать случай, когда имеется ровно слагаемых.

Подход здесь может быть аналогичным задаче с булочками вы ше, но надо учитывать то, что чтобы слагаемые были ненуле выми, мы не можем поставить подряд две черты, не поставив между ними кружок. Способов сделать это 1 (докажите!).

( ) Отсюда уже довольно легко выводится и результат первоначаль ной задачи.

3.9 Разбиения множеств Когда мы выбираем из элементов элементов, мы на самом деле разбиваем множество на 2 части: ту, которую мы выбра ли (она содержит элементов), и ту, которую оставили ( элементов). Эту идею можно обобщить: можно выбирать элемен ты множества не в два подмножества, а в произвольное число 3 Натуральные числа подмножеств, где в -е подмножество попадает элементов. При этом должно выполняться соотношение 1 + 2 +... + =.

Эта идея чуть более формально отражена в следующих опреде лениях.

Определение 3.38. Упорядоченным разбиением множества [] на подмножеств называется отображение : [] []. Мы го ворим, что упорядоченное разбиение имеет тип (1, 2,..., ), если | 1 ()| =.

Определение 3.39. Число упорядоченных разбиений множе ства [] типа (1, 2,... ) называется мультиномиальным ко­ эффициентом и обозначается как ( ) 1 ;

2 ;

... ;

Упражнение 3.69. Сколько можно получить различных слов путём перестановки букв в слове «математика»? Если теперь взять произвольно слово, то сколько слов можно получить раз личными перестановками?

Теорема 3.27.

( ) !

= 1 ;

2 ;

... ;

1 !2 !... !

Доказательство. Выберем вначале 1 элемент, способов сделать ( ) это 1. Из оставшихся элементов теперь выберем во второе мно жество 2 элементов, способов сделать это 1. Продолжая ( ) рассуждать таким же образом, получаем ( ) ( )( )( ) ( ) 1 1 2 1... =...

1 ;

2 ;

... ;

1 2 3 ( 1 )! ( 1 2 )!

!

· · ·.

= 1 !( 1 )! 2 !( 1 2 )! 3 !( 1 2 3 )!

!

= 1 !2 !... !

3.9 Разбиения множеств Теорема 3.28.

( ) 1 2...

(1 + 2... ) = 1 ;

2 ;

... ;

1 1 +...+ = Здесь суммирование ведётся по всем возможным наборам чисел { }, дающим в сумме.

Доказательство. Аналогично доказательству теоремы 3.26. Про ведите его самостоятельно.

Упражнение 3.70. Покажите, что теорема 3.26 является част ным случаем для теоремы 3.29.

Упражнение 3.71. Покажите, что в теореме 3.29 будет ровно (+1) слагаемых.

Определение 3.40. Числами Стирлинга второго рода на { } зывается количество способов разбить множество [] на под множеств.

Я обращу внимание на то, что в определении чисел Стирлин га второго рода речь идёт уже о неупорядоченных разбиениях.

Например, если рассматривать множество {,,, }, то с точки зрения чисел Стирлинга разбиения ({, }, {, }) и ({, }, {, }) будут эквивалентны, а с точки зрения мультиномиального коэф фициента — нет.


Упражнение 3.72. Докажите, что 4 = 8, но в то же время { } ( ) = ;

(4 ) = {} Упражнение 3.73. Выразите через мультиномиальные ко эффициенты.

Определение 3.41. Числами Белла () называется количе ство способов разбить множество [] на подмножества.

3 Натуральные числа Речь опять же идёт о неупорядочнных разбиениях.

Теорема 3.29.

{} () = = Доказательство. Очевидно.

{} = 21 1.

Упражнение 3.74. Докажите, что Значения = = 1 настолько очевидны, что даже не за { } { } 1 служивают отдельного упражнения. Остальные значения, как и в случае чисел Стирлинга первого рода и количества сочетаний, могут быть вычислены рекурсивно.

Теорема 3.30.

{ } { } { } 1 = + Доказательство. Рассмотрим элемент множества []. При раз биении [] на подмножества может войти в отдельное подмно жество мощности 1, либо же войти в состав более крупного под множества. В первом случае количество таких разбиений будет {1} 1 — количество разбиений без учёта элемента. Во втором случае мы опять же строим разбиение множества [ 1], но уже на подмножеств. Нам остаётся лишь выбрать { какое из этих в } подмножеств добавить элемент. Получаем 1.

Числа Белла так же допускают рекурсивное определение, хотя и не особо удобное.

Теорема 3.31.

() ( + 1) = () = 3.10 Включения-исключения Доказательство. Пусть элемент + 1 при некотором разбие ( ) нии множества [ + 1] попал в множество размера. Есть способов выбрать это множество, оставшиеся элементы можно разбить на подмножества ( + 1 ) способами. Поскольку может быть произвольным от 1 до + 1, получаем +1 ( ) ( + 1 ) ( + 1) = = +1 ( ) ( + 1) = + = () = () = Чтобы эта формула работала, нужно положить (0) = 1 (что бы увидеть это, примените 3.32 к значению (1)), что соответ ствует интуиции: существует лишь одно разбиение пустого мно жества на подмножества, которое само является пустым множе ством.

Упражнение 3.75. Докажите, что для 2 выполняется оценка { } ! (2)!

Вероятно, вначале будет целесообразно, пользуясь 3.31, дока зать, что () ! при 3.

3.10 Включения-исключения Вот задачка, которая как-то попалась мне в младшем возрасте на олимпиаде по математике, а затем многократно попадалась в разных книжках с занимательными примерами по математике.

3 Натуральные числа Есть класс, в котором известно, что все ученики ходят в какие то секции. Известно, что 12 учеников ходят на плавание (и, воз можно на что-то ещё), 13 на карате, 12 на шахматы, 6 одновре менно на плавание и на карате, 6 на карате и шахматы, 2 на шахматы и плавание и 2 ходят во все три секции. Сколько всего учится детей в классе?

Мы не будем решать эту задачу, а сразу перейдём к общему случаю. Пусть у нас есть семейство множеств { }, нам известны мощности каждого из них, а так же мощности любых их пересе чений. Необходимо найти мощность объединения этих множеств.

Напомню, что в § 3.1 мы ввели понятие характеристической функции (). Эта функция принимает значение 0, если и 1, если. Нам потребуются дополнительные факты о ней:

1. Пусть, тогда || = Теорема 3.32. () 2. () = 1 () 3. () = () () Доказательство. В качестве упражнения.

Теорема 3.33.

| | | | + | |...

= =1 =1 Здесь суммирование справа ведётся по всем таким наборам (, ) таким, что, затем по наборам (,, ), таким что и так далее.

Доказательство. Утверждение на самом деле следует непосред ственно из теоремы 3.32. В выкладках ниже я не указываю пре 3.10 Включения-исключения делы суммирования, т.к. они и так очевидны:

() = ( ) () = 1 ( ) () = 1 () =1 () =1 (1 ()) () = () () +...

=1 () = () +...

=1 В предпоследней строке мы просто раскрыли скобки. Применяя к полученному пункт 1 теоремы 3.32, получаем утверждение тео ремы.

Теорема легко выводится, но пока, вероятно, не очень понятна по смыслу. Давайте посмотрим на случаи нескольких множеств.

Пусть нам надо подсчитать ||. Мы могли бы просто сложить их мощности ||+||, однако в этом случае получится, что часть будет учтена в этом выражении дважды — один раз от || и один раз от ||, значит из полученного нам надо вычесть ||, в результате чего получаем | | = || + || | | (3.8) Можно было бы увидеть это и по-другому. Множества =, = и = не пересекаются, причём =, =, =. Т.к., и не пересекаются, мы можем записать | | = | | = || + | | + || Но поскольку || = || + | |, || = | | + || и | | = | |, мы опять получаем (3.8).

3 Натуральные числа Перейдём к случаю трёх множеств. Опять же простая сумма || + || + || будет дважды учитывать попарные пересечения множеств и трижды — тройное пересечение. Чтобы ис править ситуацию, нам надо вычесть все попарные пересечения, однако этого тоже недостаточно — вычтя три попарных пересе чения мы в том числе три раза вычтем тройное пересечение, а это значит, что оно теперь остаётся вообще не учтено. Его надо прибавить. Получаем | | = || + || + || | | | | | | + | | Собственно утверждение теоремы 3.33 можно было бы полу чить и по индукции, рассуждая таким образом, однако такой путь явно сложнее.

Для пересечения множеств можно получить результат, анало гичный 3.33.

Теорема 3.34. Пусть, тогда | | + | |...

= | | =1 =1 Доказательство. Утверждение следует непосредственно из тож дества | | = |( ) | = | | | | Применяя теперь теорему 3.33 получаем желаемый результат.

Помимо простых задачек для школьников, конечно же, это всё имеет применения и к чистой математике. Давайте приведём примеры.


Определение 3.42. Функцией Эйлера () называется количе ство чисел, меньших и взаимопростых с ним (исключая ноль, включая единицу).

3.10 Включения-исключения — разложение на про­ Теорема 3.35. Пусть = = стые множители. Тогда () = + +...

=1 Доказательство. Будем рассматривать в качестве универсума (то есть множества, относительно которого мы берём дополне ния) множество чисел от 1 до 1. Определим как множество чисел, делящихся на и меньших. Его дополнение — это в точности числа, меньшие, которые не делятся на. Соот ветственно числа, взаимопростые с — это пересечение, то есть это все числа, которые не делятся ни на один из делителей числа. Заметим, что | | =. Так же в силу того, что все { } взаимопросты, | | = (в это пересечение попадают только числа, кратные ). Аналогичные утверждения можно получить для любых пересечений множеств { }. Отсюда сразу же по теореме 3.34 вытекает требуемое утверждение.

Упражнение 3.76. Беспорядком называется такая перестанов ка, которая не оставляет на месте ни один элемент множества, то есть такая, что () =. Сколько беспорядков возможно задать на множестве []?

Теорема 3.36. Существует в точности ( ) ( ) ( 2)...

( 1) + 1 сюръекций вида [] [] (напомню, что это функции такие, что для каждого [] существует такой что () = ).

Доказательство. Пусть множество — это множество таких отображений : [] [], что прообраз элемента не пуст (то есть существует такое, что () = ). Множество сюръекций — это в точности множество. Чтобы применить теорему 3. 3 Натуральные числа нам необходимо найти мощность всех возможных пересечений множеств семейства { }. Однако, это легко: если [], то = ( ||) поскольку это в точности множество отображений [] ([]).

Причём это выражение зависит только от количества множеств в пересечении ||, а не от самих множеств, которые пересекаются.

( ) Отсюда получаем, что для каждого = || мы будем иметь слагаемых ( ).

Упражнение 3.77. Предположим, что компьютер запрограм мирован выполнить задач типа, всего есть типов задач.

Компьютер выполняет задачи последовательно, но ему надо так распланировать свою работу, чтобы все задачи одного вида не выполнялись последовательно, он обязательно должен задачи чередовать (то есть он не может выполнить подряд задач типа ). Сколько всего способов существует для компьютера распла нировать свою работу?

3.11 Двойной счёт Напомню, что в графе степенью вершины deg() мы назвали количество рёбер, ей инцидентных.

Теорема 3.37. Пусть — множество вершин некоторого гра­ фа, — количество его рёбер. Тогда deg() = Доказательство. Мы можем пересчитать все рёбра графа дву мя способами: собственно, пересчитывая сами рёбра (получим в этом случае ), либо же пересчитывая вершины и складывая сте пени deg. В этом случае, правда, получится, что каждое ребро мы учтём два раза, поскольку каждое ребро инцидентно ровно двум вершинам.

3.11 Двойной счёт Это элементарное доказательство является простейшим при мером доказательства методом двойного счёта. Приём этот вы глядит всегда одинаково: мы берём некоторый набор объектов и считаем его двумя разными способами, получая в итоге одно и то же значение, но записанное в разном виде. По большому счёту рекурсивные формулы для вычисления числа сочетаний, чисел Белла и чисел Стирлинга, а так же формулы их сумм, до казывались нами именно методом двойного счёта, только мы не произносили этого слова. Остаток этого параграфа мы посвятим разбору ещё нескольких подобных примеров.

Теорема 3.38.

()( ) ( + ) = = Доказательство. Пусть у нас имеется мужчин и женщин.

Нам надо выбрать из них группу человек. Очевидно, что это можно сделать + способами. С другой стороны, мы можем ( ) отдельно рассмотреть все варианты, когда мы выбираем муж чин и женщин, что даёт нам левую часть.

Следствие 4.

()2 ( ) = = Доказательство. Достаточно положить = = и заметить, что =.

( ) ( ) Теорема 3.39.

()( ) ( ) = = Доказательство. Левую часть можно интерпретировать как ко личество способов выбрать различные подмножества [] с по крайней мере элементами, и затем в этих множествах выде лить ещё некоторые элементов. Правая часть даёт ровно ту 3 Натуральные числа же самую величину, но в этом случае мы вначале выбираем помеченных элементов из [], а затем добавляем к полученному набору один из 2 подмножеств, составленных из оставшихся элементов.

Теорема 3.40.

{ } ( ) ( ) = ( 1) + ( 2)...

!

1 Доказательство. Справа, как мы увидели в конце прошлого па раграфа, перечислено количество сюръекций [] []. Одна ко, их можно перечислить и по-другому. Пусть — некоторая сюръекция, тогда прообразы 1 (1), 1 (2),... не пусты и зада ют некоторое разбиение множества [] на подмножеств. Таких разбиений существует штук. В то же время если — неко { } торая перестановка на [], то так же задаёт то же самое разбиение множества [], хотя сюръекция уже будет другой. По скольку мы имеем ! таких перестановок [], общее}количество сюръекций может быть так же определено как !.

{ Определение 3.43. Граф называется связным, если в нём су ществует путь между любыми двумя вершинами.

Определение 3.44. Деревом называется связный граф без цик лов.

Деревья часто применяются в компьютерных системных по иска. Самый распространённый вариант — это двоичные дере вья поиска, которые представляют собой следующую структуру:

каждая вершина дерева обладает некоторым значением и, воз можно, тремя гранями, называемых ветвями. Одна ветвь ведёт в направлении корня, другая ветвь, называемая левой, ведёт ко всем вершинам со значениями, меньшими чем текущее, а вто рая ветвь, называемая правой, ведёт к большим значениям. Если предположить, что значения — это строки, то их порядок может восприниматься как алфавитный. Пример такого бинарного де рева поиска представлен на рисунке 3.11.

3.11 Двойной счёт Николай Евгения Роман Авдотья Жанна Ольга Света Рис. 3.11. Бинарное дерево поиска Предположим, что в дереве на рисунке 3.11 так же в каждом узле дерева записан телефон, и что мы захотели найти теле фон Ольги. Если бы мы просматривали все телефоны подряд, то в случае их упорядоченности по алфавиту, прежде чем мы наткнулись бы на Олин телефон, нам пришлось бы проверить шесть записей. Однако, вместо этого мы могли бы искать теле фон в дереве, двигаясь от корня: вначале мы увидели бы, что имя Ольга должно идти после имени Николай, что значит, что мы должны искать по правой ветви от корня, где мы встречаем имя Роман. Ольга идёт раньше Романа по алфавиту, поэтому мы продолжаем искать её в левой ветви, где и находим её телефон.

Итого нам потребовалось три шага поиска: вдвое быстрее чем при последовательном переборе.

Упражнение 3.78. Пусть мы ищем телефон Фиофанта. Пока жите, что при последовательном поиске нам потребовалось бы шагов, чтобы убедиться, что такого телефона нет, а при поиске в дереве всего 3 шага.

Упражнение 3.79. Пусть у нас теперь имеется дерево, в ко тором записано 2147483647 телефонных номеров. Например, это может база данных ФСБ или ещё какая. Покажите, что исполь зуя бинарное дерево поиска, мы можем найти любой телефон (или убедиться, что его нет в базе) максимум за 31 шаг.

3 Натуральные числа Последнее упражнение показывает, что использование дере вьев может здорово упростить поиск информации (зачастую уско рение получается в миллионы раз). Собственно очень похожим образом устроены почти все базы данных, и без деревьев не было бы ни компании Гугл, ни, наверное, вообще компьютерной тех ники в современном её виде. Чтобы уметь анализировать ско рость работы алгоритмов, нам прежде всего необходимо уметь пересчитывать все деревья.

Бинарные деревья — это в общем-то частный случай дерева.

Как перечислить все возможные деревья поиска мы поймём поз же в нашем курсе (мы изучим общие подходы), а пока что же мы перечислим просто все возможные деревья с вершинами.

При изучении следующего доказательства важно иметь ввиду следующие уточнения постановки задачи, которые мы подразу меваем:

1. Дерево не обладает корнем;

все вершины равнозначны;

2. Вершины деревьев имеют определённые метки (данные), то есть даже если два дерева имеют одинаковую форму внешне, но вершины имеют разные именования, мы рас сматриваем эти деревья как различные;

3. Каждая вершина может иметь произвольное количество инцидентных рёбер.

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

1 2 3 4 () 4 1 1 2 Таблица 3.2. Пример функции Теорема 3.41. Существует 2 деревьев с вершинами.

3.11 Двойной счёт Доказательство. Подсчитаем количество функций : [] [] двумя способами. С одной стороны количество таких функций, это тривиальная теорема, рассмотренная нами в § 3.1. По пробуем теперь подсчитать количество функций, сопоставив каждой функции некоторое дерево. Это довольно сложное рас суждение, поэтому будем рассматривать его на примере функ ции, значения которой заданы в таблице 3.2. Пусть = { []| () = } то есть это множество таких элементов из [], что применяя к ним последовательно несколько раз, мы в какой-то момент получим тот же. Для функции из нашего примера = {1, 2, 4}.

Если упорядочить по возрастанию элементы и рассмотреть ограничение на нём |, то эта функция будет действовать как перестановка, которую мы можем записать строкой (в приме ре будет | = 412). Теперь, выбрав в качестве вершин графа элементы [], мы можем соединить вершины из в порядке, заданном перестановкой. Элементы [] пока правда остаются изолированными. Чтобы сформировать из них дерево, для каж дого значения [], если () = добавим ребро. Для функции из примера это будут рёбра 31 и 54. Получившееся де рево изображено на рисунке 3.12.

(начало) 4 2 (конец) Рис. 3.12. Дерево, построенное по функции Надо теперь показать, что и для каждого дерева мы можем задать функцию. Это делается в полной аналогии: вначале вы бираем в дереве условные «начало» и «конец» (внимание!) и на ходим путь от начала к концу. Вершины этого пути задают мно 3 Натуральные числа жество, а последовательность вершин перестановку |. Для вершин, не вошедших в этот путь, в качестве значения () выбираем следующую вершину по пути от до «конца» дерева.

Остаётся лишь заметить, что заданная конструкция даёт нам не просто дерево, а дерево с выбранными «началом» и «концом».

У дерева с вершинами есть 2 способов определить начало и конец, поэтому количество произвольных деревьев в 2 раз мень ше, чем количество функций [] []. (По-хорошему так же на до более чётко указать, что соответствие деревьев и функций в данном случае действительно однозначное, но это не сложно и я оставляю это в качестве упражнения читателю).



Pages:     | 1 |   ...   | 3 | 4 ||
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.