elem_mat_copy

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

О п р е д е л е н и е 3.

× …×		=	{ , ,…,	| , = 1,2,…, }.

Правило произведения

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

Одним из основных правил, которые применяются при решении таких задач, является правило произведения.

Пусть элемент можно выбрать		способами, а элемент
― способами, тогда пару элементов		можно выбрать
способами. Это правило следует из определения,			декартова про-
изведения двух множеств.
З а м е ч а н и е: Это правило распространяется и на
множеств.
Приведем примеры решения комбинаторных задач с помо-
щью правила произведения.
З а д а ч а 1. Пусть дан упорядоченный набор длины , т.е.
каждый элемент которого может принимать одно
из двух, ,…значений, ,	(например, 0 или 1). Требуется узнать, сколько

будет таких наборов (их называют двоичными). Для решения построим клетку с ячейками, каждую из которых можно заполнить двумя способами (например, 0 или 1; или «и» и «л» и т.п.):

2 способа

2 способа

2 способа

…

2 способа

1

2

3

…

n

Следовательно,

число двоичных наборов длины n равно .

В частности, таблица истинности для логической формулы с2 n

высказывательными переменными имеет

строк,

так как каж-

дая строка таблицы представляет собой

двоичный набор длины n.

2

З а д а ч а 2.

Пусть дано множество

.

Нужно определить число всех его

подмножеств

. Пусть

= {

, ,…, }

. Тогда этому подмножеству можно поставить в(соответст)

-

41

вие двоичный набор длины n, в котором на i-ом месте стоит 1, если , либо 0, если . Тогда | ( )| = 2 .

Перестановки, размещения и сочетания

Перестановки. Одна из наиболее распространенных комбинаторных задач такова: сколькими способами можно переставить элементы некоторого конечного множества? Например: сколько 9-значных чисел с различными цифрами можно соста-

вить из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9?

При каждой перестановке n-элементного множества образуется упорядоченный набор длины n, все элементы которого различны. Число всех возможных перестановок в данном множестве совпадает с числом всех таких наборов.

О п р е д е л е н и е 4: Перестановкой из n элементов назы-

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

Число перестановок из n элементов обозначают Рn. Выведем формулу для вычисления Рn.

Пусть некоторое множество М состоит из n элементов. Рассмотрим произвольную перестановку элементов этого мно-

жества, то есть упорядоченный набор (		), где аi		М.
Элемент а1 в этом наборе можно выбрать,n	различными спосо-
	,…,

бами (взять любой элемент из множества M); элемент а2 выбирается n-1 способами (так как один элемент уже использован для а1, а элементы в перестановке не повторяются); а3 выбирается n-2 способами («заняты» два элемента) и т.д. Последний элемент аn можно выбрать только одним способом. По правилу

занных наборов.		∙( −1) ∙( − 2)∙ ∙2∙1				ука-
произведения, будет всего		− 2)∙	( −1) ∙
туральное число,	1∙2∙ ∙(			, где	n ― на-
Произведение

большее 1, называется n-факториалом и обозначается n! Дополнительно полагают: 1!=0!=1. Таким образом,

= !.

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

42

1, 2, 3, 4, 5, 6, 7, 8, 9 можно составить 9!, то есть 362880 9-значных чисел с различными цифрами.

Размещения. Другой важный тип комбинаторной задачи можно продемонстрировать на следующем примере: сколькими способами из 10 учебных предметов можно составить расписание занятий на один день, включив в него 4 различных предмета? Очевидно, что один вариант расписания может отличаться от другого как предметами, так и порядком их следования. Поэтому данную задачу можно сформулировать так: сколько существует упорядоченных наборов длины 4 с различными элементами, взятыми из 10-элементного множества? Число всех таких наборов называется числом размещений из 10элементовпо4.

О п р е д е л е н и е 5: Размещением из n элементов по m

(m≤n) называется упорядоченный набор длины m различными элементами, взятыми из некоторого n-элементного множества.

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

Обозначим число размещений из n элементов по n через	и
выведемформулудлявычисления .

Рассмотрим n-элементное множество M и произвольный упорядоченный набор ( , ,…, ), где ai M для всех i, i = =1,2,...,m. Элемент а1 выбирается n различными способами; a2 выбирается n-1 способами и т.д. Последний элемент аm можно выбрать (n - (m - 1)), то есть (n - m + 1) способами. По правилу произведения, имеется всего ∙ ( −1) ∙( − 2)∙ ∙( − +1) указанных наборов.

Искомаяформулаимеетвид:

Am n (n 1) (n 2) ... (n m 1)		(1)
n
Заметим, что произведение в правой части состоит в точности
из mмножителей. Этооблегчаетприменениеформулы.
Вернемся к задаче о расписании. Число всех вариантов распи-
сания Имеет местодругаяформула для	:= 10∙9∙8∙7 = 5040		.
можнопосчитатьпоформуле(1):

43

	Am	n!
		(n m)!
	n

Дляеевыводадостаточнопреобразоватьправуючастьформулы(1).

Сочетания. Рассмотрим теперь такую задачу: сколькими способами можно из 10 учебных предметов выбрать 4 для составления расписанияна день?Заметим, чтов этой задаче, в отличиеот задачи предыдущего пункта, не требуется составлять расписание, то есть упорядочиватьпредметы. Нужно узнать, сколькими способами из множества, состоящего из 10 элементов, можно выбрать 4-элементное подмножество (а не упорядоченный набор). Число таких подмножеств называют числом сочетаний из 10 элементов по 4.

О п р е д е л е н и е 6: Сочетанием из n элементов по m (m≤n) называется m-элементное подмножество n-элементного множества.

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

Число сочетаний из n элементов по m обозначают С . Выведем формулудлянахожденияэтогочисла.

Пусть дано множество из n элементов. Возьмем произвольное m-элементное подмножество этого множества и составим из него все возможные упорядоченные наборы. Их будет m! Проделав такое действие с каждым подмножеством, получим множество всех упорядоченныхнаборов длины m, то есть всех размещений из n элементов

по m. Их число

=

Такимобразом,

(	!	)!	.
(	!	)!	=	∙ !. Отсюда:	=	!∙(	!	)!	.

Иногда последнюю формулузаписывают по-другому:

Cnm Anm

Pm .

Применивполученнуюформулу,найдем

:

44

C4		10!		7 8 9 10	210	.
10		4! 1 2 3 4

Число 210 дает ответ задачи, поставленнойвначалеэтогопункта.

Упражнения

1. Вычислите:

	A4	A4		C4			1	C62	1	C83	1	C153
	12	11		21			3		28		65
		A103	; б) C193 C194		C203
