Спец.гл.мат-ки_Ч.1_УП

61

друга только порядком элементов. Такие выборки называются перестановками. Количество перестановок из n элементов обозначают Pn :

Pn = Ann = n (n − 1) ... (n − n + 1) = n (n − 1) ... 1 = n!

Пример. Сколькими способами можно выстроить очередь в кассу, если хотят получить зарплату шесть человек?

P6 = 6!= 1 2 … 6 = 720 .

2.1.7 Перестановки с повторениями
Пусть	множество X состоит из k различных элементов:
X = {x1, x2 ,…, xk } . Перестановкой с				повторениями		состава
(r1,r2 ,…,rk )	будем	называть	упорядоченный		набор	длины
n = r1 + r2 +…+ rk , в		котором	элемент	xi встречается		ri раз
(i = 1,2,…,k) . Количество таких перестановок					обозначается

Pn (r1,r2 ,…,rk ) .

Пример. Из букв {a,b,c} запишем перестановку с повторением состава (2,2,1) . Ее длина n = 2 + 2 + 1 = 5 , причем буква a

входит 2 раза, b – 2 раза, c – один раз. Такой перестановкой будет, например, (a,b,a,b,c) или (b,c,a,a,b) .

Выведем формулу количества перестановок с повторениями. Занумеруем все одинаковые элементы, входящие в перестановку, различными индексами, т.е. вместо перестановки (a,b,a,b,c) получим (a1,b1,a2 ,b2 ,c) . Теперь все элементы перестановки различны, а количество таких перестановок равно n!= (r1 + r2 +…+ rk )!. Первый элемент встречается в выборке r1

раз. Уберем индексы у первого элемента (в нашем примере получим перестановку (a,b1,a,b2 ,c) ), при этом число различных

перестановок уменьшится в r1! раз, т.к. при изменении порядка

одинаковых элементов наша выборка не изменится. Уберем индексы у второго элемента – число перестановок уменьшится в r2! раз. И так далее, до элемента с номером k – число перестано-

вок уменьшится в rk ! раз. Получим формулу

62
Pn (r1,r2 ,...,rk ) =	n!
		.
	r1! r2! ... rk !

Пример. Сколько различных «слов» можно получить, переставляя буквы слова «передача»?

В этом слове буквы «е» и «а» встречаются два раза, остальные по одному разу. Речь идет о перестановке с повторением состава (2,2,1,1,1,1) длины n = 2 + 2 + 1+ 1+ 1+ 1 = 8 . Количество

таких перестановок равно

	P8 (2,2,1,1,1,1) =	8!		= 7! 2	= 10080 .
		2! 2! 1! 1! 1! 1!

2.1.8 Сочетания

Задача. Сколько различных множеств из r элементов можно составить из множества, содержащего n элементов?

Будем составлять вначале упорядоченные наборы по r элементов в каждом. Количество таких наборов (это размещения из

n элементов по r) равно Anr =	n!	. Теперь учитываем,	что
	(n − r)!
порядок записи элементов нам безразличен. При этом из r!			раз-

личных размещений, отличающихся только порядком элементов, получим одно сочетание. Например, два различных размещения (a,b) и (b, a) из двух элементов соответствуют одному

сочетанию {a,b} . Таким образом, число сочетаний Сnr в r! раз меньше числа размещений Anr :

Сnr =	Ar	=	n!
	n			.
	r!		r!(n − r)!

Пример. Количество способов, которыми мы можем выбрать из восьми дворников троих равно

С83 =	8!	=	8!	= 56.
	3!(8 − 3)!		3! 5!

						63
