Литература 22 3 основные операции со множествами 4 Основные операции со множествами Определение
 Скачать 154.25 Kb.
|
|
n − m ∑ k=1 ( −1) k+1 · C k m · (m − k) n = m ∑ k=0 ( −1) k · (m − k) n · C k m . 5. ЛИНЕЙНЫЕ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ С ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ18 Следствие 4.1 (О числах Стирлинга второго рода). S k n = 1 k! k ∑ i=0 ( −1) i · (k − i) n · C i k . Доказательство. Число сюръекций из множества мощности n в множество мощности k совпадает с числом способов разложить n различных шаров по k раз- личным ящикам так, чтобы ни один ящик не был пустым. По определению число Стирлинга второго рода S k n равно числу разбиений множества мощности n на k непу- стых подмножеств, то есть числу разложений n различных шаров по k одинаковым ящикам. Искомая формула следует и того, что S k n · k! = D k n 5. Линейные рекуррентные соотношения с постоянными коэффициентами Определение. Пусть f : N ∪ {0} → R. Соотношение вида f (n + k) = a 1 · f(n + k − 1) + . . . + a k · f(n), где a i ∈ R, i = 1, . . . , k, называется линейным рекуррентным соотношением степени k с постоянными коэффициентами a 1 , . . . , a k . Определение. Бесконечная последовательность {x 0 , x 1 , . . . , x n , . . . } называет- ся решением рекуррентного соотношения f (n + k) = k ∑ i=1 a i · f(n + k − i), если при подстановке f (n) = x n для каждого n = 0, 1, 2, . . . это соотношение становится тождественным. Пример. Рассмотрим рекуррентное соотношение f (n + 2) = 3f (n + 1) − 2f(n). Последовательность {1, 2, 4, 8, 16, . . . , 2 n , . . . } является его решением. В самом деле, подставим f (n) = 2 n и f (n + 1) = 2 n+1 , получим: 3 · 2 n+1 − 2 · 2 n = 2 n+1 (3 − 1) = 2 n+2 = f (n + 2). Лемма 5.1 (О линейности решений рекуррентных соотношений). Пусть f (n + 2) = a 1 f (n + 1) + a 2 f (n) — линейное рекуррентное соотношение порядка 2. Пусть две последовательности {x 0 , x 1 , . . . , x n , . . . } и {y 0 , y 1 , . . . , y n , . . . } являются его решениями. Тогда для ∀α, β ∈ R последовательность {αx 0 + βy 0 , αx 1 + βy 1 , . . . , αx n + βy n , . . . } также является решением исходного рекуррентного соотношения. 5. ЛИНЕЙНЫЕ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ С ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ19 Доказательство. Подставим f (n) = αx n + βy n и f (n + 1) = αx n+1 + βy n+1 Получим: a 1 f (n + 1) + a 2 f (n) = a 1 (αx n+1 + βy n+1 ) + a 2 (αx n + βy n ) = = α(a 1 x n+1 + a 2 x n ) + β(a 1 y n+1 + a 2 y n ) = αx n+2 + βy n+2 = f (n + 2). Замечание. Лемма о линейности решений рекуррентных соотношений спра- ведлива и для линейных рекуррентных соотношений порядка, большего двух. Определение. Пусть f (n + k) = k ∑ i=1 a i · f(n + k − i) — линейное рекуррентное соотношение порядка k. Характеристическим многочленом этого рекуррентного со- отношения называется многочлен F(λ) = λ k − a 1 λ k −1 − a 2 λ k −2 − . . . − a k −1 λ − a k . Лемма 5.2 (О корнях характеристического многочлена). Пусть f (n + 2) = a 1 f (n + 1) + a 2 f (n) — линейное рекуррентное соотношение порядка 2, F(λ) — его характеристический многочлен, ρ — его корень. Тогда после- довательность {1, ρ, ρ 2 , . . . , ρ n , . . . } является решением исходного рекуррентного соотношения. Доказательство. Заметим, что F(λ) = λ 2 −a 1 λ −a 2 . Тогда, так как ρ — корень характеристического многочлена F(λ), то ρ 2 = a 1 ρ + a 2 . Подставим в рекуррентное соотношение f (n) = ρ n , f (n+1) = ρ n+1 и f (n+2) = ρ n+2 , получим: a 1 f (n + 1) + a 2 f (n) = a 1 ρ n+1 + a 2 ρ n = ρ n+2 = f (n + 2). Замечание. Лемма о корнях характеристического многочлена справедлива и для линейных рекуррентных соотношений порядка, большего двух. Теорема 5.1 (Об общем виде решения рекуррентного соотношения). Пусть f (n + 2) = a 1 f (n + 1) + a 2 f (n) — линейное рекуррентное соотношение порядка 2, причем коэффициенты a 1 , a 2 не равны нулю одновременно. Пусть F(λ) — характеристический многочлен этого рекуррентного соотношения, и пусть ρ 1 , ρ 2 — его корни. Тогда (1) Если ρ 1 ̸= ρ 2 , то любое решение рекуррентного соотношения имеет вид {x 0 , . . . , x n , . . . }, где x n = αρ n 1 + βρ n 2 ; (2) Если ρ 1 = ρ 2 , то любое решение рекуррентного соотношения имеет вид {x 0 , . . . , x n , . . . }, где x n = (αn + β)ρ n 1 ; 5. ЛИНЕЙНЫЕ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ С ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ20 Доказательство. 1. Из леммы о линейности решений и леммы о корнях ха- рактеристического многочлена следует, что последовательность {x 0 , . . . , x n , . . . }, где x n = αρ n 1 + βρ n 2 является решением исходного рекуррентного соотношения. Покажем, что любое решение имеет такой вид. Заметим, что любое решение однозначно определяется первыми двумя элемента- ми последовательности x 0 , x 1 . Поэтому решение рекуррентного соотношения пред- ставимо в нужном виде тогда и только тогда, когда для любых чисел x 0 , x 1 система уравнений { αρ 0 1 + βρ 0 2 = x 0 αρ 1 1 + βρ 1 2 = x 1 имеет решение относительно неизвестных α, β. Непосредственно вычисляется, что решением этой системы являются α = x 0 ρ 2 − x 1 ρ 2 − ρ 1 , β = x 1 − ρ 1 x 0 ρ 2 − ρ 1 . Так как ρ 1 ̸= ρ 2 , то решение всегда существует. 2. Покажем, что если ρ — корень кратности 2 характеристического многочлена, то последовательность {x 0 , x 1 , . . . , x n , . . . }, где x n = n · ρ n , является решением исходного рекуррентного соотношения. Так как характеристический многочлен F(λ) имеет корень ρ кратности 2, то λ 2 − a 1 λ − a 2 = (λ − ρ) 2 . Отсюда находим, что a 1 = 2ρ и a 2 = −ρ 2 Подставим f (n) = n · ρ n в рекуррентное соотношение, получим: a 1 f (n + 1) + a 2 f (n) = a 1 (n + 1)ρ n+1 + a 2 nρ n = = 2(n + 1)ρ n+2 − nρ n+2 = (n + 2)ρ n+2 = f (n + 2). Покажем теперь, что любое решение исходного рекуррентного соотношения пред- ставимо в нужном виде. Для этого, как и ранее, достаточно проверить, что при любых x 0 , x 1 система { (α · 0 + β)ρ 0 = x 0 (α · 1 + β)ρ 1 = x 1 имеет решение. Непосредственно вычисляется, что решением являются α = x 1 − ρx 0 ρ , β = x 0 . Из условия теоремы следует, что ρ ̸= 0, следовательно решение системы всегда существует. 5. ЛИНЕЙНЫЕ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ С ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ21 Замечание. В общем случае, если ρ является корнем кратности s характери- стического многочлена F(λ), то в общем виде решения рекуррентного соотношения f (n + k) = k ∑ i=1 a i f (n + k − i) ему соответствует слагаемое (C 1 · n s −1 + C 2 · n s −2 + . . . + C s ) · ρ n . Пример. Найдем решение рекуррентного соотношения f (n + 2) = f (n + 1) + f (n), задающего последовательность чисел Фибоначчи {1, 1, 2, 3, 5, 8, . . .} Характеристический многочлен рекуррентного соотношения f (n + 2) = f (n + 1) + f (n) имеет вид F(λ) = λ 2 − λ − 1. Находим, что ρ 1 = 1 + √ 5 2 и ρ 2 = 1 − √ 5 2 являются его корнями. Тогда общее решение рекуррентного соотношения представляется в следующем виде: x n = α · ( 1 + √ 5 2 ) n + β · ( 1 − √ 5 2 ) n Неизвестные коэффициенты α, β найдем из условия: x 0 = 1 и x 1 = 1. Для этого запишем систему: { α + β = 1 α · 1+ √ 5 2 + β · 1 − √ 5 2 = 1 и получим, что тогда α = √ 5 + 1 2 √ 5 , β = √ 5 − 1 2 √ 5 . Окончательно находим, что x n = 1 √ 5 ( 1 + √ 5 2 ) n+1 + ( 1 − √ 5 2 ) n+1 . Литература [1] Мещеряков М.В. Избранные лекции по дискретной математике. Часть 1: кобинаторика и графы // Саранск: Изд-во Мордовского ун-та, 2003. [2] Холл М. Комбинаторика // Москва: Мир, 1970. [3] Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика // Москва: МЦНМО, 2006. [4] Яблонский С.В. Введение в дискретную математику // Москва: Наука, 1986. 22 |