В.А. Носов - Комбинаторика и теория графов (1023552), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

.Интересующие нас подстановки ϕ2 есть подстановки, не обладающие ни однимиз названных свойств P1, … , Pn.Имеем N = n!, N(Pi) = (n - 1)!, … , N( Pi1 , K , Pi k ) = (n - k)! . Применяя формулу включе46ния-исключения, получаем справедливость формулы (8), а следовательно, и формулы (7). ♦Зафиксируем теперь число k, 0 ≤ k ≤ n. Две подстановки ϕ1, ϕ2 множества X называются k-толерантными, если имеется точно k элементов x ∈ X, для которыхϕ1(x) = ϕ2(x).Аналогично предыдущему, используя формулы (2), можно показать, что число Qnk парk-толерантных подстановок n-множества выражается формулойQnk =( n !) 2 1 11 n− k 1 − + −L+ ( −1)k !  1! 2 !( n − k ) !(9)Если вместо подстановок рассматривать отображения, то вопросы их толерантности решаются легко.

Пусть имеется n-множество X = {x1, … , xn} и m-множество Y == {y1, … , ym} . Два отображения f, g : X → Y называются толерантными, если существует x ∈ X, такое, что f(x) = g(x). Не толерантные отображения f, g называются противоречивыми. Число Mmn пар противоречивых отображений n-множества X в m-множествоY дается формулойMmn = mn (m - 1)n(10)Зафиксируем число k, 0 ≤ k ≤ n. Два отображения f, g : X → Y называютсяk-толерантными, если существует точно k элементов x ∈ X, таких, что f(x) = g(x). ЧислоNmn пар k-толерантных отображений n-множества X в m-множество Y дается формулой nNmn =   (m − 1) n − k ⋅ m n k(11)5.

Рассмотрим задачу построения подстановок n-множества X = {x1, … , xn}методом бесповторного набора. Суть метода заключается в следующем. Фиксируетсячисло t ≥ n и рассматривается произвольная последовательность a = (a1, a2, … , at) элементов множества X длины t. Тогда по последовательности a строится подстановка πaследующим образом: πa(x1) = a1 .

Если определены πa(x1), …, πa(xk) , то πa(xk+1) = al , гдеl - наименьший индекс, такой, что al ≠ πa(x1), al ≠ πa(x2), … , al ≠ πa(xk). Данный методпостроения подстановки - “частотный”, т.е. не для всякой последовательности a можетбыть построена подстановка πa. Примером такой последовательности является последовательность a = (x1, x1, … , x1) . Данный метод приводит к результату тогда и только47тогда, когда в последовательности a содержатся все элементыx1, … , xn .Число Rnt последовательностей a = (a1,… , at) в алфавите X = {x1, … , xn} , содержащих все элементы X (t ≥ n)выражается формулой n n nRnt = nt -   ( n − 1) t +   ( n − 2) t −L+ ( −1) n   ( n − n) t 1 2 n(12)♦ Представляя последовательность a = (a1, … , at) как отображениеϕ : Y → X, где Y = {1, 2, … , t}и отождествляя (a1,… , at) ≡ (ϕ(1), ϕ(2), … , ϕ(t)), получаем, что последовательности (a1,… , at), содержащие все элементы X = {x1, … , xn}, естьсюръективные отображения ϕ : Y → X.

Остается применить формулу (6). ♦6. Пусть X = {x1, … , xn}. найдем число Un подстановок ϕ множества X, таких,что ϕ(xi) ≠ xi и ϕ(xi) ≠ xi+1, i ∈1, n − 1, ϕ(xn) ≠ xn и ϕ(xn) ≠ x1. Другими словами, нас интересует число Un подстановок, противоречивых двум подстановкам: x1 x 2 x1 x 2... x n и... x n  x1 x 2 ...

x n  x 2 x 3 ... x1 Теорема 4. Для чисел Un (n > 1) справедлива формулаUn = n! -2 n  2 n − 22 n  2 n − 1n 2 n  n ( n − 1)!+ ( n − 2)! −K+ ( −1)  0!n  n2n − 2  2 2n − 1  1 ♦ Предварительно докажем две леммы.1. Два элемента из X вида (xi, xi+1) называются соседними ( i ∈1, n − 1). Числоf(n, k) подмножеств X из k элементов и не содержащих соседних элементов равно n − k + 1f(n, k) = k (14)♦ Каждое такое подмножество Y ⊆ X будем характеризовать двоичным вектором длины n a1, ...

