Лупаренко_ Комбинаторика

f (t) = (1+ x1t + x12t 2 )(1+ x2t + x22t2 )(1+ x3t ) = 1+ ( x1 + x2 + x3 )t +

+ ( x12 + x1 x2 + x1 x3 + x2 x3 + x22 )t 2 + ( x12 x2 + x12 x3 + x1 x22 + x1 x2 x3 + x22 x3 )t3 + + ( x12 x22 + x12 x2 x3 + x1 x22 x3 )t4 + x12 x22 x3t5 .

Если	положить	x1 = x2 = x3 = 1 ,	то	получим
f (t) = 1 + 3t + 5t2 + 5t3 + 3t 4 + t5 . Здесь коэффициент a			равен числу сочетаний
		1
из трех по одному элементу не более чем с двумя повторениями, a2				- из трёх

элементов по два не более чем с двумя повторениями, a3 - из трех по три

элемента с ограничениями, что первый и второй элемент могут встречаться не более двух раз, а третий не более одного раза. Если же не приравнивать

x	= x		= x		= 1 ,		то,			например,		коэффициент	при	t3 ,	равный
1		2		3
x2 x		+ x2 x			+ x x2		+ x x x			+ x2 x , показывает «качественный»				состав r -
1	2		1	3	1	2	1	2	3	2	3

сочетаний с указанными повторениями: 112, 113, 122, 123, 223. аналогично коэффициент при t5 - число r - сочетаний из трех элементов по пять, но с повторениями, тогда такое возможно a5 = x12 x22 x3 : 11223.

Производящая функция для сочетаний из n по r с неограниченным

числом повторений.

Найдем производящую функцию для сочетаний n элементов по r с условием, что хотя бы один элемент каждого вида появится в выборке. Очевидно, что fa (t) в этом случае будет иметь вид:

n − ∞

f (t) = (t + t2 + ... + t k + ...)n = t (1+ t + ... + t k −1 + ...) = t n (1− t ) n = t n ∑Cnk+ k −1tk .

k =0

Упростим полученную формулу, сделав в ней замену индекса суммирования n + k = r , получим

(t) =

∞

tk + n =

∞

C r − ntr = C r = C n− r =

∞

C n −1t r =

∞

C n−1t k .

f

a

∑

C k

∑

∑

∑

n+ k −1

r −1

n

n

r −1

k −1

n−1

k =0

r =n

r = n

k =n

Здесь ∑Ckn−−11tk

= 0 . Следовательно, число искомых сочетаний n элементов

k =0

Crn−−11 при

по r равно нулю при

r < n и

r ³ n .

Подобным же образом в

производящей функции можно учесть и другие требования, налагаемые на выборки.

51

ЛЕКЦИЯ 8.

МЕТОД РЕКУРРЕНТНЫХ СООТНОШЕНИЙ.

Этот метод, как известно, позволяет находить значения некоторой функции для заданной величины аргумента через меньшие значения аргументов. В комбинаторике метод дает возможность находить решение комбинаторной задачи для n предметов через решение аналогичной задачи для меньшего числа предметов с помощью некоторого соотношения,

называемого рекуррентным соотношением.

Этот метод хорошо известен из курса школьной математики, где он применялся для нахождения сумм арифметической и геометрической прогрессии, при нахождении n -го члена этих прогрессий:

-арифметическая прогрессия:

a		= a	n−1	+ d; a = a + d ×(n -1); S		=	a1 + an	× n =	2a1 + d ×(n -1)	× n
	n				n
				n 1		2		2

-геометрическая прогрессия:

b = b × q; a = b × qn−1; S =			b1 ×(1- qn )	.
n n−1	n 1	n	1 - q

Рассмотрим некоторые примеры.

Ряд чисел Фибоначчи. Этот ряд задается следующими соотношениями:

a1 = a(1) = 1; a2 = a(2) = 1; an = an−1 + an− 2 , n > 2 .

Используя эти соотношения получим последовательность чисел,

которая известна под названием последовательность чисел Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... .

Квадраты натуральных чисел. Рассмотрим последовательность квадратов натуральных чисел:

