Дискретная математика. Методичка. Кацаран

3.140. Определить количество способов разбить n различных предметов на k различных групп, при котором допускаются пустые группы.

3.141. Определить количество способов разбить n различных предметов на k различных групп, при котором существенен порядок элементов в группе.

3.142. Определить количество способов разбить n различных предметов на k различных групп, при котором все группы непустые.

3.143. Определить количество способов разбить n одинаковых предметов на k различных групп, при котором допускаются пустые группы.

3.144. Определить количество способов разбить n одинаковых предметов на k различных групп, при котором каждая группа содержит не менее r предметов.

3.145. Определить количество способов разбить n одинаковых предметов на k различных групп, при котором все группы непустые.

3.146. Задача мажордома. К обеду за круглым столом приглашены n пар враждующих рыцарей ( n ≥ 2 ). Требуется рассадить их так, чтобы никакие два врага не сидели рядом. Показать, что это можно сделать

n супружеских пар так, чтобы мужчины и женщины чередовались и никакие двое супругов не сидели рядом?

3.148. Сколько подмножеств из k элементов имеет множество из n элементов?

3.149. Пусть B = {b1, . . . , bn} произвольное множество. Обозначим Bnr множество размещений без повторений из n по r . Введем на этом множестве отношение по правилу: размещения (bi1 , . . . , bir ) и (bj1 , . . . , bjr ) связаны отношением Φ , если они состоят из одних и тех же элементов и отличаются друг от друга только порядком этих элементов. Показать, что отношение Φ является отношением эквивалентности, построить соответствующее ему разбиение множества Bnr на классы эквивалентности, найти индекс этого разбиения.

3.150. Обозначим B(n) множество различных перестановок из элементов множества B = {b1, . . . , bn}. Введем на B(n) отношение по пра-

вилу: перестановки (bi1 , . . . , bir ) и (bj1 , . . . , bjr ) связаны отношением Ψ , если одна получается из другой сдвигом ее элементов (например, пере-

становки (1, 2, 3, 4) и (3, 4, 1, 2) , (2, 4, 3, 1) и (1, 2, 4, 3) связаны отношением Ψ в отличие от перестановок (1, 2, 3, 4) и (1, 3, 4, 2) . Показать, что отношение Ψ является отношением эквивалентности, построить соответствующее ему разбиение множества B(n) на классы эквивалентности, найти индекс этого разбиения.

51

ГЛАВА 4. ЛИНЕЙНЫЕ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ ВТОРОГО ПОРЯДКА

§ 1. Постановка задачи. Общее и частное решения

Линейным рекуррентным соотношением второго порядка (ЛРС) называется функциональное уравнение вида

где f (n) неизвестная функция, определенная на множестве натуральных чисел N со значениями в R , a1 , a2 вещественные числа.

Из вида ЛРС (4.1) следует, что для вычисления значения функции f при фиксированном значении аргумента необходимо и достаточно знать f (1) и f (2) . Условия

называются начальными условиями для ЛРС (4.1) . Рассмотрим в качестве примера ЛРС

Если f (1) = 0 , f (2) = 1 , то f (3) = 5f (2)−6f (1) = 5 , f (4) = 5f (3)− − 6f (2) = 19 , f (5) = 5f (4) − 6f (3) = 65 и т. д.

Нетрудно убедиться, что и в случае произвольных начальных условий (4.3) значение функции f при любом фиксированном n N однозначно определяется из ЛРС.

Решением ЛРС называется функция f (n) (f : N → R) , при подстановке которой в (4.1) получается равенство, истинное при всех n N .

Функция f (n) = 3n является решением ЛРС (4.3), так как, положив f (n) = 3n , f (n + 1) = 3n+1 , f (n + 2) = 3n+2 в уравнении (4.3), получим тождество: 3n+2 = 5 · 3n+1 − 6 · 3n .

Частным решением ЛРС (4.1) называется решение, удовлетворяющее начальным условиям (4.2).

В дальнейших рассуждениях используется очевидный факт: при любых a , b , a1 , a2 R задача (4.1), (4.2) имеет единственное решение, другими словами, частное решение всегда единственно.

Общим решением ЛРС (4.1) называется вещественная функция f (n, C1, C2) , зависящая от натурального аргумента n и двух вещественных произвольных постоянных C1 и C2 , такая , что: 1) при конкретных значениях произвольных постоянных C10 и C20 функция

