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

Поэтому n( A) = 47; n(B) = 35; n( A Ç B) = 23 .

Тогда, число сотрудников, изучающих хотя бы один из этих языков,

равно:

n( A È B) = n( A) + n(B) - n( A Ç B) = 47 + 35 - 23 = 59 .

Ответ: 59 сотрудников.

Используя формулу (5.1) и законы алгебры множеств, можно получить формулу для числа элементов любой конечной совокупности конечных множеств. Например, для объединения трех множеств получим: n( A È B È C) = n ( A È( B È C )) = n( A) + n(B È C) - n ( A Ç ( B È C )) =

=n( A) + n(B) + n(C) - n(B Ç C) - n (( A Ç B) È ( A ÈC )) =

=n( A) + n(B) + n(C) - n(B Ç C) - n( A Ç B) - n( A Ç C) + n (( A Ç B) Ç ( A ÇC )) =

=n( A) + n(B) + n(C) - n(B Ç C) - n( A Ç B) - n( A Ç C) + n ( A Ç B Ç C )

			Получили формулу:
	A	B	n( A È B È C) = n( A) + n(B) + n(C) -	(5.2)
			- n( A Ç B) - n( A Ç C) - n(B Ç C) + n ( A Ç B Ç C )

C

2. Известно, что 60 студентов курса изучают английский язык, 40 студентов изучают немецкий язык, 30 студентов курса изучают французский язык, 20 студентов изучают английский и немецкий, 15 английский и французский, 20 изучают немецкий и французский, а 5 студентов изучают все три языка. Определить число студентов,

изучающих хотя бы один из этих трёх языков.

Решение.

Пусть A - множество студентов, изучающих английский язык; B -

множество студентов, изучающих немецкий язык,				C - множество студентов,
изучающих французский язык. Тогда	A Ç B	-	это		множество		студентов,
изучающих английский и немецкий,	A ÇC	-	это		множество		студентов,
изучающих английский и французский языки,			а	B ÇC		- это	множество
студентов, изучающих немецкий и французский				языки;		A Ç B Ç C - это
множество студентов, изучающих все три языка;			A È B È C - это множество
студентов, изучающих хотя бы один из этих трёх языков.
Поэтому

31

n( A) = 60; n(B) = 40; n(C) = 30 ;

n( A Ç B) = 20; n( A Ç C) = 15; n(B Ç C) = 20; n( A Ç B Ç C) = 5 .

Тогда число студентов, изучающих хотя бы один из этих трёх языков, равно:

n( A È B È C) = 60 + 40 + 30 - 20 -15 - 20 + 5 = 80 .

Решение задачи наглядно демонстрирует диаграмма Эйлера-Венна:

A		B
30	15	5
	5
10		15
	0

C

Ответ: 80 студентов.

В общем случае для n конечных множеств справедлива теорема.

Теорема 5.1. Если A1 , A2 ,..., An - некоторые конечные множества и n( A1 ), n( A2 ), ... , n( An ) известны, то

n( A1 È A2 È... È An ) = n( A1 ) + n( A2 ) +...+ n( An ) -{ n( A1 Ç A2 ) + n( A1 Ç A3 ) +...

... + n( An−1 Ç An )} +{n( A1 Ç A2 Ç A3 ) + n( A1 Ç A2 Ç A4 ) +...+ n( An−2 Ç An−1 Ç An )} + ...

... + (-1)n −1 n( A1 Ç A2 Ç... Ç An ).

(5.3)

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

Чтобы доказать теорему, необходимо показать, что каждый элемент из множества A1 È A2 È... È An учитывается и в правой части равенства (5.3), причем только один раз.

Пусть a Î A1 È A2 È... È An - такой элемент, который входит в состав

m множеств			Ai , i =	1, n	. Тогда элемент		a в правой части подсчитывается:
Cm1	- Cm2	+ Cm3	-... + (-1)m −1 Cmm			раз. Но
Cm1	- Cm2	+ Cm3	- ... + (-1)m −1 Cmm			= 1 - (Cm0 + Cm1	- Cm2 + Cm3 -... + (-1)m −1 Cmm ) = 1- 0 = 1

Значит, каждый элемент a из A1 È A2 È... È An учитывается в правой

части равенства только один раз. Теорема доказана.

Метод подсчета по формуле (5.3), который состоит в последовательном выполнении операций сложения и вычитания, чередующихся между собой, называется методом включений и

исключений.

32

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