а)						; в)			P3 A53		.

2. а) Сколькими способами можно расположить пять книг разных авторов на книжной полке в один ряд?

б) Сколькими способами можно переставить буквы в слове «выборка»?

в) Сколько всего сигналов можно составить, меняя порядок семи различных флагов: красного, синего, зеленого, желтого, коричневого, черного и белого?

г) Сколькими способами можно распределить 10 различных писем по 10 различным конвертам?

д) Сколькими способами 10 человек могут встать в очередь друг за другом?

3. а) Сколько различных четырехзначных чисел можно составить из цифр 1,2,3,4,5, если цифры в числе не повторяются?

б) Сколько различных четырехзначных чисел можно составить из цифр 0,1,2,3,4,5, если цифры в числе не повторяются?

в) Сколько можно составить пятизначных телефонных номеров из всех цифр так, чтобы в каждом отдельном номере все цифры были различными?

г) Команда из пяти человек выступает в соревнованиях по плаванию, в которых участвует еще 20 спортсменов. Сколь-

45

кими способами могут распределиться личные места, занятые членами этой команды?

4. Докажите тождество:

		A6	A5	(n 4)2			Ann k2 Ann k1	k	2
		n	n
							An
	а)		A4		;	б)			;
			n				n k

	Ak	Pn
		P
	n
	в)	n k .

Практическое занятие №9

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

Свойства сочетаний

Рассмотрим некоторые свойства сочетаний.

Свойство 1:				= 1;	=	. Это сразу следует из
выведенной формулы=			.
Свойство 2:							.
В самом деле, сумма+в			левой части дает число всех подмно-
			+ +		= 2
жеств данного множества.
Свойство 3:				. Может быть доказано преобра-
зованием обеих частей=.
Свойство	4:				(для n, m 1) . Может
быть доказано	преобразованием правой части.
		=		+			≥

Треугольник Паскаля

Существует эффективный способ вычисления значений при различных конкретных значениях n и m.

46

Выпишем в первой строке значение						.	Во второй
строке выпишем значения			,	то есть числа=1,11. В третьей
строке выпишем значения					, то есть, соответственно,
числа 1,	2, 1.	В следующей, ,			строке	будут	значения
следующая, , ,	― соответственно, числа 1, 3, 3, 1. Каждая по-
	строка,	будет содержать все значения					при зна-

чениях m = 0, 1,…, n для n = 4, 5, ...

Заполнение каждой строки, начиная с третьей, происходит следующим образом, в соответствии со свойствами сочетания:

1.Крайние слева и справа элементы любой строки равны 1 (свойство 1).

2.Каждый внутренний элемент строки равен сумме соседних

сним слева и справа элементов предыдущей строки (свойство 4).

Получаем следующую фигуру (при n = 0, 1, 2, З, 4, 5):

n = 0				1
n = 1				1	1
n = 2			1	2	1
n = 3		1		3	3	1
n = 4	1		4	6	4		1
n = 5	1	5	10		10	5	1

