С.Н. Селезнева - Основы дискретной математики (1060725), страница 8
Текст из файла (страница 8)
. , bn ), где (b1 , . . . , bn ) ∈ C} \\ {(1, a1 , . . . , an )}.Полученнное разбиение куба B n на цепи называется разбиением нацепи Анселя14 .1. Разбить на цепи Анселя куб1) B 1 ;2) B 2 ;3) B 3 ;4) B 4 .2. Доказать индукцией по n, что в разбиении куба B n на цепи Анселяbnc1) всего цепей ровно Cn 2 ;2) цепей длины n − 2 · p + 1 ровно Cnp − Cnp−1 , p = 0, 1, .
. . , b n2 c;3) в любой цепи длины n − 2 · p + 1, где p = 0, 1, . . . , b n2 c, минимальныйэлемент содержит (n − p) нулей и p единиц и максимальный элементсодержит p нулей и (n − p) единиц;4) для любых трех наборов вида14Жорж Ансель (Hansel) – французский математик XX века.45α1 = (a1 , . . . , ai−1 , 0, ai+1 , .
. . , aj−1 , 0, aj+1 , . . . , an ),α2 = (a1 , . . . , ai−1 , 0, ai+1 , . . . , aj−1 , 1, aj+1 , . . . , an ),α3 = (a1 , . . . , ai−1 , 1, ai+1 , . . . , aj−1 , 1, aj+1 , . . . , an ),принадлежащих цепи длины n − 2 · p + 1, p = 0, 1, . . . , b n2 c, наборβ = (a1 , . . . , ai−1 , 1, ai+1 , . .
. , aj−1 , 0, aj+1 , . . . , an )принадлежит цепи длины n − 2 · p − 1.Задача 3.34. Пусть I = {i1 , . . . , ir } ⊆ {1, . . . , n}, 0 ≤ r ≤ n. Назовем множество I направлением. Гранью куба B n по направлению I ={i1 , . . . , ir } назовем подмножество его наборов, в которых в координатахi1 , . .
. , ir стоят известные значения σ1 , . . . , σr ∈ B, а оставшиеся координаты – произвольны. Другими словами, если Γ – грань по направлениюI = {i1 , . . . , ir }, тоΓ = {α = (a1 , . . . , an ) ∈ B n | ai1 = σ1 , . . . , air = σr }для некоторых σ1 , . . . , σr ∈ B. Число (n − r) при этом называется размерностью грани.1. Доказать, что грань размерности (n − r) является подкубом B n−r .2.
Доказать, что1) две грани по одному направлению I не пересекаются и каждыйнабор куба B n принадлежит в точности одной такой грани;2) все грани по одному направлению I образуют разбиение куба B n .3. Подсчитать в кубе B n1) количество граней по одному направлению I = {i1 , .
. . , ir },0 ≤ r ≤ n;2) количество граней размерности (n − r), 0 ≤ r ≤ n.4. Подсчитать количество всех граней куба B n .Задача 3.35. Пусть γ(n, r) – число граней куба B n размерности (n − r)(см. задачу 3.34). Доказать, что последовательность γ(n, r) при фиксированном n возрастает при r < 2n−1и убывает при r > 2n−133 .Задача 3.36. Доказать, что множество всех граней в кубе B n (см.
задачу 3.34) частично упорядочено по отношению ⊆. Найти минимальныеи наибольший элементы этого частичного порядка.4644.1ПоследовательностиВозвратные последовательностиОпределение 4.1. Если каждому натуральному числу n поставлено всоответствие некоторое число xn , то говорят, что задана последовательность {xn }. При этом числа xn называются элементами последовательности {xn }.Обозначение:{xn } – последовательность {xn }.Если все числа xn – натуральные, целые, рациональные, действительные или комплексные числа, то говорят о соответствующих последовательностях натуральных, целых, рациональных, действительных иликомплексных чисел.Определение 4.2.
Последовательность {xn } задана явно, еслиxn = f (n),где f (n) – некоторая функция.Определение 4.3. Последовательность {xn } задана рекуррентно, илизадана рекуррентным уравнением (степени k), еслиxn = f (xn−1 , . . . , xn−k ),где f (xn−1 , . . . , xn−k ) – некоторая функция, k ≥ 1.Если последовательность {xn } задана рекуррентным уравнением степени k и известны ее первые k элементов x1 , . . . , xk , то вся последовательность однозначно находится, так какxk+1 = f (xk , . .
. , x1 ), xk+2 = f (xk+1 , . . . , x2 ), . . .Определение 4.4. Решить рекуррентное уравнение – значит найти всетакие последовательности, которые, будучи подставлены в это уравнение, при каждом значении n превратят его в верное равенство (тождество). При этом множество всех таких последовательностей называетсяобщим решением рекуррентного уравнения, а каждая из последовательностей этого множества – частным решением рекуррентного уравнения.47Определение 4.5. Линейным однородным рекуррентным уравнениемназывается уравнение видаxn + p1 xn−1 + .
. . + pk xn−k = 0,p1 , . . . , pk – некоторые числа, k ≥ 1.Определение 4.6. Характеристическим многочленом линейного однородного рекуррентного уравненияxn + p1 xn−1 + . . . + pk xn−k = 0называется многочлен комплексной переменнойP (x) = xk + p1 xk−1 + . . . + pk−1 x + pk .Теорема 4.1. Пусть λ1 , . . . , λs – все корни характеристического многочлена линейного однородного рекуррентного уравнения кратности r1 ,.
. . , rs соответственно, r1 + . . . + rs = k. Тогда общее решение этогоуравнения имеет видxn =sX(Ci,0 + Ci,1 n + . . . + Ci,ri −1 nri −1 ) · λni ,i=1Ci,0 , Ci,1 , . . . , Ci,ri −1 – произвольные (комплексные) числа, i = 1, . . . , s.Определение 4.7. Возвратной называется последовательность, являющаяся решением какого-то линейного однородного рекуррентного уравнения. Другими словами, возвратная последовательность задается каким-то линейным однородным рекуррентным уравнением.Определение 4.8.
Линейным неоднородным рекуррентным уравнением называется уравнение видаxn + p1 xn−1 + . . . + pk xn−k = f (n),p1 , . . . , pk – некоторые числа, k ≥ 1, и f (n) – некоторая функция, не равная тождественно 0.Если в линейном неоднородном рекуррентном уравнении заменитьправую часть (то есть функцию f (n)) на 0, то полученное линейноеоднородное рекуррентное уравнение называется соответствующим исходному неоднородному уравнению.48Теорема 4.2. Общим решением линейного неоднородного рекуррентного уравнения является сумма какого-то его частного решения иобщего решения соответствующего ему линейного однородного рекуррентного уравнения.Теорема 4.3.
Для линейного неоднородного рекуррентного уравненияxn + p1 xn−1 + . . . + pk xn−k = (d0 + d1 n + . . . + dm nm ) · λn ,p1 , . . . , pk , d0 , d1 , . . . , dm , λ – некоторые числа, λ 6= 0, k ≥ 1, существуетчастное решение вида1) x0n = (c0 +c1 n+. . .+cm nm )·λn , где c0 , c1 , . . .
, cm – некоторые числа,если λ не является корнем характеристического многочлена соответствующего линейного однородного рекуррентного уравнения;2) x0n = nr · (c0 + c1 n + . . . + cm nm ) · λn , где c0 , c1 , . . . , cm – некоторыечисла, если λ – корень кратности r характеристического многочленасоответствующего линейного однородного рекуррентного уравнения.Общее решение однородного уравнения находится в соответствии с теоремой 4.1. Частное решение неоднородного уравнения можно искать в виде, указанном в теореме 4.3, методом неопределенных коэффициентов.Пример 4.1. Решить линейное однородное рекуррентное уравнениеxn − 2xn−1 − 15xn−2 = 0, x1 = −1, x2 = 43.Решение.
Найдем его характеристический многочлен: P (x) = x2 −2x − 15. Решим уравнение P (x) = x2 − 2x − 15 = 0. Откуда x = −3 иx = 5 – корни характеристического многочлена.Следовательно, общее решение исходного уравнения имеет вид:xn = C1 · (−3)n + C2 · 5n ,где C1 и C2 – произвольные константы.Подставим в общее решение значения x1 и x2 . Получаем систему уравнений для коэффициентов C1 и C2 :−3C1 + 5C2 = −1,9C1 + 25C2 = 43.Решая ее, находим C1 = 2, C2 = 1. Искомая последовательностьxn = 2 · (−3)n + 5n .Ответ: 2 · (−3)n + 5n .49Пример 4.2. Решить линейное неоднородное рекуррентное уравнениеxn − 4xn−1 + 4xn−2 = 2n − 9, x1 = 9, x2 = 31.Решение.
Сначала рассмотрим соответствующее однородное рекуррентное уравнение xn − 4xn−1 + 4xn−2 = 0. Найдем его характеристический многочлен: P (x) = x2 −4x+4. Решим уравнение P (x) = x2 −4x+4 =0. Откуда x = 2 – корень характеристического многочлена кратности 2.Общее решение соответствующего однородного рекуррентного уравнения имеет вид:(C1 + C2 n) · 2n ,где C1 и C2 – произвольные константы.Найдем частное решение исходного уравнения. Будем искать его ввиде c0 + c1 n, где c0 и c1 – некоторые константы, так как 1 не являетсякорнем характеристического многочлена P (x). Получаем(c0 + c1 n) − 4(c0 + c1 (n − 1)) + 4(c0 + c1 (n − 2)) = (c0 − 41 ) + c1 n = −9 + 2n.Приравнивая соответствующие коэффициенты при степенях n, находим:c0 = −1, c1 = 2.Следовательно, общее решение исходного уравнения имеет вид:xn = (C1 + C2 n) · 2n + (2n − 1),где C1 и C2 – произвольные константы.Подставим в общее решение значения x1 и x2 .
Получаем систему уравнений для коэффициентов C1 и C2 :C1 + C2 = 4,2C1 + 2C2 + 1 = 9,или4C1 + 8C2 + 3 = 31,C1 + 2C2 = 7.Решая ее, находим C1 = 1, C2 = 3. Искомая последовательностьxn = (1 + 3n) · 2n + (2n − 1).Ответ: (1 + 3n) · 2n + (2n − 1).504.2УпражненияЗадача 4.1. Найти общее решение следующих линейных однородныхрекуррентных уравнений:1)2)3)4)xn − 2xn−1 = 0;xn − 2xn−1 + xn−2 = 0;xn + 3xn−1 + 2xn−2 = 0;xn + xn−1 + 12xn−2 = 0;5)6)7)8)xn − 8xn−3 = 0;xn − x√=0;n−1 − 2xn−2 + 2xn−3√xn − 3 3xn−1 + 9xn−2 − 3 3xn−3 = 0;xn − 6xn−1 + 11xn−2 − 6xn−3 = 0.Задача 4.2. Решить следующие линейные однородные рекуррентныеуравнения:1)2)3)4)5)6)7)8)xn − 3xn−1 = 0, x1 = 15;xn + xn−1 − 2xn−2 = 0, x1 = 0, x2 = 3;xn − 4xn−1 + 4xn−2 = 0, x1 = 8, x2 = 28;xn − 5xn−1 + 6xn−2 = 0, x1 = 2, x2 = 5;xn − xn−1 − 2xn−2 + 2xn−3 = 0, x1 = 21 , x2 = 3, x3 = 2;xn − 3xn−1 + 3xn−2 + xn−3 = 0, x1 = 1, x2 = 3, x3 = 7;xn − 3xn−1 + 4xn−3 = 0, x1 = 5, x2 = 21, x3 = 55;xn − xn−3 = 0, x1 = 0, x2 = 0, x3 = 2.Задача 4.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
