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

a ×b = p1α1 p2α2 ×...× pmαm q1β1 q2β2 ×...× qrβr

Является каноническим разложением числа ab на простые множители, и поэтому в силу теоремы 6.1

		1				1										1							1						1				1
ϕ (a ×b) = ab 1	-		1-								... 1-										× 1 -					1 -					... 1	-		.
		p1			p2										pm									q1					q2				qr
Но
											1						1									1
	ϕ (a) = a 1						-						1		-							... 1-
											p1							p2								pm
											1						1									1
	ϕ (b) = b 1						-					1		-						... 1			-
									q1								q2								qr
Таким образом,				ϕ(a ×b) = ϕ(a) ×ϕ(b) ,																				то				есть			функция ϕ(n)

мультипликативная.

Определим следующее свойство мультипликативных функций.

Теорема 6.3. Пусть f (x) мультипликативная функция, n = p1α1 p2α2 ×...× pmαm - каноническое разложение числа на простые множители.

Тогда

m

∑ f (d ) = ∏{ f (1) + f ( pi ) + ... + f ( piαi )}

(6.3)

d

n

i =1

Слева в равенстве (6.3) стоит сумма, распространяющаяся на

значения функции

f

для всех делителей числа n , включающих единицу и

само число n .

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

p1β1 p2β2

×...× pmβm , где

Каждый

делитель

числа

n

имеет

вид

0 £ β1 £ α1 ,..., 0 £ βm £ αm . В силу мультипликативности функции f

f ( p1β1

p2β2 ×...× pmβm ) =

f ( p1β1

) f ( p2β2

)×...× f ( pmβm ) .

Сумма всех делителей

α1 α2

αn

( pmβm ) =

∑ f (d ) = ∑∑...∑ f ( p1β1 ) f ( p2β2 )×...× f

d

n

β1 β2

βm

= m { f (1) + f ( p ) + ... + f ( pαi )} .

∏ i i i =1

Например.

Вычислить ∑ϕ(d ) .

d 8

Решение. Имеем

41

∑ϕ(d ) = ϕ(1) +ϕ(2) +ϕ(4) +ϕ (8) = 1 +1 + 2 + 4 = 8 .

d 8

Ответ: ∑ϕ (d ) = 8 .

d 8

Ответ в задаче не является случайным. Имеет место такая теорема.

Теорема 6.4. ∑ϕ(d ) = n .

d n

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

Пусть n = p1α1 p2α2 ×...× pmαm - каноническое разложение числа n на простые множители. Тогда согласно теореме 6.3 имеем

∑

∏{

i

i

}

ϕ(d ) =

m

ϕ(1) +ϕ ( p ) + ... +ϕ ( pαi

=

i =1

)

d

n

m

}

=