, an , где ai = 1 ⇔ xi ∈ Y . Интересующим нас подмножествам соответствуют вектора с k единицами и не содержащие двух единиц подряд. Число таких векторов можно подсчитать так. Если взять последовательность n - k нулей, то k единиц могутразмещаться только в промежутках между нулями. Число мест для единиц n - k +1 , число единиц k. Следовательно, число интересующих нас подмножеств выражается формулой (14). ♦482. Пусть теперь считаются соседними элементы X вида (xi, xi+1), ( i ∈1, n − 1), атакже (x1, xn) . Тогда число g(n, k) подмножеств X из k элементов и не содержащих соседних элементов равноg(n, k) =n  n − kn−k k (15)♦ Разобьем все такие подмножества Y ⊆ X на два класса: те, которые содержатx1 , и те, которые не содержат x1 .

Подмножество, содержащее x1 , не содержит x2 и xn .Значит, число таких подмножеств равно числу (k - 1)-подмножеств из (n - 3)-множестваX′ = {x3, ... , xn-1}, не содержащих соседних элементов, и по предыдущему это число рав n − 3 − (k − 1) + 1  n − k − 1но =  . Число подмножеств второго класса равно числу kk −1  k −1 подмножеств из (n - 1)-множества X′′ = {x2, x3, … , xn}, не содержащих соседних эле n − 1 − k + 1  n − kментов, и, согласно предыдущему, это число равно  = . Следоваk  k тельно, интересующее нас число k-подмножеств по правилу суммы равно n − k − 1  n − kn  n − kg(n, k) = + = ♦ k −1   k  n − k  k Завершим теперь доказательство теоремы 4.

На множестве n! подстановок множестваX = {x1, , xn} введем 2n свойств P1, ... , Pn, , P1′, ... , Pn′, где ∀ i ∈1, n свойство Pi подстановки ψ означает, что ψ(xi) = xi , свойство Pi′ означает, что ψ(xi) = xi+1 при i ∈1, n − 1, приi = n Pn′ означает, что ψ(xn) = x1.Расположим указанные свойства в рядP1, P1′, P2, P2′, ... , Pn, Pn′(16)Теперь для любого k-подмножества множества этих свойств определим число Vk подстановок, обладающих каждым из свойств, входящих в k-подмножество.

Оно равно(n - k)!, если выбранные k свойств совместимы и 0 в противном случае. Чтобы применить формулу включения-исключения остается найти число способов выбора из 2nсвойств (16) k-подмножество совместимых свойств. Ясно, что несовместимыми свойствами являются два соседних в последовательности (16), при этом свойства Pn′ и P1 считаются соседними. Число способов выбора k-подмножеств совместимых свойств со-49гласно предыдущему равно2n  2n − k . По формуле включения-исключения полу2n − k  k чаем формулу (13). ♦50§ 2. Метод рекуррентных соотношенийДанный метод состоит в том, что решение комбинаторной задачи с n предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, называемого рекуррентным. Говорят, что последовательность элементов u0, u1, … un, … над полем комплексных чисел C удовлетворяет рекуррентному соотношению порядка k, еслиun = F(un-1, … , un-k),∀ n ≥k(1)Если задать u0, u1, … uk-1, то un, ∀ n ≥ k определено однозначно.

Рекуррентное соотношение называется линейным, еслиun = a1 un-1 + … + ak un-k,∀ n ≥k(2)где a1, … , ak - коэффициенты из C. Соотношения такого типа естественным образомвозникают при решении комбинаторных задач.Пример. Пусть имеется последовательность позиций, занумерованных числами1, 2, … , n, … и в начальный момент предмет находится в 1-ой позиции. За один ходпредмет продвигается вперед на 1 и 2 позиции.

Найти число способов попадания в n-юпозицию.♦ Пусть un - интересующее нас число. Ясно, что u2 = 1, u3 = 2 . Далее, разобьемвсе способы попадания в позицию с номером n на два класса: те, при которых на последнем шаге предмет передвигается на 1 шаг и те, при которых он передвигается на 2шага. Ясно, что в первом случае имеем un-1 вариантов, во втором un-2 вариантов. Следовательно, имеемun = un-1 + un-2(3)В качестве начальных условий можно взять u1 = 1, u2 = 1.