Пусть дано n элементное множество Sn некоторых элементов и множество k свойств p1 , p2 ,..., pk , которыми элементы множества Sn могут как обладать, так и не обладать. Выделим какую-либо выборку объёма r свойств ( pi1 , pi2 ,..., pir ) . Число элементов s Sn , обладающих всеми r

выбранными свойствами, обозначим через n ( pi1 , pi2 ,..., pir ) . Отсутствие у элемента какого-либо свойства pi будем обозначать pi . Тогда, например, запись n ( p1 , p2 , p3 ) означает число элементов, обладающих свойствами p1 и p3 , но не обладающих свойством p2 .

Найдем число элементов, не обладающих набором определённых свойств, начав с самых простых случаев.

1.Пусть имеется одно свойство p , тогда n( p) = n − n( p) .

2.Имеется конечное число свойств: p1 , p2 ,..., pk несовместимых друг с

k

другом. Тогда снова: n ( p1 , p2 ,..., pk ) = n − ∑n( pi ) .

i =1

3.Элементы обладают комбинациями различных свойств. Тогда справедлива теорема 5.2.

Теорема 5.2. Если даны множества Sn и k - элементное множество

свойств pi , i = 1, k , совместимых между собой, тогда количество элементов

множества Sn , не обладающих ни одним из свойств pi , i =									1, k	вычисляется
по формуле:
						k
n (		1 ,		2 ,...,		k ) = n − ∑n( pi ) +	∑ n( pi , p j ) −	∑ n( pi , p j , pl ) + ...
	p		p		p
						i =1	1≤i < j ≤ k	1≤i < j <l ≤ k		(5.4)
						... + (−1)k n ( p1 , p2 ,..., pk ).
							Доказательство.

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

k =1, n(p)= n −n(p). Эта формула очевидна. Пусть теорема верна для k −1 свойств, т.е.

k −1

n(

p1

,

p2

,...,

pk −1

)= n −∑n(pi )+

∑ n(p1 , p j )−

∑ n(pi , p j , pl )+...

i=1

1≤i<j≤k −1

1≤i< j≤k−1

...+ −1

k −1 n

(

p , p

2

,..., p

k−1 )

.

(5.5)

( )

1

33

Перейдем к случаю,

когда имеется k свойств. Так как n(

p

)= n −n(p), то по

аналогии можно записать n(

,

,...,

,

)= n (

,

,...,

)−

p1

p2

pk−1

pk

p1

p2

pk −1

- n(

,

,...,

, pk ).

Применим

соотношение

(5.5)

для

числа

p1

p2

pk−1

n(

,

,...,

, pk ). Получим следующую формулу:

p1

p2

pk−1

k −1

n(

p1

,

p2

,...,

pk −1

, pk )= n(pk )−∑n(pi , pk )+

∑ n(pi , p j , pk )+...

i=1

1≤i< j≤k−1

...+ −1 k −1 n

(

p , p

,..., p

k −1

, p

.

(5.6)

(

)

1

2

k )

Прокомментируем ее. В ней

n(

,

,...,

, pk )

-

число

элементов,

p1

p2

pk−1

обладающих

свойством

pk

и

одновременно не обладающих

свойствами

p1 , p2 ,..., pk −1 ;

n(pk )

-

число

элементов,

обладающих

только

свойством

k −1

pk , ∑n(pi , pk ) - число элементов,

обладающих

свойствами

p1

и pk

i=1

одновременно, и т.д. Ясно,

что для того чтобы получить n(

p1

,

p2

,...,

pk−1

, pk ),

из общего числа элементов со свойством

pk , надо вычесть сначала число

элементов, обладающих свойствами pi и

pk . Однако при этом элементы,

имеющие три свойства, а именно

pk и, скажем,

pi и p j , будут исключены

дважды (сначала как элементы со свойствами pi

и pk

, затем как элементы со

свойствами p j и pk ). Значит,

надо возвратить все элементы, обладающие

тремя свойствами, т.е. прибавить

∑ n(pi , p j , pk )

и т.д. Вычтем теперь из

1≤i<j≤k −1

(5.5) формулу (5.6), получим

n(

,

,...,

)−n(

,

,...,

, pk )= n(

,

,...,

)= n −

p1

p2

pk −1

p1

p2

pk −1

p1

p2

pk

k −1

k−1

−

∑n(pi )+n(pk ) +

∑ n(pi

, p j )+∑n(pi , pk ) +...

i=1

1≤i< j≤k −1

i=1

k

...−(−1)k−1 n(p1 , p2 ,..., pk −1 , pk )= n −∑n(pi )+