2.1.9 Сочетания с повторениями
Задача. Найти количество Сnr							сочетаний с повторениями из
n предметов по r.
Рассмотрим вывод формулы на примере с фотографиями
(см. 2.1.2). Имеется n типов предметов ( n = 3 негатива). Нужно
составить набор из r					предметов ( r = 5			фотографий).		Наборы
различаются своим составом, а не порядком элементов. Напри-
мер, разными будут наборы состава (3,1,1) и (1,0,4)									– один со-
держит три фотографии с первого негатива и по одной со второ-
го и с третьего, а другой – одну с первого и четыре с третьего.
Разложим эти наборы на столе, разделяя фотографии разного
типа карандашами. Карандашей нам понадобится n −1= 3−1= 2,
а фотографий r = 5 . Мы будем получать различные сочетания с
повторениями, переставляя между собой эти (n − 1) + r										предме-
тов, т.е. Сr	= P	−1+ r		(n −1, r) − число сочетаний с повторениями из
n	n
n предметов по r равно числу перестановок с повторениями
длины n − 1+ r состава (n − 1,r) . В нашем примере
	С5	= P			(3 − 1,5) = P (2,5) =			7! = 21.
	3			3−1+5		7		2! 5!
Иначе формулу сочетаний с повторениями можно записать
				Сnr = (n − 1+ r)! = Cnr−1+ r .
					(n − 1)!r!
					Определить n и r
Нет				Порядок важен?				Да
Повторения						Выбираем все n
есть?					Нет		элементов?		Да
Нет			Да
					Повторения			Повторения
						есть?		есть?
r		r			Нет		Да	Нет		Да
Cn =	Cn		=		Ar =	Ar =		Pn = n!	Pn(r1...rk)
n!		r
					n		n
r!(n − r)!	Cn		−1+ r		n!		nr		=	n!
					(n − r )!
									r1!...rk!
				Рис. 2.1 − Выбор формулы

64

1.2.10 Решение задач 2,3 контрольной работы № 2

При решении задач комбинаторики рекомендуем выбирать нужную формулу, пользуясь блок-диаграммой (рис. 2.1).

Задача 3. В профком избрано 9 человек. Из них надо выбрать председателя, его заместителя и казначея. Сколькими способами это можно сделать?

Решение. Составим список в порядке: председатель, заместитель, казначей. Выбираем трех из 9 человек, т.е. n = 9, r = 3 .

Порядок важен? Да, выбираем правую часть блок-диаграммы (рис. 2.1). Следующий вопрос: выбираем все n элементов? Нет. Повторения есть? Нет. Следовательно, наша выборка – размещение без повторений и количество таких выборок

A3	=		9!		=	9!	= 7 8 9 = 504.
9	(9		− 3)!		6!

Задача 2. Сколькими способами 40 человек можно рассадить в три автобуса, если способы различаются только количеством человек в каждом автобусе?

Решение. Выстроим 40 человек в очередь и выдадим каждому билет с номером автобуса. Получим выборку, например, такую: 1,1,2,2,3,1,…,2,1. В этой выборке 40 элементов ( r = 40 ),

а значений – номеров автобусов – три ( n = 3 ). Порядок важен? Чтобы ответить на этот вопрос, поменяем местами двух человек в очереди и посмотрим, изменилась ли выборка. Выборка не изменилась, т.к. количество людей в каждом автобусе осталось прежним. Порядок не важен, поэтому выбираем левую часть блок-диаграммы (рис. 2.1). Повторения есть? Да, в нашей выборке номер автобуса может встречаться несколько раз. Следовательно, выборка является сочетанием с повторениями из n = 3 по r = 40 элементов:

				(3 − 1+ 40)!	=	42!	= 41 21 = 861.
		С340 =
				40! (3 − 1)!		40! 2!

2.1.11 Бином Ньютона

В школе изучают формулы сокращенного умножения:

65

(a + b)2 = a2 + 2ab + b2 ,

(a + b)3 = a3 + 3a2b + 3ab2 + b3.

Бином Ньютона позволяет продолжить этот ряд формул. Раскроем скобки в следующем выражении:

(a + b)n = (a + b)(a + b)…(a + b)

n раз

Общий член суммы будет иметь вид Cak bn−k . Чему равен коэффициент C? Он равен количеству способов, которыми

можно получить слагаемое ak bn−k (т.е. количеству способов, которыми можно выбрать k скобок с множителем a, а из остальных n − k скобок взять множитель b). Например, если

n = 5, k = 2, то слагаемое a2b3 можем получить, выбрав множи-

