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

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

). Требуется рассадить их так, чтобы

никакие два врага не сидели рядом. Показать, что это можно сделать

P

n
k

=0

(

−

1)

k

C

k

n

2

k

(2

n

−

k

)!

способами.

3.147. Сколькими способами можно расположить за круглым столом

n

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

никакие двое супругов не сидели рядом?

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

k

элементов имеет множество из

n

элементов?

3.149. Пусть

B

=

{

b

1

, . . . , b

n

}

произвольное множество. Обозначим

B

r

n

множество размещений без повторений из

n

по

r

. Введем на этом

множестве отношение по правилу: размещения

(

b

i

1

, . . . , b

i

r

)

и

(

b

j

1

, . . . , b

j

r

)

связаны отношением

Φ

, если они состоят из одних и тех же элементов

и отличаются друг от друга только порядком этих элементов. Показать,
что отношение

Φ

является отношением эквивалентности, построить со-

ответствующее ему разбиение множества

B

r

n

на классы эквивалентно-

сти, найти индекс этого разбиения.

3.150. Обозначим

B

(

n

)

множество различных перестановок из эле-

ментов множества

B

=

{

b

1

, . . . , b

n

}

. Введем на

B

(

n

)

отношение по пра-

вилу: перестановки

(

b

i

1

, . . . , b

i

r

)

и

(

b

j

1

, . . . , b

j

r

)

связаны отношением

Ψ

,

если одна получается из другой сдвигом ее элементов (например, пере-
становки

(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

+ 2) =

a

1

f

(

n

+ 1) +

a

2

f

(

n

)

,

(4

.

1)

где

f

(

n

)

— неизвестная функция, определенная на множестве натураль-

ных чисел

N

со значениями в

R

,

a

1

,

a

2

— вещественные числа.

Из вида ЛРС

(4

.

1)

следует, что для вычисления значения функ-

ции

f

при фиксированном значении аргумента необходимо и достаточно

знать

f

(1)

и

f

(2)

. Условия

f

(1) =

a,

f

(2) =

b

(4

.

2)

называются начальными условиями для ЛРС

(4

.

1)

.

Рассмотрим в качестве примера ЛРС

f

(

n

+ 2) = 5

f

(

n

+ 1)

−

6

f

(

n

)

.

(4

.

3)

Если

f

(1) = 0

,

f

(2) = 1

, то

f

(3) = 5

f

(2)

−

6

f

(1) = 5

,

f

(4) = 5

f

(3)

−

−

6

f

(2) = 19

,

f

(5) = 5

f

(4)

−

6

f

(3) = 65

и т. д.

Нетрудно убедиться, что и в случае произвольных начальных усло-

вий (4.3) значение функции

f

при любом фиксированном

n

∈

N

одно-

значно определяется из ЛРС.

Решением ЛРС называется функция

f

(

n

) (

f

:

N

→

R

)

, при под-

становке которой в (4.1) получается равенство, истинное при всех

n

∈

N

.

Функция

f

(

n

) = 3

n

является решением ЛРС (4.3), так как, положив

f

(

n

) = 3

n

,

f

(

n

+ 1) = 3

n

+1

,

f

(

n

+ 2) = 3

n

+2

в уравнении (4.3), получим

тождество:

3

n

+2

= 5

·

3

n

+1

−

6

·

3

n

.

Частным решением ЛРС (4.1) называется решение, удовлетворя-

ющее начальным условиям (4.2)

.

В дальнейших рассуждениях используется очевидный факт: при лю-

бых

a

,

b

,

a

1

,

a

2

∈

R

задача (4.1), (4.2) имеет единственное решение,

другими словами, частное решение всегда единственно.

Общим решением ЛРС (4.1) называется вещественная функция

f

(

n, C

1

, C

2

)

, зависящая от натурального аргумента

n

и двух веще-

ственных произвольных постоянных

C

1

и

C

2

, такая , что: 1) при

конкретных значениях произвольных постоянных

C

0

1

и

C

0

2

функция

52

ϕ

(

n

) =

f

(

n, C

0

1

, C

0

2

)

является частным решением ЛРС (4.1); 2) любое

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

a

и

b

, получается из

f

(

n, C

1

, C

2

)

при опре-

деленных значениях

C

1

и

C

2

, которые зависят от

a

и

b

.

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

Лемма

.

Пусть

f

1

(

n

)

и

f

2

(

n

)

— решения ЛРС (4.1), тогда их ли-

нейная комбинация

ϕ

(

n

) =

β

1

f

1

(

n

) +

β

2

f

2

(

n

)

, где

β

1

и

β

2

— произ-

вольные вещественные числа, также является решением ЛРС

(4

.

1)

.

Доказательство. Так как

f

1

(

n

)

и

f

2

(

n

)

являются решениями ЛРС

(4.1), то имеют место тождества

f

1

(

n

+ 2)

≡

a

1

f

1

(

n

+ 1) +

a

2

f

1

(

n

)

,

∀

n

∈

N

,

f

2

(

n

+ 2)

≡

a

1

f

2

(

n

+ 1) +

a

2

f

2

(

n

)

,

∀

n

∈

N

.

Умножим первое тождество на

β

1

, а второе — на

β

2

и сложим по-

лученные выражения, в результате имеем:

β

1

f

1

(

n

+2)+

β

2

f

2

(

n

+2)

≡

a

1

(

β

1

f

1

(

n

+1)+

β

2

f

2

(

n

+1))+

a

2

(

β

1

f

1

(

n

)+

β

2

f

2

(

n

))

,

откуда следует, что функция

ϕ

(

n

) =

β

1

f

1

(

n

) +

β

2

f

2

(

n

)

является реше-