i=1

+ ∑ n(pi , p j )+...+(−1)k n(p1 , p2 ,..., pk −1 , pk ).

1≤i< j≤k

34

Замечание 1. Характер теоремы 5.2 таков, что её можно применять для любой комбинации свойств, как выполняющихся, так и нее имеющих места. Таким образом, в левой части формулы (5.4) может стоять не только

n ( p1 , p2 ,..., pk ) , но и, например, n ( p1 , p2 , p3 , p4 ) . Тогда теорема 5.2 формулируется относительно совокупности свойств p2 и p4 с обязательным выполнением свойств p1 и p3 следующим образом:

n ( p1 , p2 , p3 , p4 ) = n ( p1 , p3 ) - n ( p1 , p2 , p3 ) - n ( p1 , p3 , p4 ) + n ( p1 , p2 , p3 , p4 ) .

Замечание 2. Если дополнительно предположить, что число элементов с какими-либо свойствами зависит только от количества этих свойств, а не от типа свойств, характерных элементам, т.е.:

n( p1 ) = n( p2 ) =				... = n( pn ) = N (1)
n( p , p ) = n( p , p ) = ... = n( p							n−1	, p ) = N ( 2)
1	2		1	3				n
...............................................................
n( p ,..., p		k	) = ...	= n( p	n− k +1	,..., p ) = N (k )
1							n

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

n( p1 , p2 ,..., pn ) = N (n)

Тогда суммарное число элементов, которые имеют ровно k свойств, равно:

n( p ,..., p

k

...) +

+ n( p

n− k +1

,..., p

n

) = C k

× N (k ) , k =

1, n

.

1

n

При указанных ограничениях формула включений и исключений

имеет вид:

n (

1 ,

2 ,...,

k ) = n - Cn1 × N (1)

+ Cn2 × N (2)

- Cn3 × N (3)

+

+ (-1)k Cnn × N ( n)

(5.7)

p

p

p

Применение формулы включений и исключений

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

Найдем число смещений Dn

- перестановок из n элементов, среди

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

беспорядках).
	Задача о беспорядках известна давно: её решением занимался ещё
Л.Эйлер. Значения			Dn быстро получаются при помощи						формулы (5.7)
включений и исключений с ограничениями.
	Пусть N = Pn			= n!	- число всех перестановок из				n	элементов,
N (1) = P		= (n -1)!	-	число	тех перестановок, где			один	фиксированный
n−1
элемент	p остается на своём месте. В общем случае,							N (k ) = P		= (n - k)! -
		i							n−k
число перестановок,			в которых k фиксированных элементов (из этих n
элементов) остаются на своих местах, k =							.
						1, n

35

Тогда число смещений Dn равно n (

1 ,

2 ,...,

n ) - числу

p

p

p

перестановок,

в которых каждый элемент pi

не остаётся на своём месте.

Согласно формуле (5.7) имеем:

D = P − C1 P

+ C 2 P

− ... + (−1)n C n P = n!− C1 (n −1)!+ C

2

(n − 2)!− ... + (−1)n C n =

n

n n n−1

n n −2

n 0

n

n

n

= n!-

n!

(n -1)!+

n!

(n - 2)!-... + (-1)n

n!

=

(n -1)!×1!

(n - 2)!×

2!

n!

1

1

1

(-1)n

= n! 1

-

+

-

... +

(5.8)

1!

2!

3!

n!

Очевидно, что D1 = 0 .

Условимся, что, если n = 0 , то D0

= 1 .

Смещение неполного числа элементов Dn,k .

Число перестановок n различных предметов, при которых ровно k предметов остаются на своих первоначальных местах, а оставшиеся n - k обязательно сменяют своё место, выражается числом:

D		= C k × D		.	(5.9)
n,k			n n−k
Сначала следует выбрать,			какие именно k		элементов остаются на
месте. Это можно сделать Cnk	способами. Остальные n - k элементов можно

переставлять любым способом, лишь бы ни один из них не оказался на своём

первоначальном месте. Это		можно сделать Dn−k способами.				По правилу
произведения получим C k × D				искомых перестановок.
	n	n− k
	n			n
Очевидно, что ∑ Dn,k			= ∑Cnk × Dn−k = n!			(5.10)
	k =0			k =0
Применение метода включений и исключений в теории чисел.
Напомним	некоторые			сведения из теории чисел.	Пусть a и b
натуральные числа.	Наибольшим общим делителем a				и b	называется