тель a из первой и пятой скобки. Каков тип выборки? Порядок перечисления не важен (выбираем сначала первую, затем пятую скобки, или, наоборот, сначала пятую, затем первую – безразлично), повторяющихся элементов (одинаковых номеров скобок) в выборке нет. Это сочетание без повторений. Количество таких выборок равно

Сnk =	n!
		.
	k!(n − k)!

Таким образом, формула бинома для произвольного натурального n имеет вид:

(a + b)n = Cn0bn + Cn1abn−1 + Cn2a2bn− 2 + ... + Cnn−1an−1b + Cnnan

или

n

(a + b)n = ∑Cnk ak bn− k . k =0

Пример. При n = 4 получим формулу

(a + b)4 = C40b4 + C41ab3 + C42a2b2 + C43a3b + C44a4 =

= b4 + 4ab3 + 6a2b2 + 4a3b + a4 ,

66

т.к. C40 =

4!

= 1; C41 =

4!

= 4;

C42 =

4!

= 6; ...

0!(4 − 0)!

1!(4

− 1)!

2!(4

− 2)!

Проверьте правильность формулы,

перемножив (a + b)3 на

(a + b) .

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

2.1.12 Свойства биномиальных коэффициентов

Биномиальными коэффициентами являются величины

	Сnk =	n!		,
		k!(n − k)!

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

Свойство симметрии.

Сnk = Cnn−k .

В формуле бинома это означает, что коэффициенты, стоящие на одинаковых местах от левого и правого концов форму-

лы, равны, например: С62 = С64 = 6! = 15. 2! 4!

Действительно, Сnk − это количество подмножеств, содержащих k элементов, множества, содержащего n элементов. А Сnn−k − количество дополнительных к ним подмножеств. Сколько подмножеств, столько и дополнений.

Свойство Паскаля.

Сnk = Cnk−1 + Cnk−−11.

Пусть X = {x1, x2 ,…, xn}. Число Сnk – это количество под-

множеств из k элементов множества X. Разделим все подмножества на два класса:

1)подмножества, не содержащие элемент x1 , – их будет

Сk− ; n 1

67

2) подмножества, содержащие элемент x1 , – их будет Сnk−−11 .

Т.к. эти классы не пересекаются, то по правилу суммы количество всех k-элементных подмножеств множества X будет

равно Сnk−1 + Cnk−−11.

На этом свойстве основано построение треугольника Паскаля (рис. 2.2), в n-ой строке которого стоят коэффициенты раз-

ложения бинома (a + b)n .

Рис. 2.2 − Треугольник Паскаля

Свойство суммы.

Сn0 + Cn1 + Cn2 + ... + Cnn = 2n.

Подставим в формулу бинома Ньютона

n

(a + b)n = ∑Cnk ak bn− k k =0

значения a = 1, b = 1. Получим

n

2n = ∑Cnk 1k1n−k k =0

n

= ∑Cnk . k =0

Заметим, что с точки зрения теории множеств сумма Сn0 + Cn1 + ... + Cnn выражает количество всех подмножеств n- элементного множества. По теореме о мощности булеана (см. 1.4.4) это количество равно 2n .

Свойство разности.

Сn0 − Cn1 + Cn2 − Сn3...+ (−1)n Cnn = 0.

68

Положим в формуле бинома Ньютона a =1, b = −1. Получим

в левой части (1− 1)n = 0 , а в правой – биномиальные коэффици-

енты с чередующимися знаками, что и доказывает свойство. Последнее свойство удобнее записать, перенеся все коэф-

фициенты с отрицательными знаками в левую часть формулы:

Cn1 + Cn3 + Сn5 + ... = Cn0 + Cn2 + ...,

тогда свойство легко запоминается в словесной формулировке: « сумма биномиальных коэффициентов с нечетными номерами равна сумме биномиальных коэффициентов с четными номерами».

		1	n
	Задача. Найти член разложения бинома x +			, не со-
		x4

держащий x, если сумма биномиальных коэффициентов с нечетными номерами равна 512.