52

ϕ(n) = f (n, C10, C20) является частным решением ЛРС (4.1); 2) любое частное решение, т. е. решение, удовлетворяющее начальным условиям (4.2) с произвольными a и b , получается из f (n, C1, C2) при определенных значениях C1 и C2 , которые зависят от a и b .

§ 2. Свойства решений

Лемма. Пусть f1(n) и f2(n) решения ЛРС (4.1), тогда их линейная комбинация ϕ(n) = β1 f1(n) + β2 f2(n) , где β1 и β2 произвольные вещественные числа, также является решением ЛРС (4.1) .

Доказательство. Так как f1(n) и f2(n) являются решениями ЛРС (4.1), то имеют место тождества

Умножим первое тождество на β1 , а второе на β2 и сложим полученные выражения, в результате имеем:

β1 f1(n+2)+β2f2(n+2) ≡ a1(β1f1(n+1)+β2f2(n+1))+a2(β1f1(n)+β2f2(n)),

откуда следует, что функция ϕ(n) = β1f1(n) + β2f2(n) является решением ЛРС (4.1). Лемма доказана.

Алгебраическое уравнение второго порядка

называется характеристическим уравнением, соответствующим ЛРС (4.1).

§ 3. Случай простых корней характеристического уравнения

Теорема (об общем решении ЛРС в случае простых корней характеристического уравнения). Пусть λ1 и λ2 различные вещественные корни характеристического уравнения (4.4), тогда общее решение ЛРС (4.1) находится по формуле

ляется решением ЛРС (4.1). При подстановке fi(n) в (4.1) получаем:

что равносильно равенству: λ2i = a1λi + a2 , истинность которого вытекает из предположений теоремы. Функция f (n, C1, C2) в равенстве (4.5)

53

представляет собой линейную комбинацию решений fi(n) , i {1, 2} и в силу доказанной выше леммы также является решением ЛРС (4.1).

Пусть ψ(n) произвольное частное решение ЛРС (4.1), удовлетворяющее начальным условиям (4.2). Найдем C1 и C2 из равенств:

и тем же начальным условиям (4.2) и в силу единственности решения задачи (4.1), (4.2) совпадают:

ψ(n) = f (n, aλ2 − b , aλ1 − b ). λ2 − λ1 λ1 − λ2

Теорема доказана.

§ 4. Случай кратных корней характеристического уравнения

Рассмотрим случай, когда λ0 двухкратный корень характеристического уравнения (4.4). Тогда, используя формулы Виета, получим

Теорема (об общем решении ЛРС в случае кратного корня).

Пусть λ0 6= 0 двухкратный корень характеристического уравнения (4.4), тогда общее решение ЛРС (4.1) находится по формуле

Доказательство. Покажем, что функция ϕ(n) = nλn0 −1 является решением ЛРС (4.1). Подставляя ϕ(n) в (4.1) и учитывая равенства (4.8),

получим

(n + 2)λn0 +1 = 2λn0 − λ20 nλn0 −1,

что равносильно равенству (n + 2)λ20 = 2λ20(n + 1) − λ20 n , истинность которого при всех n очевидна. Формула (4.9) задает решение ЛРС (4.1), так как является линейной комбинацией решений λn0 −1 и nλn0 −1 .

54

известно как соотношение Фибоначчи. Характеристическое уравнение

Отметим, что это последнее выражение при всех натуральных значениях

nпринимает целые неотрицательные значения.

§6. Рекомендации к решению задач

Нахождение общего и частного решений рекуррентного соотноше-

ния

f (n + 2) = a1f (n + 1) + a2f (n)

состоит из следующих шагов:

55

1) выписывается характеристическое уравнение

λ2 = a1λ + a2,

инаходятся его корни λ1 , λ2 ;

2)если λ1 6= λ2 , общее решение ЛРС записывается в виде:

f (n, C1, C2) = C1λn1 −1 + C2λn2 −1;

3) если λ1 = λ2 = λ0 =6 0 , общее решение ЛРС также содержит две произвольные постоянные

f (n, C1, C2) = (C1 + C2 · n)λn0 −1;

4) для нахождения частного решения f (n) , удовлетворяющего условию f (1) = a , f (2) = b , составляется система уравнений с неизвестными C1 и C2 . В случае 2) она имеет вид