наибольшее натуральное число, которое является одновременно делителем a и b . Обозначается НОД (a,b) . Запись НОД (a, b) = 1 означает, что числа a

и b взаимно простые.

Наименьшим общим кратным чисел a и b называется наименьшее число, которое делится на a и b одновременно. Обозначается

НОK (a,b) .

Рассмотрим каноническое разложение чисел a и b на простые множители:

a = p1α1 p2α2 ×...× pkαk ,

b = p1β1 p2β2 ×...× pkβk

36

(не	нарушая	общности,	будем считать	наборы простых множителей
p1 , p2 ,..., pk одинаковыми для обоих чисел). Тогда
	НОД (a,b) = p1min{α1 ,β1} p2min{α2 ,β2 } ×...× pkmin{αk ,βk } ,				(5.11)
	НОK (a, b) = p1max{α1 ,β1} p2max{α2 ,β2 } ×...× pkmax{αk ,βk } ,				(5.12)
где	символы	min{α , β} ,	max{α , β}	соответственно	наименьшее и

наибольшее из чисел α и β .

Например.

Найти наибольший общий делитель и наименьшее общее кратное

чисел a = 120, b = 42 .

Решение.

Запишем канонические разложения чисел a и b

на простые

множители:

a = 120 = 23315170 ,

b = 42 = 213150 71 .

В соответствии с равенствами (5.11) и (5.12) имеем:

НОД (120, 42) = 213150 70 = 6 ,

НОK (120, 42) = 23315171

= 840 .

Ответ:

НОД (120, 42) = 6 , НОK (120, 42) = 840

Введем обозначения: d

a -

число

d является делителем числа

a ;

d

a - число d

не является делителем числа a .

Пусть

x -

действительное неотрицательное число. Через [x] будем

обозначать целую

часть числа

x -

наибольшее целое

число,

не

превышающее x .

Используем без доказательства следующее утверждение из теории

чисел.

Теорема 5.3. Если a n, b n , a и b взаимно простые, то ab n . Например. Сколько чисел среди 1, 2,3,..., 99,100 таких, которые не

делятся ни на 2, ни на 3, ни на 5?

Решение.

Подсчитаем сначала количество чисел, которые делятся хотя бы на одно из чисел 2,3,5. Пусть A1 - множество тех чисел, которые делятся на 2,

A2 - множество тех чисел, которые делятся на 3,									A3 - множество тех чисел,
которые делятся на 5. Тогда:
100				100					100
n( A1 ) =			= 50,	n( A2 ) =			= 33,	n( A3 ) =				= 20 ,
2				3					5

100

100

100

n( A1

Ç A2 ) =

= 16,

n( A1

Ç A3 ) =

= 10,

n( A2

Ç A3 ) =

= 6 ,

×5

2 ×3

2

×5

3

37

		100
n( A1 Ç A2	Ç A3 ) =			= 3 .
	2 ×3×5

Тогда n( A1 È A2 È A3 ) = 50 + 33 + 20 - (16 +10 + 6) + 3 = 74 .

Количество чисел, которые не делятся ни на одно из чисел 2,3,5

равно 100 − 74 = 26 .

Ответ: 26 чисел.
Теорема 5.4. Пусть есть	натуральное число n и натуральные
числа a1 , a2 ,..., am взаимно простые	НОД (ai , a j ) = 1, i ¹ j . Тогда число N
целых чисел k , таких что 0 < k £ n	и k не делится ни на одно из чисел

a1 , a2 ,..., am , равно:

m

n

n

n

N = n - ∑

+

∑

-... + (-1)m

∑

.

(5.13)

1

1

2

ai

2

m

i =1

1≤i1 <i2 ≤ m

ai

ai

1≤i1 <i2 <...<im ≤m

ai

ai

...ai

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

Для доказательства теоремы, будем искать количество чисел,

которые не делятся ни на одно из чисел

a1 , a2 ,..., am . Пусть

Ai

- множество

тех чисел k (k ³ 0) , которые делятся на ai

. Тогда

n

n

n( Ai ) =

,..., n( Ai1

Ç Ai2 Ç... Ç Aim )

=

.

...aim

ai

ai1 ai2

Согласно с равенством (5.3)

m

m

n

n

n

n

Ai

= ∑

-

∑

+ ... + (-1)m−1

∑

.

i =1

i =1

ai

1≤i1 <i2 ≤ m ai1 ai2

1≤i1 <i2

<...<im ≤m ai1 ai2 ...aim

Далее остается отметить, что количество чисел, которые не делятся

