Конспект лекций. Оглавление
 Скачать 1.11 Mb.
|
a в вершину b на прямоугольной сети дорог предыдущего параграфа. Каждому пути можно поставить в соответствие двоичное слово, обозначая единицей перемещение по горизонтали и нулем – по вертикали. Чтобы попасть из вершины a в вершину b надо сделать 4 перемещения по горизонтали и 3 по вертикали. Поэтому получающееся двоичные слова будут иметь длину 7 и состоять из 4 единиц и 3 нулей. Наоборот, каждому такому слову соответствует некоторый путь из вершины a в вершину b. Число таких двоичных слов равно и, следовательно, число всевозможных путей равно 35. ( ) ( ) ! 1 ! ! 1 1 1 Доказательство. Предположим, что n объектов выбираются из k типов и повторение допускается. Обозначим а – объект типа i. Тогда наш выбор определяется мультимножеством ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ = k k n n a a M 1 или по – другому а 1 а 1 ...а 1 | а 2 а 2 ...а 2 | ... | а k а k ...а k , где вой группе объектов элементы а повторяются n i рази. Группы завершаются вертикальной чертой за исключением последней серии элементов. Поскольку месторасположения каждого типа понятно, то выборку можно записать в виде Заметим, что разделителей | на один меньше количества типов. Таким образом, имеем n объектов плюс k–1 разделителей, образующих n+k–1 мест для размещения х или |. Каждое расположение знаков хи дает новый способ выбора n объектов из k типов. Поскольку существует способов выбора места для знаках или способов выбора знака | (что эквивалентно, то существуют различных способов выбора n объектов из k типов объектов с возможностью неограниченного повторения. n k n C 1 − + 1 1 − − + k k n C n k n k k n C C 1 Отметим, что здесь под символом x мы не имели ввиду объект какого – то конкретного типа, темы могли говорить об n неразличимых объектах, но различимых группах, в которые мы их пометили. Поэтому это модельное число часто называют числом размещений n неразличимых предметов по k ящикам. Однако, обычно, это число называют числом сочетаний из n пос повторением и обозначают n k C . 13 ( ) 15 2 5 6 ! 2 6 ! 2 ! 6 2 6 1 3 1 4 3 4 Проверим этот результат. Для этого перечислим всевозможные способы дележа яблок (4,0,0), (0,4,0), (0,0,4), (3,1,0), (3,0,1), (0,3,1), (1,3,0), (0,1,3), (1,0,3), (2,2,0), (2,0,2), (0,2,2), (2,1,1), (1,2,1), (1,1,2). Всего 15 способов. Пример. Вернемся к задаче с пончиками. Сколько существует различных вариантов выбора десяти пончиков из 4 – х видов Поскольку 10 объектов выбираются из 4 различных типов с повторением, то имеются ( ) 286 6 11 12 13 ! 10 ! 3 ! 13 ! 3 13 ! 3 ! 13 3 1 10 4 10 4 = ⋅ ⋅ = = − = = − + C C □ Пример. Найти количество целочисленных решений системы Решение. Число k можно представить в виде суммы k единиц, которые следует разложить в n корзин, сумма единиц в каждой из которых будет представлять число x i . Но число размещений k неразличимых предметов (в нашем случае единиц) по n корзинам (числам x i ) равно ( ) ( ) ! 1 ! ! 1 1 1 Перестановки с повторениями. Рассмотрим теперь задачу о количестве перестановок букв в слове КОЛОБОК. Оно состоит из семи букв, которые можно переставить 7! способами. Однако в нем есть три буквы О и две буквы К. Поэтому меняя местами буквы О или переставляя буквы К, мы не получим новых слов. Фактически мы имеем мультимножество М, K, ООО, Л, Б, элементы которого относятся км разным типам являются разными буквами. Обозначим их через a, b, c, d. Тогда М, a, b, b, b, c, d}. Если бы мы рассматривали все элементы множества М как различные, обозначив их а, ас то получили бы 7! перестановок, но после отбрасывания индексов многие из них оказались бы одинаковыми. Фактически каждая перестановка множества М встретилась бы ровно 2!3!1!1! раз, поскольку в любой перестановке М индексы при буквах а можно расставить 2! способами, при b — 3! способами, при си одним способом. Поэтому число перестановок элементов мультимножества М равно 420 ! 1 ! 1 ! 2 ! 3 ! 7 = и, тем самым, мы получаем, что разных слов из слова КОЛОБОК можно составить 420. В применении к общему случаю те же рассуждения показывают, что число перестановок любого мультимножества перестановки с повторениями) равно 14 M={1,2,3,4,5} вида {{1,3},{4},{2,5}}, {{1,3},{2,5},{4}}, {{2,5},{1,3},{4}} считаются одинаковыми. Подсчитаем, сколькими способами можно разбить множество M на подмножества, среди которых имеется m 1 одноэлементных, двухэлементных, m 3 трехэлементных и т.д. m n элементных подмножеств так, что . Число неупорядоченных разбиений множества M обозначается через N(m 1 ,m 2 ,…,m n ). Например, 17 яблок можно разложить в 6 кучек по 2 яблока и одну кучку из и яблок. Тогда m 2 =6 и m 5 =1, а остальные m i =0 . Число различных способов разложения этих яблок обозначается ( 5 , 2 , 17 1 ≠ ≠ = i i i ) ( ) 17 7 6 5 4 3 2 Вначале посчитаем количество упорядоченных перестановок множества. Для этого воспользуемся интерпретацией упорядоченных перестановок как разложения n шаров по различным m 1 + m 2 +... +корзинам так, что в каждую из m i корзин кладут i шаров. Темы имеем m 1 одноэлементных различимых корзин, m 2 – двухэлементных и т.д. Тогда всего возможных вариантов разбиения будет { { { { { ( ) ( ) ( ) ( ) n n n m m m m m ь ь ь m m m m n n n n n P ! ! 3 ! 2 ! 1 ! ! ! 3 !... 3 ! 2 !... 2 ! 1 !... 1 ! ,..., 3 ,... 3 , 2 ,..., 2 , 2 , 1 ,..., 1 , 1 3 2 1 3 2 1 3 2 1 ⋅ ⋅ = = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ 3 2 1 3 2 1 3 Теперь откажемся от упорядоченности подмножеств в разбиении, те. начнем считать корзины с одинаковым количеством элементов неразличимыми. Если все корзины имеют различное число шаров, то их можно рассматривать как различные (они отличаются числом шаров. В этом случае упорядоченные и неупорядоченные разложения шаров совпадают. Пусть теперь в разложении существуют m i корзин с одинаковым количеством шаров. При упорядоченном разложении такие корзины рассматриваются как различные. Однако при неупорядоченном разложении обмен шарами таких корзин можно рассматривать как соответствующую перестановку указанных корзин, что не приводит к новым разложениям. Если количество корзин с одинаковым числом шаров равно m i , то неупорядоченных разложений будет в m i ! меньше, чем упорядоченных. Общее число неупорядоченных разбиений будет враз меньше, чем упорядоченных. Следовательно, Заметим еще раз, что если выполнено упорядоченное разбиение числа n на подмножества различной длины (мощности, то они совпадают с неупорядоченными разбиениями. В этом случае все 1 или Пример. Сколькими способами 17 яблок можно разложить в 6 кучек по 2 яблока и одну кучку из и яблок Решение. Требуется разбить множество из 17 яблок на непересекающиеся и неупорядоченные кучки. Откуда искомое число равно Пример. Сколькими способами можно разделить колоду из 36 карт пополам так, чтобы в каждой пачке было по два туза Решение. Для разделения х тузов на две группы есть ( ) 3 ! 2 ! 2 ! 4 2 = способа. Поясним это. Если бы нам надо было определить количество способов выбрать 2 туза из четырех, то мы бы имели 6 ! 2 ! 2 ! 4 2 4 = = C способов. Перечислим эти варианты в левом столбце следующей таблицы, указав масти тузов, ив правом столбце укажем масти двух оставшихся тузов ♦ ♥ ♣ ♠ ♦ ♣ ♥ ♠ ♦ ♠ ♥ ♣ ♥ ♠ ♦ ♣ ♥ ♣ ♦ ♠ ♣ ♠ В нашей задаче, например, первая и последняя строки представляют одно и тоже разбиение, т.к. сейчас для нас не имеет значения в какую из двух групп попали тузы и ♣ ♠. Поэтому различных способов разделить 4 туза пополам в два раза меньше, те. всего 3. Далее. Каждая половина любого из этих трех разбиений тузов играет роль различных двух корзин, куда необходимо разложить пополам оставшиеся 32 карты. Разложение 32 оставшихся карт уже будет упорядоченным, так как корзины различные, число разложений равно ! 16 ! 16 ! 32 . Согласно правилу прямого произведения, общее число вариантов разделить колоду пополам равно ! 16 ! 16 ! 32 3 × 6.3 Бином Ньютона Бином Ньютона. Рассмотрим разложение Каждое слагаемое в разложении является результатом выбора а или b в каждом сомножителе (аи последовательного их перемножения. Например, а получено путем выбора а из каждого сомножителя. Если из 17 первого сомножителя выбрано аи выбрано из остальных сомножителей, тов результате получим ab 4 . Предположим, что требуется найти коэффициент при a 3 b 2 . Слагаемое a 3 b 2 получается при выборе трех аи двух b из пяти сомножителей. Поскольку существует способов выбора трех а, то коэффициент при a 3 b 2 равен . Обобщая результат, получаем следующую теорему. 3 5 C 3 Биномиальная теорема. Для произвольного положительного целого числа n справедливы равенства ( ) ∑ ∑ = − = − = = + n r r r n r n n r r n r r n n b a C b a C b a 0 Доказательство. Поскольку a r b n-r получено в результате кратного выбора аи кратного выбора b из n сомножителей в выражении а + b) n , то коэффициент при a r b n-r равен числу способов кратного выбора а из n сомножителей . Второе равенство следует из того факта, что Последняя формула известна под названием бином Ньютона. Поскольку - это коэффициенты в биноме Ньютона, то числа еще называют биномиальными коэффициентами. Примерами бинома Ньютона прибудут при n=1 Пример. Покажем, что для любого положительного целого числа n ∑ = = n r r n n C 0 Пусть a = b = 1, тогда по биномиальной теореме и результат очевиден. ( ) ∑ = − = + n r r n r r n n C 0 1 1 Пример. Количество подмножеств n – элементного множества. Все подмножества заданного элементного множества можно перечислить следующим образом. Вначале отмечаем пустое множество, потом перечисляем одноэлементные подмножества, потом перечисляем двухэлементные и т.д. Например, все подмножества множества {a,b,c} можно разместить следующим образом 18 Напомним, что представляет количество способов выбрать элементное подмножество из элементного множества или, по-другому, количество различных элементных подмножеств. По правилу суммы количество подмножеств элементного множества равно Используя результат предыдущего примера, получаем, что каждое n- элементное множество имеет 2 n разных подмножеств. Пример Доказать тождество ( ) n n r r n r n m m C = − ∑ = − 0 Воспользуемся формулой бинома Ньютона, где положим a=1 и b=m-1. Полиномиальная формула. Пусть слагаемых не два, а больше. Имеет место формула Она называется полиномиальной, где суммирование выполняется по всем решениям уравнения n n n n k = + + + 2 1 в целых неотрицательных числах, Для доказательства выполним умножение Чтобы привести подобные в полученном выражении, необходимо подсчитать количество одночленов вида каждого разбиения k n k n n x x x 2 1 2 1 n n n n k = + + + 2 1 . Для получения же одночлена необходимо выбрать х в качестве множителя в n 1 скобках при раскрытии выражения k n k n n x x x 2 1 2 1 . Это можно сделать способами. Из оставшихся n – нераскрытых скобок необходимо выбрать х в качестве множителя в скобках. Это можно сделать способами и т. д. Тогда количество одночленов при раскрытии выражения 1 n n C 2 1 n n n C − k n k n n x x x 2 1 2 будет равно числу ! !... ! ! 2 1 1 1 2 1 1 k n n n n n n n n n n n n n C C C k k = − − − − − перестановок с повторениями. Частный вид полиномиальной формулы, содержащий только два слагаемых, называется биномом Ньютона. ( ) ∑ = − = + n r r n r r n n b a C b a 0 19 Теорема. (Формула Паскаля. Для всех целых чисел r и n таких, что имеет место r n r n r n C C C 1 1 1 − − − + = (1) Доказательство. С одной стороны мы имеем По-другому Приравнивая коэффициенты при в обеих формулах, убеждаемся в справедливости формулы (1). Формула (1) дает эффективный способ вычисления биномиальных коэффициентов. Запишем биномиальные коэффициенты в таблицу (она называется треугольником Паскаля) Каждая (я строка этого треугольника состоит из биномиальных коэффициентов, получающихся при раскрытии скобок в выражении а + Так как 1, на внешних сторонах треугольника Паскаля всегда стоят единицы. Симметрия относительно вертикальной высоты треугольника следует из тождества . Выпишем 5 строк треугольника Паскаля Видим также, что каждое внутреннее число равно сумме двух верхних соседей. Это правило нами сформулировано в виде формулы Паскаля r n r n r n C C C 1 Формулу Паскаля можно доказать комбинаторно. Зафиксируем некоторый элемент n – элементного множества. Затем все r – элементные подмножества разобьем на два типа – к одному типу отнесем те подмножества, которые содержат выделенный элемента ко второму отнесем те подмножества, которые этот элемент не содержат. Ясно, что сумма количества первых и вторых подмножеств будет равна количеству r – 20 элементных подмножеств, те. . Определим количество подмножеств первого типа, которые содержат выделенный элемент. Поскольку элемент уже выбран, то надо выбрать r-1 объект из n-1 элемента множества, те. всего способов . Рассмотрим подмножества, которые не содержат выделенный элемент. По-прежнему требуется выбрать r объектов, но теперь из n – 1 объектов, учитывая, что один элемент не может быть выбран. Таким образом, существуют способов сделать такой выбор. Складывая количество способов выбора в обоих случаях, получаем r n C 1 1 − − r n C r n C 1 − r n r n r n C C C 1 Заметим, что доказать эту теорему можно также методом математической индукции. Теорема Вандермонда. Пусть m,n,r – положительные целые числа такие, что . Тогда Доказательство это число способов выбрать r предметов из m+n предметов. Предметы можно выбирать в два приема сначала выбрать k предметов из первых m предметов, а затем выбрать недостающие r-k предметов из оставшихся n предметов. Всего для этого существует способов. Отсюда общее число способов выбрать r предметов составляет r n m C + k r n k m C C − ⋅ ∑ = − ⋅ r k k r n k m C C 0 □ 6.4 Принцип включений – исключений. Поставим задачу подсчитать количество элементов в объединении нескольких множеств. Для двух множеств мы имели 2 1 2 1 2 1 A A A A A A I U − + = (1) Рассмотрим теперь объединение трех множеств. Обозначим A A A = 2 1 U и применим предыдущую формулу = − + = = 3 3 3 3 2 1 A A A A A A A A A I U U U ( ) 3 2 3 1 3 2 1 3 2 1 3 Применяя к 2 1 A A U и 3 2 3 1 A A A A I U I формулу для двух множеств, приходим к следующему соотношению 3 2 1 3 2 3 1 2 1 3 2 1 3 Переходя к n (n>2) множествам A 1 ,A 2 ,…,A n с использованием индуктивных соображений можно получить формулу + − + − = ∑ ∑ ∑ ≤ < < ≤ ≤ < ≤ = = 1 1 1 1 n k j i k j i n j i j i n i i n i i A A A A A A A I I I U 21 ( ) ( ) ∑ ≤ < < < ≤ + + − + + − + n i i i n n i i i p p p A A A A A A 1 2 1 1 1 2 1 2 1 1 1 I I I I I I , (2) которая в словесной формулировке выглядит так чтобы найти количество элементов в объединении множеств, нужно сложить количества элементов в каждом множестве, затем вычесть количество элементов во всевозможных попарных пересечениях, прибавить количество элементов во всевозможных пересечениях потри и т.д. Для доказательства формулы (2) необходимо показать, что в правой части каждый элемент множества подсчитан и учтен ровно один раз. Предположим, что элемента принадлежит в точности р множествам из набора А 1 ,А 2 ,А 3 ,...,А n . В сумме n A A A U U U 2 1 ∑ = n i i A 1 элемента учтен р раз. В сумме ∑ ≤ < ≤ n j i j i A A 1 I элемента учтен всякий раз, когда выбраны два множества, содержащие элемента. Существуют способов выбрать такие два множества. Следовательно, в сумме 2 p C ∑ ≤ < ≤ n j i j i A A 1 I элемента учтен раз. В сумме 2 p C ∑ ≤ < < ≤ n k j i k j i A A A 1 I I элемента учтен всякий раз, когда выбраны три множества, содержащие элемента. Существуют способов выбрать такие три множества. Следовательно, в сумме 3 p C ∑ ≤ < < ≤ n k j i k j i A A A 1 I I элемента учтен раз. В сумме элементов всех возможных пересечений r множеств, где 3 p C p r ≤ , элемент a учтен раз. Следовательно, в правой части формулы (2) элемента учтен r p C ( ) ( ) 1 1 3 2 1 1 + + − + + − + − + − p i p i p p C C C p раз. Но ( ) ( ) ( ) 0 1 1 1 1 1 3 Поэтому ( ) ( ) 1 1 3 2 1 1 1 и получаем, что элемент a учтен в точности один раз. На основании этой теоремы докажем утверждение, известное как Теорема о включении – исключении. Пусть А 1 ,А 2 ,А 3 ,...,А n — набор конечных множеств. Количество элементов множества n A A A I I I 2 определяется формулой 22 Доказательство. Из теории множеств известно, что ( ) A A A U A A A A A A n n U U U U U U I I I \ 2 1 2 1 2 Это легко видеть, например, из диаграммы Эйлера так что имеем соотношение n n A A A U A A A U U U I I I 2 1 2 Заменяя в этом равенстве число n A A A U U U 2 1 его представлением по формуле (2), получаем требуемый результат. Название этой теоремы подчеркивает использование последовательных включений и исключений элементов подмножеств. Формулы (2) или (3) называются формулами включения – исключения, а метод решения комбинаторных задач сих использованием называется методом включения – исключения. Этот метод обобщает правило суммы, которое было рассмотрено нами вначале темы комбинаторика Пример. Рассмотрим слова длины n в алфавите {0,1,2}. Сколько имеется слов, в которых встречаются все три цифры Обозначим A i множество всех слов длины n, в которых не встречается цифра i, i=0,1,2. Тогда n A A A 2 2 1 Кроме того, 1 2 1 2 0 1 0 = = = A A A A A A I I I . Наконец, 0 3 1 0 = A A A I I . В множество входят слова, в которых отсутствует хотя бы одна цифра. По принципу включений – исключений (формула (2)) 3 Следовательно, число слов, в которых присутствуют все три цифры, равно ( ) 1 2 3 Иногда удобно формулу из теоремы включений и исключений трактовать в другом виде. Пусть подмножество Х определяется наличием некоторого свойства Р у элементов множества U. Тогда подмножество объединяет элементы из U, которые обладают хотя бы одним из свойств P i . Дополнение m X X X X U U U 2 1 = X составляют элементы, которые не обладают ни одним из свойств Р. Пересечения вида 23 k i i i X X X X I I I 2 1 = объединяют элементы, обладающие одновременно свойствами . Если обозначить число элементов в U через |U| = n, число элементов, обладающих одновременно набором свойств , через k i i i P P P ,..., , 2 1 k i i i P P P ,..., , 2 1 ( ) k i i i P P P N ,..., , 2 1 , то для числа элементов, не обладающих ни одним из свойств Р, имеем формулу Пример. Сколько натуральных чисел из первых 100 не делятся одновременно на 2, 3 и 5? Обозначим число натуральных чисел из первых 100, делящихся на два через N(P 2 ). Это число легко найти ( ) [ ] 50 2 / 100 2 = = P N . Здесь квадратные скобки обозначают наибольшее целое число, не превосходящее данное. Аналогично ( ) [ ] 33 3 / 100 3 = = P N , ( ) [ ] 20 5 / 100 5 = = P N . Далее число натуральных чисел из первых 100, делящихся одновременно на 2 и 3, те. на наименьшее их кратное 6, равно Аналогично получим ( ) [ ] 16 6 / 100 , 3 2 = = P P N ( ) [ ] 10 10 / 100 , 5 2 = = P P N , . Наконец, число всех натуральных чисел из первых 100, делящихся одновременно на 2, 3 и 5, равно ( ) [ ] 6 15 / 100 , 5 3 = = P P N ( ) [ ] 3 30 / 100 , , 5 Теперь, применяя формулу включений и исключений, получим Пример. В группе 23 студента. Из них 18 знают английский язык, 9 — немецкий и 6 — оба языка. Сколько студентов в группе не знают ни одного языка Сколько студентов знают только один язык Решение. Пусть S— множество всех студентов, |S| = 23. Назначим свойства элементам S s ∈ : Р — знание английского языка, Р — знание немецкого языка. N(0) — количество студентов, незнающих языков (не обладают свойствами, N(1) — количество студентов, знающих только один язык. Тогда ( ) ( ) ( ) ( ) 2 6 9 18 23 23 0 2 1 2 1 = + − − = ⋅ + − − = P P N P N P N N ( ) ( ) ( ) ( ) ( ) ( ) ( ) 15 6 9 6 18 1 2 1 2 2 1 Пример (задача о беспорядках. Перестановка a 1 a 2 …a n чисел 1,2,…,n называется беспорядком, если i a i ≠ для всех i = 1, 2, …, n. Таким образом, беспорядок – это перестановка, в которой ни один элемент не занимает своего места. Задача о беспорядках состоит в том, чтобы подсчитать число D n перестановок – беспорядков. Например, D 2 =1 – два числа {1,2} образуют только один беспорядок (2,1). D 3 =2, поскольку беспорядками из трех чисел 24 {1,2,3} являются (3,1,2) и (2,3,1). Перечислим беспорядки из четырех элементов 2143; 2341; 2413; 3142; 3412; 3421; 4123; 4312; 4321. Значит, D 4 = 9. Если перестановке назначить свойство – один предмет остается на своем месте, то таких перестановок будет ( ) ! 1 1 − n C n , поскольку предмет может находиться на любом из месте, а остальные элементы можно переставить 1 n C ( ! 1 ) − n способами. Аналогично, перестановок в которых два предмета остаются на своем месте будет ( ) ! 2 2 − n C n и т.д. Подставляя это в (3) приходим к Последнее равенство можно переписать следующим образом Также ясно, что количество перестановок n различных предметов, при которых ровно k предметов стоят на своих первоначальных местах, выражается числом k n k n k n D C D − ⋅ = , 6.5 Метод рекуррентных соотношений Последовательность a 0 ,a 1 ,a 2 ,… называют рекуррентной, если указана зависимость общего члена последовательности от предыдущих и заданы значения необходимого числа начальных членов. Примерами рекуррентных последовательностей могут служить арифметические и геометрические прогрессии. Члены геометрической прогрессии a 0 , a 1 , a 2 ,… со знаменателем q по- определению связаны рекуррентным соотношением a n+1 =q и для однозначного ее определения надо задать начальное значение Члены произвольной арифметической прогрессии a 0 , a 1 , a 2 ,… связаны рекуррентным соотношением Δ + = + n n a a 1 или, например, соотношением a n+2 = 2a n+1 – Действительно ( ) Δ − + = 1 0 n a a n Δ ⋅ + = + n a a n 0 1 ( ) ( ) ( ) ( ) n n n a a n a n a n a a − ⋅ = Δ − + − Δ ⋅ + = Δ + + = + + 1 0 0 0 2 2 1 Последовательность факториалов 1,2,6,…,n!,… определяется рекуррентным соотношением с заданием начального значения a 0 = 1. Как рекуррентость может трактоваться формула 25 связывающая биномиальные коэффициенты. Пример. Рассмотрим задачу о разбиении плоскости прямыми. Пусть D n – число областей, на которые разбивают плоскость n прямых общего положения (таких, что никакие три из них не пересекаются в общей точке и никакие две прямые не параллельны. Ясно, что D 0 = 1, D 1 = 2. Предположим, что на плоскости уже проведено n прямых, и посмотрим, сколько новых областей добавляется при проведении новой й прямой. Каждую область, по которой проходит эта прямая, она рассекает на две. Таким образом, общее число областей увеличится на число областей, через которые проходит я прямая. Двигаясь пой прямой водном направлении, мы пересечем границы областей n раз по числу старых прямых. Значит, я прямая пройдет через n+1 область (в последовательности область – граница – … – область – граница – область, число областей на единицу больше, чем число границ. В результате получаем рекуррентное соотношение D n+1 =D n +(n+1). Чтобы найти замкнутое выражение для членов последовательности D n , просуммируем следующие равенства D 1 = D 0 + 1; D 2 = D 1 + 2; ……………… D n = D n–1 + n . После сокращений получаем D n = D 0 + 1 + 2 +…+n . Следовательно, ( ) 2 Рекуррентная последовательность называется линейной однородной, если ее члены связаны соотношением вида где a i , i=1,2,…,r, – постоянные, независящие от n. Соотношение (1) называется линейным однородным рекуррентным уравнением порядка r. 26 Пример. Уравнение первого порядка с постоянными коэффициентами имеет вид 0 1 = − − n n y a y и задается начальное значение . (2) 0 Последовательные вычисления дают 0 1 2 0 n n n n n y a y a a y a y a y − − = ⋅ = ⋅ То. геометрическая прогрессия является решением линейного однородного рекуррентного уравнения первого порядка. Пример. Уравнение первого порядка с переменными коэффициентами имеет вид 0 1 = − + n n n y a y с начальным значением . Тогда 0 0 y y = 0 0 1 y a y = 0 0 1 1 1 2 y a a y a y = = 0 0 1 2 2 2 3 y a a a y a y = = ∏ − = − = ⋅ = 1 0 0 0 0 1 2 где использовано обозначение n n k k a a a a a ⋅ ⋅ ⋅ ⋅ = ∏ = 2 1 0 Пример. Линейное неоднородное уравнение го порядка имеет вид , для которого надо задать начальное значение и последовательность значений . Имеем 0 0 y y = n f 1 0 y a y f = ⋅ + 1 ( ) ( ) 2 2 1 2 0 1 2 0 1 y a y f a a y f f a y af f = ⋅ + = ⋅ + + = + + 2 ( ) ( ) ( ) 2 3 2 3 2 3 0 1 2 3 0 1 2 y a y f a a y af f f a y a f af f = Ясно, что 0 1 n n n n k y a y a f − = = + ∑ (3) Здесь мы имеем сумму решения однородного уравнения (2) и некоторого частного решения неоднородного уравнения . Действительно 1 n n k n k z a − = = ∑ ( ) 1 2 1 1 2 1 n n n n n n z a z a f a f af f − − − − − ⋅ = + + + + − K ( ) 2 3 1 2 2 1 n n n n a a f a f af f f − − − − − + + + + K n = Пример. Требуется подсчитать количество двоичных слов длины n, в которых единицы не могут стоять на соседних местах. Будем называть такие слова правильными и обозначим через A n число правильных слов длины n. Разобьем множество правильных слов длины n на два класса слова оканчивающиеся на ноль и слова, оканчивающиеся на единицу. Количество 27 слов в этих классах обозначим ( ) 0 n A и ( ) 1 n A соответственно. Очевидно, что ( ) ( ) 1 0 n n n A A A + = . У слова, оканчивающегося на ноль первые n-1 символов образуют правильное слово длины n-1. Следовательно ( ) 1 0 − = n n A A . Если правильное слово длины n оканчивается на единицу, то предыдущий символ этого слова должен быть нулем, а первые n-2 символа будут образовывать правильное слово длины n-2. Поэтому ( ) 2 1 − = n n A A . В результате мы имеем соотношение 2 Как видим, решение нашей задачи свелось к рекуррентному уравнению. В переводе – возвратному, так как для подсчета интересующей нас величины для некоторого n нужно возвратиться к предыдущим значениям этой величины. Здесь легко видеть, что 2 1 = A и 2 2 = A . Поэтому 4 2 2 3 = + = A , и т.д. 6 4 2 4 = + = A □ В общем случае рекуррентное соотношение имеет вид ( ) k n n n n a a a F a − − − = ,..., , 2 1 (4) Как правило, мы будем иметь дело с уравнением вида k n k n n n a c a c a c a − − − + + + = 2 2 1 1 (5) где - заданные числа. Такое соотношение называют линейным рекуррентным уравнением k – го порядка с постоянными коэффициентами. Соотношение (4) или (5) мы будем рассматривать как уравнение относительно неизвестной функции A(n)=A n и каждую последовательность k c c c ,..., , 2 1 ( ) ,... ,..., , 1 для которой выполняется соотношение (4) или (5) будем называть решением рекуррентного соотношения. Лемма 1 . Если последовательность ( ) ,... ,..., , 1 0 n A A A A = является решением рекуррентного соотношения (5) и C любое число, то и последовательность ( ,... ,..., , ) 1 также является решением рекуррентного соотношения (5). Доказательство. Подставив вторую последовательность в (5) и поделив на C , убеждаемся, что и вторая последовательность является решением. Если же C=0, то последовательность A C состоит из одних нулей и, очевидно, также удовлетворяет соотношению (5). Лемма 2 . Если ( ) ,... ,..., , 1 0 n A A A A = ( ) ,... ,..., , 1 0 n B B B B = являются решениями рекуррентного соотношения (5), то последовательность ( ) ,... ,..., , 1 1 0 также является решением рекуррентного соотношения (5). Доказательство. Так как A и B являются решениями, то k n k n n n A c A c A c A − − − + + + = 2 2 1 1 28 k n k n n n B c B c B c B − − − + + + = 2 2 1 Сложив эти соотношения, получаем ( ) ( ) ( k n k n k n n n n n n B A c B A c B A c B A − − − − − − + ) + + + + + = + 2 2 2 1 1 1 , те. k n k n n n C c C c C c C − − − + + + = 2 2 1 Рекуррентные уравнения для нас важны, поскольку часто решение одной комбинаторной задачи удается свести к решению аналогичных задач меньшей размерности. Тем самым решение сложной задачи можно получить, последовательно находя решения более легких задачи далее, пересчитывая по рекуррентным соотношениям, находить решение трудной задачи. Формула (4) является рекуррентным соотношением между элементами последовательности чисел . То. рекуррентное соотношение позволяет по известным значениям вычислить значение а, но первые несколько значений нужно знать заранее. Как мы видели в примерах, иногда удается получить из рекуррентного соотношения общую формулу для вычисления а по номеру n. Тогда можно сразу вычислить окончательный результат без вычисления всех предыдущих результатов. n k n a a ,..., − n k n a a ,..., − 1 Пример. Вернемся к рекуррентному соотношению а n =а n-1 + а Оно задает так называемые числа Фибоначчи F 0 , F 1 , F 2 , F 3 , … , если положить F 0 =0 и F 1 =1. Тогда последовательность решений будет иметь вид 0, 1, 1, 2, 3, 5, 8, 13, 21, Найдем общую формулу для чисел Фибоначчи. Будем искать ее в виде . Подстановка в рекуррентное соотношение дает Разделим обе части равенства на 0 . Получим квадратное уравнение . Найдем его корни n n a λ = 2 1 − − + = n n n λ λ λ 2 ≠ − n λ 0 В соответствии с леммой 1 решением являются и , где и C 2 произвольные постоянные. В соответствии с леммой 2 решением будет их сумма. То. общим решением будет линейная комбинация n n C a 1 1 λ = n n C a 2 Произвольные постоянные найдем изначальных условий a 0 =0, a 1 =1. Имеем 2 1 0 0 C C a + = = 1 и 5 2 5 1 2 5 1 2 5 1 2 5 1 1 1 1 2 1 1 C C C C a = ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ − − + = − + + = = 29 Тогда 5 1 , 5 1 2 1 − = = C C . Окончательно общее решение рекуррентного соотношения будет иметь вид который называется формулой Бине. Заметим, что деление отрезка такое, что отношение длин полученных частей равняется 2 5 1 + − называют золотым сечением. Поэтому это число часто называют отношением золотого сечения. Рассмотренный пример позволяет сформулировать общий прием решения линейных рекуррентных уравнений. Теорема. Пусть 0 1 1 = + + + − − k n k n n a c a c a – линейное однородное рекуррентное уравнение с постоянными коэффициентами Const c i = , и пусть ( k i ,... 2 , 1 = ) λ — корень характеристического уравнения . Тогда 0 1 1 = + + + − k k k c c λ λ 1) последовательность с общим членом , где С — произвольная константа, удовлетворяет исходному однородному рекуррентному уравнению n C λ 2) если k λ λ λ ,..., , 2 1 — простые корни характеристического уравнения, то общее решение рекуррентного соотношения имеет вид где С, i= 1,2, ..., k, — произвольные постоянные 3) если i λ — корень кратности r i , i =1, ..., s, характеристического уравнения, то общее решение рекуррентного соотношения имеет вид где — произвольные постоянные. Пример. Рассмотрим соотношение 2 1 2 3 − − ⋅ − ⋅ = n n n a a a , 3 , 1 2 1 = = a a . Оно является линейным рекуррентным соотношением с постоянными коэффициентами 0 2 3 2 1 = ⋅ + ⋅ − − − n n n a a a . Составим характеристическое уравнение 0 . Его корни 2 2 3 2 = + − λ λ , 1 2 , 1 = λ . Поэтому общее решение имеет вид . С учетом начальных условий имеем n n C C a 2 2 1 + = ⎩ ⎨ ⎧ = + = + 3 4 1 2 2 1 2 Тем самым C 1 = -1, С = 1. Окончательное решение будет 1 2 − = n n a 30 Для неоднородных линейных рекуррентных соотношений имеет место Теорема. Пусть n k n k n n f a c a c a = + + + − − 1 1 – неоднородное линейное рекуррентное уравнение, Его общее решение представляется в виде суммы общего решения соответствующего однородного уравнения и некоторого частного решения неоднородного уравнения Доказательство. Мы имеем 0 0 0 1 1 0 = + + + − − k n k n n a c a c a (однородное уравнение) n H k n k H n H n f a c a c a = + + + − − 1 1 (неоднородное уравнение) Сложим эти соотношения ( ) ( ) ( ) n H k n k n k H n n H n n f a a c a a c a a = + + + + + + − − − − 0 1 0 1 1 То. является решение неоднородного уравнения Пример. Рассмотрим уравнение , n n n n a a a 3 2 2 3 2 1 ⋅ + ⋅ − ⋅ = − − 86 , 30 Оно является неоднородным рекуррентным уравнением 2 – го порядка n n n n a a a 3 2 2 3 2 Соответствующее ему однородное уравнение было рассмотрено в предыдущем примере и имело общее решение . Теперь найдем частное решение неоднородного уравнения. Будем искать его в виде , где коэффициент A будем подбирать. Подстановка в исходное неоднородное уравнение дает n n C C a 2 2 1 0 + = n H n A a 3 ⋅ = n n n n A A A 3 2 3 2 3 3 3 2 1 ⋅ = ⋅ ⋅ + ⋅ ⋅ − ⋅ − − или n n A 3 2 3 Сокращая на , получаем A=9. То. общее решение неоднородного уравнения будет иметь вид . Изначальных условий находим 2 3 − n n n n C C a 3 9 2 2 1 ⋅ + + = 1 1 2 1 3 9 2 30 ⋅ + + = C C 2 2 2 1 3 9 2 Решение системы уравнений дает C 1 =1, C 2 =1. Окончательно, решение имеет вид n n n a 3 9 2 1 ⋅ + + = □ |