Построен так называемый треугольник Паскаля для n от 0 до 5. Его построение по описанному принципу может быть продолжено как угодно далеко. В любой строке треугольника равны любые два числа, равноотстоящие от концов (по свойству 3).

Заметим, что самая верхняя строка имеет номер 0; следующая ― номер 1 и т. д.; номер любой строки, начиная со второй, совпадает с числом, следующим за левой единицей. Кроме того, в любой строке с номером n сумма всех ее членов равна 2n, Это следует из свойства 2.

Треугольник Паскаля позволяет находить без вычислений по формуле любое значение . Например, найдем . Для этого ищем строку, в которой после левой единицы находится число 5, затем, начиная от этого числа, отсчитываем третье; это и будет

искомое значение. Таким образом,

= 10.

47

Формула бинома Ньютона

Выведем формулу, позволяющую возводить двучлен (бином) (а+b) в любую целую неотрицательную степень. Это формула бинома Ньютона. Она имеет следующий вид:

( + ) = ∙ ∙ + ∙		∙ +	∙	.	∙ + +
+	∙ ∙	+ ∙	∙

Докажем данную формулу методом математической индукции по n, где n≥0.

1.Формула верна при n = 0, 1, 2. В самом деле,

(a b)0 1 C00 ;

(a b)1 a b C10 a1 b0 C11 a0 b1 ;

(a b)2 a2 2ab b2 C20 a2 b0 C21 a1 b1 C22 a0 b2
2.Пусть формула верна при n = k. Докажем ее при n = k + 1.;
			( + )	∙	= ( + ) ( + ) =				.
чим: = ( ∙ ∙ +					∙	+ +	∙	∙ )( + )
Раскрыв скобки и сгруппировав слагаемые по степеням а, полу-
( + )			= ∙		∙ +	+	∙ ∙ +.		+
С учетом	свойства 4 и того, что					+	∙	и∙	,
			+	+	∙ ∙
имеем:			=	∙		=	= 1	=	= 1
( + )					∙ +		∙ ∙ + +
Итак,		индукция завершена, значит истинность							формулы
			+ ∙	∙	+	∙	∙ .

доказана.

В формуле бинома Ньютона для (а + b)n сумма степеней а

и b в каждом слагаемом равна n. Числа									называются
биномиальными коэффициентами. При							вычислении биномиаль-
							,	,…,
ных коэффициентов удобно применять треугольник Паскаля.
В качестве примера найдем: а) (a + b)5;								б) (х2-1)4:
а)	∙	∙	+	∙	∙	+	∙	∙	+
+	∙	∙	+	∙	∙	+	∙	∙	=

48

a5 5a4b1 10a3b2 10a2b3 5ab4 b5;

б)	(	− 1)8	= (	6	) ∙(−1)4		+4(2		)	4∙(−1)	+
+6(	)	∙(−1)	+4(		) ∙(−1) +(15)x					∙(−1)	=
		x 4x			6x	4x				1
		− 4			+21	−4		+1.

Легко убедиться, что хорошо известные формулы сокращенногоумножения для (a + b)2 и (a + b)3 представляют собой частные случаи формулыбиномаНьютона.

Упражнения

1.Докажите:

а) C50 C51 C52 C53 C54 C55 ;

б)	m Cm n Cm 1
		n	n 1 ;
	Cm 1	Cm	n 1
			m 1.
в)	n 1	n

2.Напишите разложение по формуле бинома Ньютона и упростите при необходимости:

а) (a + b)4;

б) (a ― b)4;

в) (a + 2b)5;

г) (a – 2b)5;

1		7
		a b
	2
д) (1 + 2x)5; е)			; ж)

	2	5
a
	b		;

	1	5
a
з)	a		;

	1	8
x		x
	2			(1	2)5 ; л) (1 2)5 ; м)				(a 6)6 ;
и)			; к)

49

н) (b 6)6 ;			о) ( 6 12)4 ;

ж)

к)

	2		5
a

b ;

(1 2)5 ;

з)

л)

	1		5
a

a ;

(1 2)5 ;

		1	(
	п)			3		15)6		;
		27

		1			8
	x			x
		2
и)						;
	(a
м)				6)6		;

3.Найдите:

а) шестой член разложения (1 ― 2z)21;

1 15

x

б) шестой член разложения x ;

1

13

x

в) пятый член разложения

x

;

(

z)10

г) пятый член разложения

z

;

д) два средних члена разложения (a3-ab)23;

3

1 18

x

е) в разложении

x3

член, не содержащий x;

1

18

1

z3

ж) в разложении

член, не содержащий z;

1

12

a

з) в разложении

a

коэффициент при а8;

x

3

12

и) в разложении

3

x

коэффициент при х4;

к) x, если третий член разложения (х +xlg x)5 равен 106 .

50