m

откуда и получается

ни на одно из чисел a1 , a2 ,..., am , равняется n - n

Ai

,

i =1

формула (5.13).

Например. Сколько чисел среди чисел, которые не превышают 35,

таких, которые не делятся ни на 3, ни на 7, ни на 8?

Решение.

Согласно с формулой (5.13) количество таких чисел равно:

35			35			35			35				35				35						35
N = 35 -			+			+			+				+				+				-				=
											× 7								×8
3			7			8			3				7		×8		3				3		×7 ×8

=35 - (11+ 5 + 4) + (1+ 0 +1) - 0 = 35 - 20 + 2 = 17

Ответ: 17 чисел.

38

ЛЕКЦИЯ 6.

ФУНКЦИЯ ЭЙЛЕРА. ФУНКЦИЯ МЁБИУСА.

В теории чисел и некоторых других разделах математики большую роль играет функция Эйлера, названная так в честь знаменитого швейцарского математика Леонарда Эйлера (1707-1783).

Функцией Эйлера называется функция ϕ(n) , определённая на

множестве натуральных чисел N , значения которой равны числу k натуральных, может быть, и составных целых чисел, взаимно простых с n и не превосходящих n , т.е. 0 < k < n, НОД(k, n) = 1 . Для n = 1 полагают

ϕ(1) = 1 .

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

k				n		n
ϕ (n) = n − ∑	n	+	∑		− ... + (−1)k			,	(6.1)
i =1 qi			1≤i< j ≤ k qi q j			q1q2 ...qk
где k - есть число простых делителей qi числа n ,							i = 1, 2,..., k .

Чаще функция Эйлера приводится в несколько другом виде:

k

1

1

1

1

ϕ (n) = n∏ 1−

=n 1

−

1 −

...

1

−

,

i =1

qi

q1

q2

qk

n = qα1 qα2

...qαk

1

2

k

Теорема 6.1. Пусть n = qα1 qα2 ...qαk

- каноническое разложение числа

1

2

k

n на простые множители. Тогда

k

1

1

1

1

ϕ (n) = n∏ 1−

=n

1−

1−

...

1−

(6.2)

qi

i =1

q1

q2

qk

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

n = qα1 qα2 . Взаимно

Рассмотрим

сначала

случай

k = 2 .

Тогда

1

2

простыми с n будут числа,

которые не делятся ни на

q1 ,

ни на q2 . Из

равенства (6.1) будем иметь:

n

n

n

1

1

ϕ(n) = n −

+

+

= n 1 −

1

−

.

q1q2

q1

q2

q1

q2

Получили частный случай формулы (6.2). В общем случае получим:

k

n

n

n

ϕ (n) = n − ∑

+

∑

− ... + (−1)k

=

i =1

qi

1≤i < j ≤ k qi q j

q1q2 ...qk

1

1

1

= n 1 −

1 −

... 1−

.

q1

q2

qk

39

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

	n		k ≤ n, НОД(k, n) = 1											ϕ(n)
	1				1									1
	2				1									1
	3				1,2									2
	4				1,3									2
	5			1,2,3,4										4
	6				1,5									2
	7			1,2,3,4,5,6										6
	8			1,3,5,7										4
Например.
1. Найти ϕ(10) .
Решение.
Разложим число 10 на простые множители:														10 = 21 ×51 . Тогда по
формуле (6.2) получим:
		ϕ (10) =			-	1			-	1		= 4 .
				10 1				1
						2				5
Действительно,			НОД(1,10) = 1,						НОД(3,10) = 1, НОД(7,10) = 1,

НОД(9,10) = 1 . Это числа 1,3,7 и 9.

2. Пусть p - простое число. Чему равна ϕ( p) ?

Решение.

Если число p простое, то все числа, не превышающие p , будут взаимно простыми с p . Поэтому ϕ( p) = p -1.

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

Определение. Функция f (n) , определённая на множестве Z + натуральных чисел, называется мультипликативной, если для любых натуральных чисел a и b таких, что НОД(a,b) = 1

f (a ×b) = f (a) × f (b) .

Теорема 6.2. Функция Эйлера ϕ(n) мультипликативная.

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

Пусть a и b взаимно простые числа. Рассмотрим канонические разложения этих чисел на простые множители:

a = p1α1 p2α2 ×...× pαmm , b = q1β1 q2β2 ×...× qrβr .

Поскольку a и b взаимно простые, то pi ¹ q j (1 £ i £ m, 1 £ j £ r ) . Далее определим, что

40