a1	= a(1) = 12 ;	a2 = a(2) = 22 ;...; an = a(n) = n2 ,... .
Используя формулу сокращенного умножения (a + b)2 = a2 + 2ab + b2
получим такую рекуррентную формулу:
	an+1 = (n +1)2 = n2 + 2n +1 = an + 2n +1.
Используя её можно находить квадраты чисел, не выполняя сложных
вычислений.	Например,	если	известно,	что	152 = 225 ,	то

162 = (15 +1)2 = 152 + 2 ×15 +1 = 225 + 30 +1 = 256 .

Аналогично можно получить формулу для кубов натуральных чисел (найти самостоятельно).

52

Сочетания с повторениями.

Пусть

число

комбинаций из

n

элементов по

k

с

повторениями

равно

f k . Тогда каждая комбинация из n по k элементов включает или нет

n

элемент a . Число

комбинаций, которые не включают

элемент

a

с

повторением равно

fnk−1 . Число комбинаций, которые включают элемент a

с

повторением равно 1× fnk −1 .

Следовательно, всего сочетаний с повторением

будет:

fnk = fnk−1 + fnk −1 .

Построенное

рекуррентное

соотношение

дает

возможность

найти

f k . Действительно,

n

fnk = fnk

1 + fnk −1

= fnk −1 + (

fnk −11 + fnk

2 )

= fnk −1 + fnk −11 +

( fnk −21

+ fnk 3 ) =

−

−

−

−

−

−

= f k −1

+ f k −1 + f

k −1

+ ... + f k −1 + f k .

(8.1)

n

n−1

n− 2

2

1

Очевидно,

что

f 1

= n

и

f k

= 1 .

Положив в формуле (8.1)

k = 2 ,

n

1

получим:

+ ... + f 1 + f k = n + (n -1) + (n - 2) + ... + 2 +1 =

f 2 = f 2

+ f 1

= f 1 + f 1

+ f 1

n

n −1

n

n

n−1

n− 2

2

1

= {арифм. прогрессия} =

1+ n

× n =

n × (n +1)

= Cn2+1 .

Далее, положив k = 3 , получим

2

2

f 3

= f

3

+ f

2 = f 2

+ f

2

+ f 2

+ ... + f 2

+ f 3

=

n

n−1

n

n

n−1

n−2

2

1

= C 2

+ C 2

+ C 2

+ ... + C 2

+ C 2

= C

3

n+1

n

n−1

3

2

n+ 2

И так далее получим, что

fnk

= Cnk+ k −1 .

Однородные линейные рекуррентные соотношения.

Рекуррентным соотношением k -го порядка называется формула,

позволяющая выражать значения члена последовательности с номером n (n > k) через члены этой последовательности с номерами n -1, n - 2,..., n - k .

Решением рекуррентного соотношения называется числовая последовательность, обращающая его в верное равенство при подстановке в него формулы общего члена последовательности.

Начальными условиями рекуррентного соотношения k -го порядка

называются первые k членов последовательности, являющейся решением данного рекуррентного соотношения.

Линейным однородным рекуррентным соотношением k -го порядка с постоянными коэффициентами называется соотношение вида:

xn+ k = a1 × xn+ k −1 + a2 × xn + k −2 + ... + ak × xn .

(8.2)

53

Общим решением соотношения (8.2) называется такое его решение, которое содержит k произвольных постоянных, путём подбора которых можно удовлетворить любым начальным условиям.

Характеристическим уравнением соотношения (8.2) называется уравнение:

λ k

= a1 × λ k −1 + a2 ×λ k − 2 + ... + ak

(8.3)

Теорема 8.1. Общее решение соотношения (8.2) имеет вид:

xn = A1 + A2 + ... + Ap , где

Ai = Ci

×λ n ,

если λ - действительный корень первой кратности уравнения (8.3), где Ci

-

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

Ai = λ n ×(Ci,1 + n ×Ci ,2

+ n2

×Ci,2 + ... + nm −1 ×Ci,m ) ,

если

λ -

действительный корень кратности m

уравнения

(8.3),

где