Решение. По свойству разности сумма биномиальных коэффициентов с четными номерами также равна 512, значит, сумма всех коэффициентов равна 512+512=1024. Но по свойству

суммы это число равно 2n = 210 = 1024 . Поэтому n = 10 . Запишем общий член разложения бинома и преобразуем его:

1

n−k

T

= Ck ak bn−k = Ck xk

= Ck xk −4n+ 4k , k = 0,1,..., n;

k +1

n

n

x4

n

при n = 10 получим:

T

= Ck

x5k −40 ,

k = 0,1,..., n.

k +1

10

Член разложения Tk +1 не содержит x, если 5k − 40 = 0 , т.е.

k = 8 . Итак,

девятый член разложения не содержит x и равен

T = C8

=

10!

= 45.

9

10

8!(10 − 8)!

Свойство максимума. Если степень бинома n – четное число, то среди биномиальных коэффициентов есть один мак-

симальный приk = n . Если степень бинома нечетное число, то

2

69

максимальное значение достигается для двух биномиальных

коэффициентов при k1	=	n − 1	и k2	=	n + 1	.
	2			2

Так, при n = 4 максимальным является коэффициент C42 = 6 , а при n = 3 максимальное значение равно C31 = C32 = 3 (рис. 2.2).

2.1.13Приближенные вычисления с помощью бинома Ньютона

Положим в формуле бинома Ньютона b = 1, a = x :

n
(1+ x)n = ∑Cnk xk = 1+ nx + n(n − 1) x2 + n(n − 1)(n − 2) x3 + ... + xn .
k =1	2	2 3

Эту формулу удобно применять для приближенных вычислений при малых значениях x ( x < 1 ).

Пример 1. Используя формулу бинома Ньютона, вычислить (1,0018)5 с точностью до ε = 0,0001.

По приведенной выше формуле имеем:

1,00185 = (1+ 0,0018)5 = 1+ 5 0,0018 + 5 4 0,00182 + ... + 0,00185. 2

Оценим третье слагаемое в этой сумме.

5 4 0,00182 = 10 0,00000324 < 0,00004 < 0,0001, 2

остальные слагаемые еще меньше. Поэтому все слагаемые, начиная с третьего, можно отбросить. Тогда

1,00185 ≈ 1+ 5 0,0018 = 1,009.

Пример 2. Вычислить 4,984 с точностью до 0,01.

	4		4				4			(−0,02)		4		4			4
4,98		= (5 − 0,02)			=	5		1	+				= 5		(1	+ (−0,004))		=
										5
54 (1− 4 0,004 +				4 3			0,0042 −				4 3 2		0,0043 + 0,0044 ).
											2 3
					2

Оценим третье слагаемое:

70

4 3 0,0042 54 = 10−6 6 24 54 = 6 10− 2 = 0,06 . 2

Оценим четвертое слагаемое:

54 4 43 10−9 = 54 24 42 10−9 =104 16 10−9 = 16 10−5 = = 0,00016 < 0,01.

Значит все слагаемые, начиная с четвертого, можно отбросить. Получим

4,984 = 54 (1− 0,016 + 0,000096) = 625 0,984096 = 615,06.

2.1.14 Контрольные вопросы и упражнения

1.Выборка, среди элементов которой нет одинаковых, а порядок записи элементов важен, является _________________ .

2.Выборка, среди элементов которой нет одинаковых, а порядок записи элементов безразличен, является ____________ .

3.Количество размещений с повторениями из n элементов по r элементов определяется по формуле

__________ = ________________________ .

4. Количество сочетаний из n элементов по r элементов определяется по формуле

____________ = ________________________ .

5.Сформулируйте основные правила комбинаторики.

6.Сколькими способами можно выбрать конверт и марку для письма, если имеется 5 конвертов и 4 марки?

7.Сколько пятизначных номеров можно составить из девя-

ти цифр {1,2,3,4,5,6,7,8,9}?

8.Сколькими способами можно составить трехцветный полосатый флаг (все полосы горизонтальные), если имеются ткани пяти различных цветов?

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