∏{

i

i

i

i

i

i =1

1 + ( p -1) +

( p

2

- p ) + ... + ( pαi

- pαi

−1 ) =

m

= ∏ piαi

=n .

i =1

Перечислим в заключение без доказательства еще некоторые

свойства функции Эйлера.

ϕ(qα ) = qα - qα −1

= qα

1

n = 8,

1.

1 -

.

Возьмём

n = 23 ,

q

ϕ(8) = 4 =

3

2

3

1

2

- 2

= 2

1-

= 4 .

2

m

m

1

m

1

2.

ϕ(n) = ∏ϕ ( piαi )

=∏ qiα1 1

-

=n∏ 1 -

.

qi

i =1

i =1

qi

i =1

3.

xϕ ( n)

º 1(mod n) , где n > 0 и НОД(x, n) = 1 . Например,

x = 3, n = 10,

3ϕ (10)

= 34

= 81 = 8 ×10 +1 º 1(mod10) .

Функция Мёбиуса.

чисел функцию μ(n)

Определим

на

множестве

натуральных

следующим образом:

1,

если n = 1,

μ(n) = 0,

если n = qα1 qα2

×...× qαk и $α

i

> 1,

(6.4)

1

2

k

n

, если n = q1 q2 ×...× qk ,

(-1)

42

где n = q1α1 q2α2 ×...× qkαk - разложение аргумента на простые сомножители, такое

же, как для функции Эйлера.

Функция, определяемая равенством (6.4) называется функцией Мебиуса в честь немецкого математика Августа Мебиуса (1790-1868).

Приведём таблицу первых значений функции μ(n) .

	n	Каноническое		μ(n)
		разложение	n
	1			1
	2	2		(−1)1 = −1
	3	3		(−1)1 = −1
	4	4 = 22		0
	5	5		(−1)1 = −1
	6	6 = 2 ×3		(−1)2 = 1
	7	7		(−1)1 = −1
	8	8 = 23		0
	9	9 = 32		0
	10	10 = 2 ×5		(−1)2 = 1
	11	11		(−1)1 = −1
	12	12 = 22 ×3		0

Функция Эйлера выражается через функцию Мёбиуса. Запишем, например, ϕ (60) , используя формулу (6.1). Имеем:

ϕ (60) =	60		60		60		60			60				60				60			60
		-		+		+			+				+			+				-		=
	1		2		3					2 ×3											2 ×3×5
							5							2 ×5 3×5
									= ∑ μ(d )						60		.
									d			60			d

(под знаком суммы перечисляются все делители числа 60).

Внимательное рассмотрение записи ϕ (n) в виде (1) приводит к выводу, что справедлива следующая теорема.

Теорема 6.5. Имеет место равенство
ϕ(n) = ∑ μ(d )			n	,	(6.5)
d		n	d

где в правой части перечисляются все делители числа n .

43

Например. Вычислить ∑ μ(d ) .

d 10

Решение.

Используя таблицу μ(n) , имеем:

∑ μ(d ) = μ(1) + μ(2) + μ(5) + μ(10) = 1 -1 -1 +1 = 0 .

d 10

Теорема 6.6. При n ³ 2 ∑ μ(d ) = 0 .

d n

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

Допустим, что n = q1α1 q2α2 ×...× qkαk . Каждый делитель имеет вид d = q1β1 q2β2 ×...× qkβk , где 0 £ β1 £ α1 ,..., 0 £ βm £ αm . Если хотя бы для одного i

βi ³ 2 , то для такого делителя μ(d ) = 0 . Если μ(d ) ¹ 0 , то делитель d имеет

вид

d = qi1 qi2 ...qik

, где {qi1 qi2 ...qik } некоторое

подмножество

множества

{qi1 qi2

...qim } . Число таких подмножеств

Cmk , а μ (d ) для соответствующего

делителя равно (-1)k . Таким образом,

∑ μ(d ) = 1 - Cm1

+ Cm2 -... + (-1)m Cmm = (1-1)m = 0 .

d

n

6.7. Пусть g -

функция,

Теорема

которая

определена на

множестве натуральных чисел и

f (n) = ∑ g(d ) .

(6.6)

Тогда g

d

n

f

может быть выражена через функцию

с помощью

соотношения

g(n) = ∑

n

μ(d ) f

(6.7)

d

n

d

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

Сделаем сначала следующее замечание: если d

n

, то

n

и c

c

n

и

n

d

. Действительно, так как d

n , то существует натуральное число s

такое,

d

c

n

что n = ds . Из того, что c

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

t

d

такое, что s =

n

= ct . Поэтому n = dct = c(dt) , то есть c

n ,

n

.

d

d

c

44

n

Рассмотрим сумму

∑ μ(d ) f

.

Используя формулу (6.6),

будем

иметь:

n

d

n

d

∑ μ(d ) f

=

∑ μ(d )∑ g(c) = ∑ μ(d )g(c) ,

d

n

d

d

n

c

n

(c,d ) S

d

где в двойной сумме ведётся суммирование по множеству S пар (c, d ) , для

которых d

n и c

n

. Но согласно замечанию, сделанному

выше,

это

d

(c, d ) , для которых

n

.

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

c

n и

d

Поэтому мы можем записать двойную сумму в виде:

c

∑ g(c) ∑ μ(d ) .

c

n

d

n

c

Сумма в круглых скобках равна нулю, когда n ³ 2 (теорема 6.6). Поэтому c

окончательно получим:

g(n)∑ μ(d ) = g(n)μ(1) = g(n) ,

d 1

что и доказывает равенство (6.5).

Теорему 6.7 называют принципом обращения Дедекинда-Лиувилля

в честь немецкого математика Рихарда Дедекинда (1831-1916) и французского математика Жозефа Лиувилля (1809-1882).

По теореме 6.4

∑ϕ(d ) = n .

d n

Применяя принцип обращения Дедекинда-Лиувилля, получим равенство:

ϕ(n) = ∑ μ(d ) n .
d n	d

Это еще одно доказательство теоремы 6.5.

45

ЛЕКЦИЯ 7.

МЕТОД ПРОИЗВОДЯЩИХ ФУНКЦИЙ.

Метод производящих функций не является элементарным, т.к. при его использовании приходится иметь дело с некоторыми понятиями теории функциональных рядов. Метод производящих функций – один из самых развитых теоретических методов комбинаторного анализа и один из самых сильных в приложениях. Его главные идеи были высказаны в конце XVIII в. в работах Лапласа по теории вероятностей. Для случаев с конечным числом исходов аппарат теории вероятностей чисто комбинаторный.

Рассмотрим произведение конечного числа линейных биномов:

n	n
∏(1+ xk t ) = ∑ak t k .
k =1	k =0

В правой части равенства коэффициенты имеют вид:

	n
ak =	∑ xi1 × xi2 ×...× xin .
i1	,i2 ,...,ik =1,
i1	<i2 <...<ik

Это легко проверить, например, для случая малых n .

Пусть n = 2 , тогда:	(1 + x1t )(1 + x2t ) = 1+ x1t	+	x2t
	i1 =1,i2 нет		i2 =1,i1 нет,
			т.к. нет i1 <1

+x x t 2 .

1 2

i1 =1,i2 =1, i1 <i2

Для n > 2 проверка аналогична. В частном случае,				когда xk = 1, k =		1, n	, в
качестве коэффициентов ak получим числа k - сочетаний, т.е.
		n
	(1+ t )n = ∑Cnk tk .
Здесь функция f (t) = (1+ t )n		k =0
		и	числа	Cnk связаны	взаимно-
однозначно.	f (t) = (1+ t )n
Функция		есть	производящая		функция

последовательности Cnk . Производящей функцией последовательности

{ak }	n
	называется сумма степенного ряда fa (t) = ∑ak t k .
	k =0

Оперировать с такой функцией гораздо удобнее и проще, особенно, когда её можно представить в простой аналитической форме. В то же время эти операции доставляют (производят) необходимую информацию о последовательности k - сочетаний. Идея применения метода производящих функций такова: необходимо вычислить все члены некоторой

последовательности {ak } . С помощью рекуррентного соотношения для ak или непосредственно из некоторых комбинаторных соображений вычисляют

46

n
производящую функцию fa (t) = ∑ak t k . Раскладывая затем fa (t)			в ряд и
k =0
находя коэффициенты при tk , тем самым находят a	k	.
Пример 1.
		n
Из формулы бинома Ньютона fa (t) = (1+ t )n = ∑Cnk t k .			Таким
		k =0

образом, последовательность биномиальных коэффициентов имеет

производящую функцию (1 + t )n , т.е. {Cn0 , Cn1 , Cn2 ,..., Cnn } → (1+ t )n .

Пример 2.

Пусть ak

= ak , k = 0,1,... .Тогда

n

n

= 1 + at + a2t 2 + ... + ak t k + ... = 1+ (at ) + (at )2 + ... + (at )k + ... .

∑ak t k

= ∑ak t k

k =0

k =0

Это

бесконечно

убывающая

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

прогрессия

со знаменателем

q = at . Если

q

=

at

< 1, то ряд сходится и его сумма S = fa

(t) =

1

. Итак,

{

}

1

1

− at

1, a, a2 , a3 ,..., ak ,... →

при

at

< 1 .

− at

Пример 3.

1

Рассмотрим формулу бинома Ньютона при действительном

показателе α R :

α (α −1)

α (α −1)(α − 2)...(α − k +1)

(1 + t )α

= 1 + αt +

t 2 + ... +

t k + ... .

2!

k !

Пусть t = −t

и α = −1 , тогда

1

= 1 + t + t

2 + ... + t k + ... , т.е. {1,1,1,...,1,...} →

1

.

Если t = −t

1 − t

1− t

и α = −n , тогда

n (n −1)(n − 2)...(n − k +1)

1

= 1 + nt +

n(n +1)

t2 + ... +

t k

+ ... .

(1− t )n

2!

k !

Но n = Cn1 ,

n(n +1)

= Cn2+1 ,

n (n −1)(n − 2)...(n − k +1)

= Cnk+ k −1 и т.д.

2

k !

Тогда

1

= 1 + C1t + C2 t 2 + C

3

t3 + ... + Ck

tk + ... ,

(1− t )n

n

n+1

n + 2

n+ k −1

т.е.

1, C1 , C

2

,C

3

,...,C k

,...

→

1

.

+

+

−

(1

− t )n

{

n

1 n

2

n

+

k

}

n

1

47

Пример 4.

0 ≤ k

< r,

t

0,

r

Пусть ak =

r

Тогда fa (t) =

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

(

)

r +1

- t

Ck , k ³ r.

1

∞

∞

∞

k = r + i,

∞

∞

fa (t) = ∑ ak t k = ∑ak tk = ∑Ckr tk =

= r, i =

= ∑Crr+i t r +i = t r ∑Crr+i ti =

k =0

k = r

k =r

∞

k

0

i =0

i =0

1

∑Cnk

k 1t k =

,

C

r

C

k

−

r

∞

n

r

=

k

+ −

(1 - t)

t

=

kr

= t r ∑Cri +i ti = k =0

=

.

i

1

(1 - t)

r +1

C

= C

i

=

0

∞

i

i

r

+i

r

+i

∑Cr

+

i t

=

(1

- t)

r 1

i =0

+

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

В комбинаторном анализе чаще всего используют три вида производящих функций:

-обычные степенные.

-экспоненциальные.

-функции Дирихле.

Обычные производящие функции (см. примеры 1-3), представляемые

n

в виде fa (t) = ∑ak t k , соответствуют семействам последовательностей,

k =0

элементы которых являются числами неупорядоченных выборок из n

элементов по k	или функциями от них.
Введем	несколько операций в классе	производящих функций.
{ fa (t)} - класс обычных производящих функций		n
		fa (t) = ∑ak t k .

k =0

·Суммой последовательностей {a} = {a0 , a1 ,...} и {b} = {b0 , b1 ,...}

называется последовательность {c} = {a + b} = {a0 + b0 , a1 + b1 ,...} = {c0 , c1 ,...} , а

	n	n
суммой	производящих функций fa (t) = ∑ak t k и	fb (t) = ∑bk t k -
	k =0	k =0
производящая функция
	∞
	fc (t) = fa (t) + fb (t) = ∑ck t k .
	k =0
·	Произведением (или сверткой) последовательностей {a} и {b}

называется последовательность {d} = {a ×b} = {d0 , d1 ,...} , у которой dr = a0br + a1br −1 + a2br −2 + ... + ar b0 , r = 0,1, 2,... ,

48

а произведением (сверткой) производящих функций fa (t) и fb (t) -

производящая функция

∞

fd (t) = fa (t) × fb (t) = ∑ dk t k .

k =0

Данная формула нуждается в пояснении. Эти коэффициенты получаются при перемножении рядов следующим образом:

	r = 0, d0 = a0b0 ,
	r = 1, d1 = a0b1 + a1b0 ,
	r = 2, d2 = a0b2 + a1b1 + a2b0 ,
	...................................................
	r = k, dk = a0bk + a1bk −1 + + ak −1b1 + ak b0 ,
.......................................................................
Нуль в классе производящих функций				{ fa (t)} -	это	f0 (t) = 0 ; ей
		{		}
соответствует нулевая последовательность			0, 0, 0,..., 0,... .
Единица в классе производящих функций { fa (t)}					- это	fe (t) = 1 ; ей
соответствует единичная последовательность {1, 0, 0,..., 0,...} = e .

Обратный относительно сложения (противоположный) элемент в классе производящих функций есть следующая функция: -

n

fa (t) = f− a (t) = ∑(−ak )tk , которой соответствует последовательность

k=0

{−a0 , −a1 ,..., −ak ,...} .

Обратный элемент относительно умножения в классе производящих

∞

функций есть функция fa−1 (t) = ∑aɶk tk , ей соответствует последовательность

{ a} = { a0		, a1	,..., ak ,...} ,	причем		k =0			. Так	как a × a = e, a ¹ 0 , то
						a × a = e, a ¹ 0
ɶ	ɶ	ɶ	ɶ			ɶ				ɶ
получим систему:
						ɶ
						a0 a0 = 0,
						ɶ	ɶ
					a0 a1 + a1a0 = 0,
					ɶ	ɶ	ɶ	= 0,
					a0 a2	+ a1a1	+ a2 a0
			............................................
				ɶ		ɶ		ɶ	ɶ	= 0,
				a0 ak	+ a1ak −1 + ... + ak −1a1				+ ak a0

...........................................................

Неизвестные здесь aɶ0 , aɶ1 ,..., aɶk ,... . Количество неизвестных равно количеству уравнений.

49

· Умножение производящей функции на действительное число α определяется по формуле:

n

α fa (t) = ∑(α × ak )t k .

k =0

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

с ограниченным

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

В этом случае для получения производящей функции нельзя

воспользоваться произведением

биномов

вида

(1+ xk t ) ,

т.е. формулой

n

n

∏(1+ xk t ) = ∑ak t k , поскольку

всякий

такой

бином

отражает лишь две

k =1

k =0

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

xk

множества либо не появляется в

r

- сочетаниях,

либо появляется ровно один раз. Пусть элемент

xk

появляется

в r -

сочетаниях

с повторениями 0,1, 2,..., j

раз,

тогда

точно

i

появлениям

элемента x

будет соответствовать

одночлен

xi

ti

, а

по

правилу

суммы

k

k

появлению

элемента

xk

либо

0,

либо

1,…,

либо

j

раз

должен

соответствовать многочлен 1 + xk t + xk2t2 + xk3t3 + ... + xkj t j . Тогда производящая функция будет иметь вид:

n
f (t) = ∏(1 + xk t + xk2t 2 + xk3t3 + ... + xkj t j ) .
k =1
Если нужно найти лишь число ar соответствующих сочетаний из n
по r , то необходимо положить x1 = x2 = ... = x j	= 1 и
f (t) = (1 + t + t 2 + ... + t j )n	l
	= ∑ak t k .
	k =1

Коэффициенты ak будут здесь равны числу сочетаний из n элементов по k с j повторениями.

Пример 1.

Рассмотрим сочетания из трёх предметов 1, 2, 3; причем 1 и 2 могут встречаться не более двух раз, а 3 – не более одного раза.

Составим производящую функцию по формуле:

f (t) = ∏n (1 + xk t + xk2t 2 + xk3t3 + ... + xkj t j )

k =1

50