Рекуррентные соотношения. Разбиения множеств. Лексикографическое упорядочение перестановок

Лекция №8. Рекуррентные соотношения. Разбиения множеств. Лексикографическое упорядочение перестановок Золотая пропорция. Последовательность Фибоначчи. Определение 1. Говорят, что точка С делит отрезок AB в золотой |AC| пропорции (в золотом сечении), если |AB| = |AC| |CB| . Обозначим { |AB| |AC| = t, |AC| |CB| = t. |AB| |AC| = t > 0. Вычислим значение t: { { |AB| = t|AC|, |AC| + |CB| = t|AC|, ⇒ ⇒ |AC| = t|CB|. |AC| = t|CB|. Следовательно t|CB| + |CB| = t2|CB|. Так как, |CB| ̸= 0, получаем: t + 1 = t2. Откуда t2 − t − 1 = 0 √ D = 5,√t1,2 = 1±2 5 t = 1+2 5 - искомое значение. 1 Задача о кроликах В 1240 году итальянским математиком Леонардо из Пизы по прозвищу Фибоначчи была предложена так называемая ”задача о кроликах”. Формулируется она следующим образом. На ферму купили одну пару ”молодых” крольчат. Требуется определить, сколько пар кроликов будет на ферме через n месяцев, если известно, что каждая пара ”молодых” кроликов через месяц становится плодоносящей и ежемесячно приносит приплод в виде одной пары кроликов. Считаем, что кролики никогда не умирают. Решение. Обозначим искомое число через fn. Ясно, что каждый месяц на ферме имеются ”молодые” и ”старые” кролики. Поэтому общее число кроликов через n месяцев после приобретения одной пары крольчат на ферму есть сумма числа ”молодых” и ”старых” кроликов: fn = On + Yn, где On - количество пар ”старых” кроликов через n месяцев, а Yn количество пар ”молодых” кроликов через n месяцев. Аналогично через n + 1 месяцев fn+1 = On+1 + Yn+1. Очевидно, что ”молодых” кроликов в каждом рассматриваемом месяце будет на ферме столько же, сколько имелось ”старых” кроликов в предыдущий месяц. Следовательно Yn+1 = On. 2 Все ”старые” кролики в предыдущем месяце останутся ”старыми” и в рассматриваемом месяце (кролики никогда не умирают). Кроме того, все ”молодые” в предыдущем месяце кролики через месяц становятся ”старыми”. Поэтому общее число пар ”старых” кроликов на ферме через n + 1 месяцев равно On+1 = On + Yn = fn. Рассуждая аналогичным образом, имеем далее fn+2 = On+2 + Yn+2, где Yn+2 = On+1 = fn и On+2 = On+1 + Yn+1 = fn+1. Тогда окончательно получаем fn+2 = fn+1 + fn. Здесь f0 = 0, f1 = 1. Полагая n = 0, 1, 2, ... получим ряд чисел Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... Решение линейных рекуррентных соотношений Если для некоторой числовой последовательности задано рекуррентное соотношение, то имеются проблемы, связанные с тем, что для вычисления любого члена такой последовательности необходимо вычислить все предыдущие. Поэтому для быстрого вычисления любого элемента числовой последовательности стремятся получить формулу для его вычисления в явном виде, т.е. как функцию номера вычисляемого элемента в рассматриваемой числовой последовательности. 3 Поэтому, если получено рекуррентное соотношение, его целесообразно использовать для построения упомянутой функции. Такая задача легко разрешима для рекуррентного соотношения с постоянными коэффициентами. Методику поиска искомой функции предварительно рассмотрим на примере. Предположим, что решение рекуррентного соотношения имеет вид: fn = pn. Откуда fn+1 = pn+1, fn+2 = pn+2. Тогда соотношение fn+2 = fn+1 + fn примет вид pn+2 = pn+1 + pn. Разделив обще части на pn ̸= 0, получим p2 = p + 1, p2 − p − √1 = 0, p1,2 = 1±2 5 . Тогда общее решение рекуррентного соотношения имеет вид √ √ 1− 5 n 1+ 5 n ) + C2 ( ) . fn = C1pn1 + C2pn2 = C1( 2 2 Используем начальные условия f0 = 0, f1 = 1 для нахождения коэффициентов C1 и C2 . { f0 = C1 + C2 = 0, f1 = √ 1+ 5 C1 ( 2 ) + √ 1− 5 C2 ( 2 ) = 1. C1 = −C√2 √ 1+ 5 1− 5 − C2( 2 √) + C2( √ 2 )= 1 C2 5 + 1 − 5) = 1 ⇒ C2 = 2 (−1 − √ 1+ 5 n ( 2 ) fn = · − чисел Фибоначчи. √1 5 √1 5 · √ 1− 5 n ( 2 ) − 4 −1 √ , C1 5 = √1 . 5 формула Бине для вычисления В общем случае линейное рекуррентное соотношение с постоянными коэффициентами имеет вид: xn = an−1xn−1 + an−2xn−2 + ... + an−k xn−k , где an−1, an−2, ..., an−k − некоторые постоянные коэффициенты, x0, x1, ..., xk−1− начальные значения последовательности. Решение будем искать в виде xn = pn; подставляя это выражение, получаем полином k-й степени: pn = an−1pn−1 + an−2pn−2 + ... + an−k pn−k . Умножив обе части равен1 ства на pn−k получаем pk = an−1pk−1 + an−2pk−2 + ... + an−k . Это уравнение имеет k корней p1, p2, ..., pk . Если эти корни вещественные и различные, то общее решение будем искать в виде k ∑ n n n xn = C1p1 + C2p2 + ... + Ck pk = Cipni, где неизвестные коэффиi=1 циенты Ci находим, используя начальные условия, которые позволяют составить систему k линейных уравнений относительно этих коэффициентов. Разбиение множеств. Понятия разбиения множества на подмножества мы рассматривали в связи с отношениями эквивалентности. Изучим это понятие далее. Обозначим через S(n, m) число разбиейний n-элементного множества на m блоков. Число S(n, m) называется числом Стирлинга второго рода. 5 Пример 1. Пусть M={a,b,c,d}. Найти число разбиений этого множества на 2 блока. {a}, {b, c, d} {a, b}, {c, d} {b}, {a, c, d} {a, c}, {b, d} {c}, {a, b, d} {a, d}, {b, c} {d}, {a, b, c} Тогда S(4, 2) = 7. Из определения числа Стирлинга второго рода вытекают свойства S(n, m): 1)S(0, 0) = 1, 2)S(n, n) = 1, 3)S(n, 0) = 0, при n > 0, 4)S(n, m) = 0, при m > n. Теорема 1. ∀n, m ∈ N S(n, m) = S(n − 1, m − 1) + m · s(n − 1, m). Доказательство. Положим для определенности, что множество имеет вид {1, 2, ..., n}. Все разбиения множества разделим на 2 части: C1 - разбиения, куда выходит блок {n}; C2 - остальные разбиения. Тогда |C1| = S(n − 1, m − 1), |C2| = m · s(n − 1, m). Общее число S(n, m) разбиений множества на n блоков равно S(n, m) = |C1| + +|C2| = S(n − 1, m − 1) + m · s(n − 1, m). Теорема доказана. Рекуррентная формула, доказанная в теореме, позволяет последовательно вычислять все числа Стирлинга второго рода при рас6 тущих m и n. Значения чисел Стирлинга для n меньших или равных 8 представлены в таблице. Пример 2. S(4, 2) = S(3, 1) + 2 · S(3, 2) = [S(2, 0) + 1 · S(2, 1)] + 2[S(2, 1) + 2 · S(2, 2)] = 3 · S(2, 1) + 4 · 1 = 3[S(1, 0) + 1 · S(1, 1)] + 4 = 3 + 4 = 7. Для вычисления чисел Стирлинга второго рода существует явная формула 1 S(n, m) = m! n ∑ 1 +n2 +...+nm n! n !n !...nm! =n,n >0 1 2 i Определение 2. Число всех разбиений n-элементного множества назывется числом Белла и обозначается B(n), B(0) = 1. Теорема 2. n ∑ B(n) = S(n, m), при n ≥ 1. m=0 Числа Белла приводятся в последнем столбце таблицы. 7 Четность перестановок Определение 3. Говорят, что пара (i, j) образует инверсию в перестановке (...i...j...), если i > j. Определение 4. Перестановка (i1i2...in) называется четной, если количество инверсий в перестановке четное. В противном случае ее называют нечетной. Пример 3. В перестановке (5 2 3 1 4) инверсии образуют пары (5,2), (5,3), (5,1), (5,4), (2,1), (3,1). Всего пар 6, следовательно перестановка четная. Определение 5. Переход от перестановки (...i...j...) к перестановке (...j...i...) называется транспозицией и обозначается (ij). Теорема 3. Все перестановки n-элементного множества можно расположить в таком порядке, что каждая следующая будет получаться из предыдущей одной транспозицией, причем начать можно с любой. Доказательство. Доказательство проведем индукцией по n. При n = 2 имеем две перестановки (1 2) и (2 1), причем вторая получается из первой одной транспозицией. Пусть утверждение справедливо для n − 1-элементного множества. 8 Рассмотрим перестановки (i1i2...in) при фиксированном i1. Таких перестановок (n−1)! и, по предположению индукции, их можно упорядочить как требуется: (i1i2...in) → (i1i2...in−1) → ... → (i1in...i2) {z } | (n − 1)! Далее меняем i1 на i2 в последней перестановке и упорядочиваем перестановки (i2in...i1) при фиксированном i2. По предположению индукции их так же будет (n − 1)! и т.д. Всего перестановок будет (n − 1)! · n = n!, и они удовлетворяют утверждению теоремы. Следствие. Так как всякая транспозиция меняет четность перестановки, то из теоремы следует, что количество четных и нечентных перестановок одинаково и равно n!/2. Лексиграфическое упорядочение перестановок. Определение 6. Перестановка (i1i2...in) лексиграфически предшествует перестановке (j1j2...jn), если существует такое m, что ik = jk для 1 ≤ k < m и im < jm. Обозначение: (i1i2...in) ≤ (j1j2...jn). Пример 4. (2 1 3 4 5) ≤ (2 1 4 3 5). Алгоритм лексиграфического упорядочения. 9 1. Находим упорядоченный по убыванию ”хвост” перестановки наибольшей длины. Если ”хвост” совпадает со всей перестановкой, то конец алгоритма, иначе шаг 2; 2. Элемент, предшествующий ”хвосту” меняем с наименьшим элементом ”хвоста” большим его; элементы ”хвоста” упорядочиваем в порядке возрастания и возвращаемся к шагу 1. Пример 5. Приведем пример выполнения алгоритма лексикографического упорядочения перестановок трехэлементного множества {1,2,3}. (123) → (132) → (213) → (231) → (312) → (321). Теорема 4. При лексиграфическом упорядочении номер перестановки (i1i2...in) вычисляется по формуле N = a1 · (n − 1)! + a2 · (n − 2)! + ... + an−1 · 1!, где aj - количество элементов, меньших ij и стоящих правее его (0 ≤ aj ≤ n − j). Пример 6. Определить номер перестановки (2 3 1). Для этой перестановки a1 = 1, a2 = 1, a3 = 0. Следовательно N = 1 · 2! + 1 · 1! = 2 + 1 = 3. Пример 7. Восстановить перестановку (i1i2i3i4) 4-x элементного множества по ее номеру N=5. 10 Запишем номер перестановки в 3-факториальной системе счисления: 5 = 0 · 3! + 2 · 2! + 1 · 1!. Таким образом a1 = 0, a2 = 2, a3 = 1. Искомая перестановка имеет вид (1 4 3 2). 11