нием ЛРС (4.1). Лемма доказана.

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

λ

2

=

a

1

λ

+

a

2

(4

.

4)

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

.

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

Теорема (об общем решении ЛРС в случае простых корней

характеристического уравнения)

.

Пусть

λ

1

и

λ

2

— различные ве-

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

f

(

n, C

1

, C

2

) =

C

1

λ

n

−

1

1

+

C

2

λ

n

−

1

2

.

(4

.

5)

Доказательство. Покажем, что функция

f

i

(

n

) =

λ

n

−

1

i

, i

= 1

,

2

, яв-

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

f

i

(

n

)

в (4.1) получаем:

λ

n

+1

i

=

a

1

λ

n
i

+

a

2

λ

n

−

1

i

,

(4

.

6)

что равносильно равенству:

λ

2

i

=

a

1

λ

i

+

a

2

, истинность которого выте-

кает из предположений теоремы. Функция

f

(

n, C

1

, C

2

)

в равенстве (4.5)

53

представляет собой линейную комбинацию решений

f

i

(

n

)

,

i

∈ {

1

,

2

}

и

в силу доказанной выше леммы также является решением ЛРС (4.1).

Пусть

ψ

(

n

)

— произвольное частное решение ЛРС (4.1), удовлетво-

ряющее начальным условиям (4.2). Найдем

C

1

и

C

2

из равенств:

(

f

(1

, C

1

, C

2

) =

C

1

+

C

2

=

a,

f

(2

, C

1

, C

2

) =

C

1

λ

1

+

C

2

λ

2

=

b.

Последнее представляет собой линейную алгебраическую систему

второго порядка с неизвестными

C

1

и

C

2

. Решая ее, находим

C

1

=

aλ

2

−

b

λ

2

−

λ

1

,

C

2

=

aλ

1

−

b

λ

1

−

λ

2

.

(4

.

7)

Здесь мы воспользовались тем, что

λ

1

и

λ

2

различны, поэтому

λ

1

−

λ

2

6

= 0

.

Частные решения

ψ

(

n

)

и

f

(

n,

aλ

2

−

b

λ

2

−

λ

1

,

aλ

1

−

b

λ

1

−

λ

2

)

удовлетворяют одним

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

ψ

(

n

) =

f

(

n,

aλ

2

−

b

λ

2

−

λ

1

,

aλ

1

−

b

λ

1

−

λ

2

)

.

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

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

Рассмотрим случай, когда

λ

0

— двухкратный корень характеристи-

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

a

1

= 2

λ

0

, a

2

=

−

λ

2

0

.

(4

.

8)

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

.

Пусть

λ

0

6

= 0

— двухкратный корень характеристического уравнения

(4.4), тогда общее решение ЛРС (4.1) находится по формуле

f

(

n, C

1

, C

2

) = (

C

1

+

C

2

n

)

λ

n

−

1

0

.

(4

.

9)

Доказательство. Покажем, что функция

ϕ

(

n

) =

nλ

n

−

1

0

является ре-

шением ЛРС (4.1). Подставляя

ϕ

(

n

)

в (4.1) и учитывая равенства (4.8),

получим

(

n

+ 2)

λ

n

+1

0

= 2

λ

n

0

−

λ

2

0

nλ

n

−

1

0

,

что равносильно равенству

(

n

+ 2)

λ

2

0

= 2

λ

2

0

(

n

+ 1)

−

λ

2

0

n

, истинность

которого при всех

n

очевидна. Формула (4.9) задает решение ЛРС (4.1),

так как является линейной комбинацией решений

λ

n

−

1

0

и

nλ

n

−

1

0

.

54

Повторяя рассуждения предыдущей теоремы, находим постоянные

C

1

и

C

2

из уравнений

C

1

+

C

2

=

a

,

C

1

λ

0

+ 2

C

2

λ

0

=

b

. Так как

λ

0

6

= 0

,

то

C

1

=

2

aλ

0

−

b

λ

0

,

C

2

=

b

−

aλ

0

λ

0

. Мы получили, что решение задачи (4.1),

(4.2) в случае кратного корня

λ

0

характеристического уравнения (4.4)

находится по формуле:

ψ

(

n

) =

2

aλ

0

−

b

λ

0

+

n

b

−

aλ

0

λ

0

λ

n

−

1

0

.

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

§ 5. Соотношение Фибоначчи

Рекуррентное соотношение

F

(

n

+ 2) =

F

(

n

+ 1) +

F

(

n

)

(4

.

10)

известно как соотношение Фибоначчи. Характеристическое уравнение
для соотношения (4.10) имеет вид:

λ

2

=

λ

+ 1

. Корни характеристиче-

ского уравнения

λ

1

=

1+

√

5

2

,

λ

2

=

1

−

√

5

2

. Таким образом, общее решение

соотношения Фибоначчи находится по формуле:

F

(

n

) =

C

1

1 +

√

5

2

n

−

1

+

C

2

1

−

√

5

2

n

−

1

.

(4

.

11)

Числами Фибоначчи называется решение соотношения (4.10), удо-

влетворяющее начальным условиям

F

(1) = 0

,

F

(2) = 1

. Полагая в

формуле (4.11)

n

= 1

и

n

= 2

, получим для

C

1

и

C

2

систему уравне-

ний:

C

1

+

C

2

= 0

,

√

5

2

(

C

1

−

C

2

) = 1

,

откуда находим

C

1

=

−

C

2

=

1

√

5

. Поэтому

F

(

n

) =

1

√

5

1 +

√

5

2

n

−

1

−

1

−

√

5

2

n

−

1

.

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

n

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

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

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

ния

f

(

n

+ 2) =

a

1

f

(

n

+ 1) +

a

2

f

(

n

)

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

55