Ci,1 , Ci,2 ,...,Ci,m

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

r ×(cosϕ ± i sinϕ )

Ai = r n ×(cos nϕ × Di + sin nϕ × Ei ) ,

если

-

комплексно-сопряженная

пара,

каждый

член

которой является корнем первой кратности уравнения

(8.3)

и Di , Ei

-

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

Ai

= r n × (cos nϕ ×(Di,1

+ n × Di,2

+ ... + nm−1 × Di,m ) +

,

+ sin nϕ ×(Ei ,1 + n × Ei ,2

+ ... + nm−1 × Ei,m ))

если

r ×(cosϕ ± i sin ϕ )

-

комплексно-сопряженная

пара,

каждый

член

которой

является

корнем кратности

m

уравнения

(8.3)

и

Di,1 , Di,2 ,..., Di,m , Ei,1 , Ei,2 ,..., Ei,m - произвольные постоянные.

Например:

1. Найти общее решение рекуррентного соотношения 5-го порядка

xn+5 = 4 × xn+ 4 - 4 × xn+3 - 2 × xn+ 2 + 5 × xn+1 - 2 × xn .

Решение.

Запишем характеристическое уравнение данного соотношения:

λ 5 - 4λ 4 + 4λ3 + 2λ 2 - 5λ + 2 = 0 .

Непосредственной подстановкой убеждаемся, что λ1

= 1 - корень

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

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

на λ −1 по схеме Горнера:

1

-4

4

2

-5

2

1

1

-3

1

3

-2

0

54

В результате деления получили уравнение четвёртой степени:

λ 4 - 3λ 3 + λ 2 + 3λ - 2 = 0 .

Заметим, что λ2			= 1 является корнем и этого уравнения. Разделим
левую часть уравнения на λ −1 по схеме Горнера:
			1	-3	1		3	-2
	1		1	-2	-1		2	0

Получено уравнение λ 3 - 2λ 2 - λ + 2 = 0 , которое также имеет корень λ3 = 1. Понижаем степень этого уравнения:

	1	-2	-1	2
1	1	-1	-2	0

В результате имеем квадратное уравнение λ 2 - λ - 2 = 0 , которое имеет

корни λ4 = -1 и λ5 = 2 .

По теореме о виде общего решения линейного однородного рекуррентного соотношения с постоянными коэффициентами, запишем его общее решение:

xn = 1n ×(C1 + nC2 + n2C3 ) + (-1)n C4 + 2n ×C5 ; . xn = C1 + nC2 + n2C3 + (-1)n C4 + 2n ×C5 .

Ответ: xn = C1 + nC2 + n2C3 + (-1)n C4 + 2n ×C5 .

2. Найти общее решение рекуррентного соотношения 5-го порядка

xn+5 = 23 × xn + 4 - 4 × xn+3 - 2 × xn+ 2 + 43 × xn+1 - 8 × xn .

Решение.

Запишем характеристическое уравнение данного соотношения:

λ5 - 23λ 4 + 4λ3 + 2λ 2 - 43λ + 8 = 0 .

Спомощью группировки разложим левую часть на множители:

λ3 ×(λ 2 - 23λ + 4) + 2 (λ 2 - 23λ + 4) = 0 .

или

(λ3 + 2) ×(λ 2 - 23λ + 4) = 0 .

Рассмотрим два случая:

iπ (1+ 2k )

1) λ	3	+ 2 = 0 λ	3	= -2 λ	3	= 2 ×e	3	, k Î Z .

55

Если k = 3n +1 , то λ = -32 , при k = 3n и k = 3n -1 получаем пару

комплексно-сопряженных чисел с модулями, равными 32 , и аргументами

ϕ = ± π . 3

Соответствующие слагаемые в общем решении будут иметь вид:

				n					n	π n	π n
C1 (-	3	2 )			+ (	3	2 )
									C2	cos	+ C3 sin	.
										3	3

2) λ 2 - 23λ + 4 = 0 λ4,5 = 3 ± i .

Модуль и аргумент комплексного числа 3 + i соответственно равны:

r = 2, ϕ = π . 6