для f (n, C1, C2) в случаях 2) или 3) соответственно, получим частное решение ЛРС.

Если λ0 = 0 (это возможно, когда a1 = a2 = 0 ), решение рекуррентного соотношения имеет вид f (n + 2) = 0 . Решением в этом случае

Далее находим частное решение. Система уравнений для C1 и C2

56

F (n + 2) = F (n + 1) + F (n),

удовлетворяющее условию F (1) = F (2) = 1 . Требуется доказать тожде-

Для доказательства воспользуемся методом математической индукции. При n = 1 равенство (4.12) приобретает вид F (1) + F (3) = F (4) , что верно, так как F (3) = F (2) + F (1) = 2 , F (4) = F (3) + F (2) = 3 . Предположим, что равенство (4.12) верно при n = k , т. е.

F (1) + F (3) + . . . + F (2k + 1) = F (2k + 2).

Докажем его для случая n = k + 1 . Действительно, по предположению индукции и из уравнения Фибоначчи получаем:

F (1)+F (3)+. . .+F (2n+1)+F (2k+3) = F (2k+2)+F (2k+2) = F (2k+4),

что и доказывает утверждение.

Пример 4. Построить ЛРС, частные решения которого имеют вид: f1(n) = 5 · 2n и f2(n) = 4 .

Решение. Из вида частных решений искомого рекуррентного соотношения корни его характеристического уравнения λ1 = 2 , λ2 = 1 . Составим квадратное уравнение с указанными корнями

(λ − 2)(λ − 1) = λ2 − 3λ + 2 = 0.

Перепишем его в стандартном виде λ2 = 3λ −2 , откуда находим a1 = 3 , a2 = −2 и запишем ЛРС

f (n + 2) = 3f (n + 1) − 2f (n).

§7. Задачи и упражнения для самостоятельной работы

4.1.Пусть {an} и {bn} две последовательности, члены которых связаны отношениями

an+1 = p1 · an + q1 · bn, bn+1 = p2 · an + q2 · bn,

57

4.2. Обозначим через F (n) решение рекуррентного соотношения Фибоначчи, удовлетворяющее условиям F (1) = F (2) = 1 . Доказать, что:

а) для любых натуральных m и n :

F (m + n) = F (n − 1)F (m) − F (n)F (m + 1) ;

б) для любых m и n = km число F (n) делится на F (m) ; в) два соседних числа взаимно просты;

г) всякое натуральное число может быть однозначно представлено в виде суммы чисел Фибоначчи, такой, что каждое число входит в сумму не более одного раза и никакие два соседних числа не входят вместе;

д) F (1) + F (3) + . . . + F (2n + 1) = F (2n + 2) ; е) 1 + F (2) + F (4) + . . . + F (2n) = F (2n + 1) .

4.3. Линейным рекуррентным соотношением k -го порядка называется соотношение

f (n + k) = a1 f (n + k − 1) + a2f (n + k − 2) + . . . + ak f (n), (20)

где коэффициенты ai , i = 1, k произвольные вещественные числа. Многочлен

называется характеристическим для рекуррентного соотношения (20). Доказать, что:

а) решение рекуррентного соотношения однозначно определяется заданием ее первых k членов;

б) функция f (n) = Cλn0 −1 , где λ0 корень характеристического уравнения (21), C – произвольная постоянная, является решением рекуррентного соотношения (20);

в) если λ1 , . . . , λk простые корни характеристического многочлена (21), то общее решение соотношения (20) имеет вид:

f (n, C1, . . . , Ck) = C1λn1 −1 + C2λn2 −1 + . . . + Ck λnk−1,

где C1 , . . . , Ck произвольные постоянные.

4.4. Найти частные решения ЛРС второго порядка.

1)f (n + 2) = 2893 f (n) − 172 f (n + 1) , f (1) = f (2) = 1 ;

2)f (n + 2) = 16935 f (n) + 132 f (n + 1) , f (1) = 1 , f (2) = 2 ;

3)f (n + 2) = 113 f (n + 1) + 12118 f (n) , f (1) = 2 , f (2) = 1 ;

4)f (n + 2) = 27 f (n + 1) + 498 f (n) , f (1) = 3 , f (2) = 1 ;

5)f (n + 2) = 3581 f (n) + 29 f (n + 1) , f (1) = 1 , f (2) = 0 ;