♦Полученные числа un называются числами Фибоначчи. Наиболее известной частью рекуррентных соотношений являются линейные рекуррентные соотношения. Свяжем с линейным соотношением (2) многочлен над CP(x) = xk - a1xk-1 - … - ak(4)Многочлен P(x) называется характеристическим для линейного рекуррентного соотношения (2). Заметим, что всякая рекуррентная последовательность k-го порядка однозначно определяется заданием k ее первых членов.Пусть λ - корень характеристического многочлена P(x).Теорема 1. Последовательность u0, u1, … un, … , где un = cλn, c - произвольнаяконстанта из C, удовлетворяет линейному рекуррентному соотношению (2).51♦Подставляя данные значения un, n = 0, 1, … в (2), имеемcλn - a1 cλn-1 - a2 cλn-2 - … - ak cλn-k = cλn-k (λk - a1 λk-1 - … - ak) ≡ 0.

♦Теорема 2. Пусть последовательности un, vn, n = 0, 1, … удовлетворяют линейному рекуррентному соотношению (2). Тогда этим свойством обладает последовательность rn, n = 0, 1, … , где rn = αun+ βvn , ∀ n , α, β - произвольные константы из C.♦ Доказательство очевидно. ♦Теорема 3. Пусть λ1, … , λk - простые (т.е. не являющиеся кратными) корни характеристического многочлена P(x) для последовательности (2).Тогда общее решение данного рекуррентного соотношения имеет видun = c 1λn1 + c 2 λn2 +K+ c k λnk ,∀n(5)где c1, … , ck - подходящие константы из C.♦ Согласно предыдущему замечаем, что последовательностьun, n = 0, 1, … естьрешение соотношения (2).

Чтобы доказать, что любое решение имеет вид (5) достаточнопоказать, что для произвольной последовательности vn, n = 0, 1, … , удовлетворяющей(2), существуют константы c1, … , ck, такие, что un = vn , ∀ n . Для этого достаточно, чтобы выполнялось v0 = u0, v1 = u1, … , vk-1 = uk-1 . Рассмотрим данные условияu0 = c 1 + c 2 + … + c k = v 0u1 = c 1 λ 1 + c 2 λ 2 + … + c k λ k = v 1(6).

. . . . . . . . . . . . . . . . . .uk-1 = c1λk1−1 + c2λk2−1 +K+ c k λkk−1 = vk-1Покажем, что для любых v0, v1, … , vk-1 данная система уравнений всегда разрешимаотносительно c1, c2, … , ck . Определитель этой системы есть определитель Вандермондаи согласно (7, стр. 118).det1λ11λ2..LL1λk..k −1k −1k −1λ1λ2L λk= ∏ (λ i − λ j ) ≠ 0i< jсогласно предположению о корнях λ1, … , λk . Отсюда и следует утверждение. ♦ В качестве примера рассмотрим рекуррентное соотношение (3). Имеем характеристическиймногочленP(x) = x2 - x -1Его корни равны λ1 =1+ 51− 5, λ2 =, Общее решение имеет вид2252n1 + 5 1 − 5  + c2 un = c1  2  2 nСистема уравнений для констант c1, c2 :1 + 5 1 − 5  + c2 =1c1  2  2 221 + 5 1 − 5  + c2  =1c1  2  2 1Откуда получаем c1 =5, c2 = -15.Пусть теперь λ - корень кратности r характеристического многочлена P(x). Аналогичнопредыдущему доказываетсяТеорема 4.

Последовательности c 1λn , c 2 nλn , K , c r n r −1λn , n = 0, 1, … для произвольных констант c1, … , cr из C удовлетворяют соотношению (2).Теорема 5. Пусть характеристический многочлен P(x) имеет корни λ1, … , λsкратностей r1, … , rs (r1 + … + rs = k) . Тогда общее решение рекуррентного соотношения(2) имеет видun = ∑ si =1 (c i1 + c i2 n +K+ c ir i n ri −1 ) λni , c ij ∈ C(7)Укажем еще одно полезное свойство линейных рекуррентных соотношений.Теорема 6.

Характеристики

Список файлов книги