Соответствующие слагаемые в общем решении будут иметь вид:

2	n	π n	π n
	C4	cos	+ C5 sin	.
		6	6

В итоге получаем общее решение исходного рекуррентного соотношения. Ответ:

n

n

π n

π n

n

π n

π n

xn

= C1 (-

3

2 )

+ (

3

2 )

+ C3 sin

C2 cos

3

+ 2

C4

cos

+ C5 sin

.

3

6

6

3. Найти решение рекуррентного соотношения 4-го порядка

xn+ 4 = 6 × xn + 2 + 8 × xn+1 + 3× xn +1 с начальными условиями

x0

= 0, x1 = -6, x2 = -4, x3 = -34 .

Решение.

Запишем характеристическое уравнение данного соотношения:

λ 4 - 6λ 2 - 8λ - 3 = 0 .

Непосредственной подстановкой убеждаемся, что λ1 = -1 - корень

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

Понизим степень уравнения, поделив характеристический многочлен на λ +1 по схеме Горнера:

	1	0	-6	-8	-3
-1	1	-1	-5	-3	0

Врезультате деления получили уравнение третьей степени:

λ3 - λ 2 - 5λ - 3 = 0 .

56

Заметим, что λ2		= −1 также является корнем и этого уравнения.
Разделим левую часть уравнения на λ +1 по схеме Горнера:
			1		-1	-5	-3
	-1		1		-2	-3	0
Получено уравнение λ 2 - 2λ - 3 = 0 , которое имеет корни
				λ3	= −1,	λ4 = 3 .
Общее решение исходного рекуррентного соотношения имеет вид:

xn = (-1)n ( A + B × n + C × n2 ) + D ×3n .

Учтём начальные условия, получим систему линейных уравнений:

A + D = -34

-A - B - C + 3D = -6	.
A + 2B + 4C + 9D = -4

− A − 3B − 9C + 27D = −34

Решив эту систему, будем иметь: A = 1, B = 2, C = 0, D = −1 .

Подставив найденные значения констант в формулу общего решения, получим:

xn = (-1)n (1 + 2n + 0 × n2 ) -1×3n

Ответ: xn = (−1)n (1 + 2n) − 3n .

57

ЛИТЕРАТУРА

1.Андерсон, Джейм А. Дискретная математика и комбинаторика. – М.: «Вильямс», 2004. – 960 с.

2.Бондаренко М.Ф. та ін. Комп’ютерна дискретна математика: підручник. – Харків, 2004. – 480 с.

3.Бардачов Ю.М. та ін.. Дискретна математика. Підручник. – 2- ге видання, переробл. і допов. – К.: Вища школа, 2008. – 383 с.

4.Борисенко О.А. Дискретна математика: Підручник. – Суми: ВТД «Університетська книга», 2007. – 255 с.

5.Виленкин Н.Я. Комбинаторика. – М.: «Наука», 1969. – 328 с.

6.Галушкина Ю.И., Марьямов А.Н. Конспект лекций по дискретной математике. – М.: Айрис – пресс, 2007. – 176 с.

7.Капитонова Ю.В. и др. Лекции по дискретной математике. – СПб.: БХВ – Петербург, 2004. – 624 с.

8.Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВ

– Петербург, 2008. – 352 с.

9.Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий. – СПб.: БХВ – Петербург, 2007. – 400 с.

58

СОДЕРЖАНИЕ

Введение…………………………………………..…………………….. 3

Лекция 1. Элементы комбинаторного анализа………….………….... 5

Лекция 2. Размещения, перестановки и сочетания с повторениями.

Лекция 3. Бином Ньютона. Биномиальная теорема. Треугольник Паскаля. Полиномиальная теорема……………………….

Лекция 4. Свойства биномиальных коэффициентов.……………….. 22

Лекция 5.	Метод включений и исключений. …………...………….	30
Лекция 6.	Функция Эйлера. Функция Мёбиуса. ………..…………	39
Лекция 7. Метод производящих функций….………………...……… 46
Лекция 8.	Метод рекуррентных соотношений……………………..	52
Литература……………………………………………………………… 58

12

17

59