Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
a n+k + p 1 a n+k−1 + . . . + p k a n = 0 (5.4) (p i = const), последовательность a 0 , a 1 , a 2 , . . . называется возвратной. Мно- гочлен P a (x) x k + p 1 x k−1 + . . . + p k (5.5) называется характеристическим для возвратной последовательности {a n }. Корни многочлена P a (x) называются характеристическими. Множество всех последовательностей, удовлетворяющих данному ре- куррентному соотношению, называется общим решением. Описание общего решения соотношения (5.4) имеет аналоги с описани- ем решения обыкновенного дифференциального уравнения с постоянными коэффициентами. Теорема 5.6.1. 1. Пусть λ — корень характеристического многочле- на (5.5). Тогда последовательность {cλ n }, где c — произвольная константа, удовлетворяет соотношению (5.4). 2. Если λ 1 , λ 2 , . . ., λ k — простые корни характеристического многочле- на (5.5), то общее решение рекуррентного соотношения (5.4) имеет вид a n = c 1 λ n 1 + c 2 λ n 2 + . . . + c k λ n k , где c 1 , c 2 , . . . , c k — произвольные константы. 178 Глава 5. КОМБИНАТОРИКА 3. Если λ i — корень кратности r i (i = 1, . . . , s) характеристического многочлена (5.5), то общее решение рекуррентного соотношения (5.4) име- ет вид a n = s X i=1 (c i1 + c i2 n + . . . + c ir i n r i −1 ) · λ n i , где c ij — произвольные константы. ¤ Зная общее решение рекуррентного уравнения (5.4), по начальным усло- виям a 0 , a 1 , . . ., a k−1 можно найти неопределенные постоянные c ij и тем самым получить решение уравнения (5.4) с данными начальными условия- ми. Пример 5.6.2. Найти последовательность {a n }, удовлетворяющую ре- куррентному соотношению a n+2 − 4a n+1 + 3a n = 0 и начальным условиям a 1 = 10, a 2 = 16. Корнями характеристического многочлена P a (x) = x 2 − 4x + 3 являются числа x 1 = 1 и x 2 = 3. Следовательно, по теореме 5.6.1 общее решение имеет вид a n = c 1 + c 2 3 n . Используя начальные условия, получаем систему ( c 1 + 3c 2 = 10, c 1 + 9c 2 = 16, решая которую, находим c 1 = 7 и c 2 = 1. Таким образом, a n = 7 + 3 n . ¤ Рассмотрим неоднородное линейное рекуррентное уравнение a n+k + p 1 a n+k−1 + . . . + p k a n = f (n), n = 0, 1, . . . (5.6) Пусть {b n } — общее решение однородного уравнения (5.4), а {c n } — частное (конкретное) решение неоднородного уравнения (5.6). Тогда после- довательность {b n +c n } образует общее решение уравнения (5.6), и тем самым справедлива Теорема 5.6.2. Общее решение неоднородного линейного рекуррентного уравнения представляется в виде суммы общего решения соответствую- щего однородного линейного рекуррентного уравнения и некоторого част- ного решения неоднородного уравнения. ¤ 5.6. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ 179 Таким образом, в силу теоремы 5.6.1 задача нахождения общего решения рекуррентного уравнения (5.6) сводится к нахождению некоторого частного решения. В отдельных случаях имеются общие рецепты нахождения частного ре- шения. Если f (n) = β n (где β не является характеристическим корнем), то, под- ставляя a n = cβ n в (5.6), получаем c(β k + p 1 β k−1 + . . . + p k ) · β n = β n и отсюда c · P a (β) = 1, т. е. частное решение можно задать формулой a n = 1 P a (β) · β n Пусть f (n) — многочлен степени r от переменной n и число 1 не является характеристическим корнем. Тогда P a (1) = 1 + p 1 + . . . + p k 6= 0 и частное решение следует искать в виде a n = r P i=0 d i n i . Подставляя многочлены в фор- мулу (5.6), получаем r X i=0 d i (n + k) i + p 1 r X i=0 d i (n + k − 1) i + . . . + p k r X i=0 d i n i = = r X i=0 d i ((n + k) i + p 1 (n + k − 1) i + . . . + p k n i ) = = r X i=0 d i (g 1 n i + . . .) = f (n). Сравнивая коэффициенты в левой и правой частях последнего равенства, получаем соотношения для чисел d i , позволяющие эти числа определить. Пример 5.6.3. Найти решение уравнения a n+1 + 2a n = n + 1 (5.7) с начальным условием a 0 = 1. Рассмотрим характеристический многочлен P a (x) = x+2. Так как P a (1) = = 3 6= 0 и правая часть f (n) уравнения (5.6) равна n + 1, то частное реше- ние будем искать в виде c n = d 0 + d 1 · n. Подставляя c n в уравнение (5.7), получаем (d 0 +d 1 (n+1))+2(d 0 +d 1 ·n) = (3d 0 +d 1 )+3d 1 ·n = 1+n. Приравни- вая коэффициенты в левой и правой частях последнего равенства, получаем систему ( 3d 0 + d 1 = 1, 3d 1 = 1, 180 Глава 5. КОМБИНАТОРИКА откуда находим d 0 = 2 9 , d 1 = 1 3 . Таким образом, частное решение уравне- ния (5.7) имеет вид c n = 2 9 + 1 3 n. По теореме 5.6.1 общее решение однородно- го уравнения a n+1 + 2a n = 0 задается формулой b n = c · (−2) n , и по теореме 5.6.2 получаем общее решение уравнения (5.7): a n = 2 9 + 1 9 n + c · (−2) n . Из на- чального условия a 0 = 1 находим 2 9 + c = 1, т. е. c = 7 9 . Таким образом, a n = 2 9 + 1 3 n + 7 9 (−2) n . ¤ Задачи и упражнения 1. Сколько различных слов можно составить из букв a, b, c, d, если использо- вать каждую букву по одному разу? 2. Сколькими способами можно расставить 8 ладей на шахматной доске так, чтобы они не били друг друга? 3. Сколько различных флагов можно составить из трех горизонтальных полос белого, синего и красного цветов? 4. Сколькими способами можно составить список из 22 студентов? 5. В чемпионате участвуют 12 спортсменов. Сколькими способами могут быть распределены золотая, серебряная и бронзовая медали? 6. 15 студентов обменялись попарно друг с другом фотографиями. Сколько всего фотографий? 7. Сколько существует неупорядоченных четырехзначных кодов, составленных из 10 цифр? 8. Во взводе 3 сержанта и 30 солдат. Сколько существует способов выделения одного сержанта и трех солдат для патрулирования? 9. Сколькими способами из 20 студентов можно выбрать 5 делегатов? 10. Сколькими способами из простых делителей числа 2310 можно составить числа, имеющие ровно два простых делителя? 11. Сколько диагоналей имеет выпуклый n-угольник? 12. Найти наибольшее возможное число пересечений диагоналей выпуклого n-угольника. 13. Сколькими способами можно разбить группу из 15 человек на две подгруп- пы, в одну из которых входят 4 человека, а в другую — 11? ЗАДАЧИ И УПРАЖНЕНИЯ 181 14. Решить уравнение: а) A 5 n = 18 · A 4 n−2 ; б) C x−2 x = 45, в) C 2x+3 2x+8 = 13 · A 3 2x+6 15. Найти два средних члена разложения (a 3 − ab) 31 16. Доказать, что а) 1 − C 1 n + C 2 n − C 3 n + . . . + (−1) n = 0; б) 1 2 + (C 2 n ) 2 + . . . + (C n n ) 2 = C n 2n 17. Крокодил имеет 68 зубов. Доказать, что среди 16 17 крокодилов может не ока- заться двух с одним и тем же набором зубов. 18. Сколько различных десятизначных чисел можно написать, используя циф- ры 0, 1 и 2? 19. Алфавит X состоит из двух символов. Сколько существует слов алфавита X, длины которых не превосходят 4? 20. Автомобильные номера данного региона состоят из трех цифр и трех букв алфавита X = {A, B, C, D, E, H, K, M, O, P, T, X, Y}. Сколько автомобилей может быть занумеровано различными номерами? 21. Сколькими способами можно разложить 5 монет достоинством 1 коп., 5 коп., 10 коп., 50 коп., 1 руб. в два кармана? 22. Чему равно число различных результатов бросаний двух неотличимых ку- биков, на грани каждого из которых нанесены цифры 1, 2, 3, 4, 5, 6? 23. Сколько различных перестановок образуется из следующих слов: а) зебра; б) баран; в) водород; г) абракадабра? 24. Группе из пяти сотрудников выделено три путевки. Сколько существует спо- собов распределения путевок, если: а) все путевки различны; б) все путевки одинаковы? 25. Сколько существует способов размещения 8 человек в восьмиместном авто- мобиле, если место водителя могут занять 4 человека? 26. На арену цирка выводятся 5 львов и 4 тигра. Сколькими способами мож- но расположить зверей в цепочку, если запрещено выводить тигров одного за другим? 182 Глава 5. КОМБИНАТОРИКА 27. В лотерее разыгрывается 5 выигрышных билетов. Подошедший к урне вы- нимает наугад 5 билетов из 100 имеющихся. Сколькими способами можно вынуть 3 выигрышных билета? 28. Имеется 2n билетов в театр на один ряд, состоящий из 2n мест. Сколько су- ществует способов распределения мест для компании из n мужчин и n жен- щин, если не располагаются рядом двое мужчин и две женщины? 29. На плоскости заданы m параллельных прямых, а также n параллельных прямых так, что каждая из m прямых пересекается с каждой из n прямых в единственной точке. Сколько различных параллелограммов можно соста- вить из рассматриваемых прямых? 30. Сколько решений в натуральных числах имеет уравнение x 1 + x 2 + . . . + x n = n? 31. Сколькими способами из группы в 30 человек можно сформировать 5 коа- лиций по 6 человек? 32. Сколько натуральных чисел от 20 до 1000 делятся ровно на одно из чисел 7, 11 или 13? 33. Сколько трехзначных чисел делятся хотя бы на одно из чисел: a) 7, 11, 13; б) 6, 8, 21? 34. Найти общее решение рекуррентного уравнения: а) a n+2 + 3a n = 0; б) a n+2 − a n+1 − a n = 0; в) a n+2 + 2a n+1 + a n = 0; г) a n+3 + 10a n+2 + 32a n+1 + 32a n = 0; д) a n+3 + 3a n+2 + 3a n+1 + a n = 0; е) a n+2 + 4a n+1 + 4a n = n 2 − 3n + 1. 35. Найти решение рекуррентного уравнения с начальными условиями: а) a n+2 − a n = 0, a 0 = 0, a 1 = 2; б) a n+2 − 6a n+1 + 9a n = 0, a 1 = 6, a 2 = 27; в) a n+2 + a n+1 − 2a n = n, a 0 = 1, a 1 = −2; г) a n+2 − 4a n+1 + 4a n = 3 n , a 0 = 5, a 1 = 7; д) a n+2 + 2a n+1 − 8a n = 27 · 5 n , a 1 = −9, a 2 = 45. Глава 6 АЛГЕБРА ЛОГИКИ § 6.1. Формулы алгебры логики Высказыванием называется повествовательное предложение, о котором в данной ситуации можно сказать, что оно истинно или ложно, но не то и другое одновременно. В качестве примеров высказываний приведем предложения “НГТУ — крупнейший вуз Новосибирска” и “Снег зеленый”. Первое высказывание яв- ляется истинным, а второе — ложным. Поставим в соответствие высказыванию P логическую переменную x, которая принимает значение 1, если P истинно, и 0, если P ложно. Если имеется несколько высказываний, то из них можно образовать раз- личные новые высказывания. При этом исходные высказывания называются простыми, а вновь образованные — сложными. Соответственно из логиче- ских переменных можно составлять различные конструкции, которые обра- зуют формулы алгебры логики. Итак, пусть {x i | i ∈ I} — некоторое множество логических переменных. Определим по индукции понятие формулы алгебры логики: 1) любая логическая переменная является формулой (называемой ато- марной); 2) если ϕ и ψ — формулы, то выражения ¬ϕ, (ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ → ψ), (ϕ ↔ ψ) являются формулами; 3) никаких других формул, кроме построенных по пп. 1 и 2, нет. Если формула ϕ построена из логических переменных, лежащих в мно- жестве {x 1 , x 2 , . . . , x n }, то будем писать ϕ(x 1 , . . . , x n ). Символы ¬, ∧, ∨, →, ↔, использованные в определении, называются ло- гическими операциями или связками и читаются соответственно: отрицание или инверсия, конъюнкция, дизъюнкция, импликация и эквивалентность. 184 Глава 6. АЛГЕБРА ЛОГИКИ Введенные в п. 2 формулы следующим образом интерпретируются в рус- ском языке: ¬ϕ — “не ϕ”, (ϕ ∧ ψ) — “ϕ и ψ”, (ϕ ∨ ψ) — “ϕ или ψ”, (ϕ → ψ) — “если ϕ, то ψ”, (ϕ ↔ ψ) — “ϕ тогда и только тогда, когда ψ”. Вместо ¬ϕ часто пишут ϕ, вместо (ϕ ∧ ψ) — (ϕ & ψ), (ϕ · ψ) или (ϕψ), а вместо (ϕ → ψ) — (ϕ ⊃ ψ). Действия логических операций задаются таблицами истинности, каждой строке которых взаимно однозначно сопоставляется набор значений переменных, составляющих формулу, и соответствующее этому набору значение полученной формулы: ϕ ¬ϕ 0 1 1 0 ϕ ψ (ϕ ∧ ψ) (ϕ ∨ ψ) (ϕ → ψ) (ϕ ↔ ψ) 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 1 1 1 Приведенные таблицы истинности называются также интерпретациями логических операций и составляют семантику формул (т. е. придание смыс- ла формулам) в отличие от синтаксиса формул (т. е. формальных законов их построения, данных в определении формулы). Исходя из таблиц истинности для логических операций можно строить таблицы истинности для произвольных формул. Пример 6.1.1. Построить таблицу истинности для формулы ϕ = ((x → y) ∧ ((y → z) → x)). Будем строить таблицу истинности последовательно в соответствии с ша- гами построения формулы ϕ: x y z (x → y) (y → z) ((y → z) → x) ϕ 0 0 0 1 0 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 1 1 1 1 0 0 Легко заметить, что таблица истинности для |