6)f (n + 2) = 38 f (n + 1) + 1864 f (n) , f (1) = 2 , f (2) = 1 ;

7)f (n + 2) = 28910 f (n) − 173 f (n + 1) , f (1) = f (2) = 1 ;

8)f (n + 2) = 643 f (n) − 14 f (n + 1) , f (1) = f (2) = 1 .

58

4.5. Найти ЛРС второго порядка, решением которого является одна из следующих функций. Каким начальным условиям удовлетворяет это решение?

1)f (n) = 17 − 2 · 3n−1 ;

2)f (n) = 3 · 2n − 1 ;

3)f (n) = 2n − 3n−1 ;

4)f (n) = 5n − 3 · 2n ;

5)f (n) = 12 n−1 + 1 ;

6)f (n) = 5n − 1 ;

7)f (n) = 3n ;

8)f (n) = 3n + 2n−1 .

Литература

1.Лавров И.А. Задачи по теории множеств, математической логике

итеории алгоритмов : учеб. пособие / И.А. Лавров, Л.Л. Максимова. 4-е изд. М. : Физматлит, 2001. 255 с.

2.Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: учеб. пособие для студ. вузов, обуч. по экон. и упр. специальностям и направлениям / Г.И. Москинова. М. : Логос, 2004. 238 с.: ил., табл. (Учебник XXI века). Предм. указ. : с. 227 235. Библиогр. : с. 236.

3.Ежов И.И. Элементы комбинаторики / И.И. Ежов, А.В. Скороход, М.И. Ядренко ; пер. с украинского З.Л. Кулик. М. : Наука, 1977. 79,[1] с. : ил.

4.Гаврилов Г.П. Задачи и упражнения по дискретной математике : учеб. пособие / Г.П. Гаврилов, А.А. Сапоженко. 3-е изд., перераб. М. : Физматлит, 2004. 416 с. : ил., табл. Предм. указ. : с. 414-416.

59

Содержание

Программа курса Дискретная математика . . . . . . . . . . . . . . . . . . . . . . . . .3 Глава 1. Множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 § 1. Определение и способы задания множеств . . . . . . . . . . . . . . . . . . . 6 § 2. Операции над множествами и их свойства . . . . . . . . . . . . . . . . . . . 7 § 3. Мощность конечного множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 § 4. Прямое произведение двух и более множеств . . . . . . . . . . . . . . . . 9 § 5. Булеан множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 § 6. Рекомендации к решению задач. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11 § 7. Задачи и упражнения для самостоятельной работы . . . . . . . . . 13

Глава 2. Бинарные отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 § 1. Определение и способы задания отношений . . . . . . . . . . . . . . . . . 16 § 2. Операции над отношениями. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17 § 3. Свойства отношений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 § 4. Отношение эквивалентности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 § 5. Отношение порядка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 § 6. Рекомендации к решению задач. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21 § 7. Задачи и упражнения для самостоятельной работы . . . . . . . . . 22

Глава 3. Комбинаторика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 § 1. Основные правила комбинаторики . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 § 2. Понятие k -выборки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 § 3. Размещения с повторениями и без повторений. Перестановки

без повторений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 § 4. Сочетания с повторениями и без повторений . . . . . . . . . . . . . . . . 30 § 5. Перестановки с повторениями. Подсчет числа беспорядков .31 § 6. Свойства сочетаний. Бином Ньютона . . . . . . . . . . . . . . . . . . . . . . . . 32 § 7. Общий случай формулы включений и исключений . . . . . . . . . . 33 § 8. Частный случай формулы включений и исключений . . . . . . . . 35 § 9. Применение формулы включений и исключений . . . . . . . . . . . . 36 § 10. Рекомендации к решению задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 § 11. Задачи и упражнения для самостоятельной работы . . . . . . . . 41

Глава 4. Линейные рекуррентные соотношения второго порядка. . . . . .52 § 1. Постановка задачи. Общее и частное решения. . . . . . . . . . . . . . .52 § 2. Свойства решений. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53 § 3. Случай простых корней характеристического уравнения . . . . 53 § 4. Случай кратных корней характеристического уравнения. . . .54 § 5. Соотношение Фибоначчи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 § 6. Рекомендации к решению задач. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55 § 7. Задачи и упражнения для самостоятельной работы . . . . . . . . . 57

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59

60