Добавил:

guap4736_vkclub152685050 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Национальный минерально-сырьевой университет «Горный»

Предмет:

Дискретная математика

Файл:

Дискретная математика

.pdf

Скачиваний:

Добавлен:

11.08.2019

Размер:

1.66 Mб

Скачать

☆

<<< < Предыдущая 1 2 34 / 114 5 6 7 8 9 10 11 > Следующая >>>

vk.com/club152685050 | vk.com/id446425943

Глава 2. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

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

элементов конечного множества.

Задача пересчета – это задача определения количества элементов множества.

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

§1. Размещения, перестановки, сочетания

Доказательства многих комбинаторных тождеств основываются на

правилах суммы и произведения.

Правило суммы

Рассмотрим два непересекающихся множества X ,Y : X Y , пусть элемент x можно выбрать из множества X m способами, а элемент y из Y - n способами, тогда выбор одного из элементов x или y

можно сделать m+n способами.
Правило произведения
Если элемент x можно выбрать из множества X m способами, а элемент
y из множества Y - n способами,	тогда упорядоченную пару элементов (x, y)
можно выбрать m n способами.
Опр. Размещением из n элементов по m элементов называется
упорядоченный набор m различных	элементов из исходных n элементов. Число

размещений обозначается символом Am .
n
Опр. Перестановкой из n элементов называется размещение из n по n .
Число перестановок находится по формуле	P An .
	n	n
Опр. Сочетанием из n элементов		по m элементов называется

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

символом Cnm Подчеркнем, что сочетание – неупорядоченный	набор
элементов.

Теорема (о числе размещений). Число размещений из n элементов по m может быть найдено по следующей формуле:

vk.com/club152685050 | vk.com/id446425943

Am	n!	.


n	(n m)!

Доказательство (основано на правиле умножения).

Первый элемент размещения может быть выбран n способами, после чего второй элемент размещения может быть выбран (n-1) способом и т.д.; для выбора последнего m–го элемента останется (n - (m-1)) способ, таким образом, используя правило умножения, получим:

		Am n(n 1)(n 2)...(n (m 1))		n!	, ч.т.д.

				(n m)!
		n		(n m)!
Следствия.
1.	P An n!,
	n	n
2.	C m	n!	.


	n	m!(n m)!
		m!(n m)!

Доказательство следствия 2. Все размещения из n элементов по m можно получить, если для каждого сочетания из n по m сконструировать всевозможные перестановки по m элементов, число которых Pm m! и

воспользоваться правилом умножения Anm m!Cnm . Отсюда и вытекает формула 2, ч.т.д.

Теорема (формула бинома Ньютона)

a b n Cnm an mbm . m 0

Доказательство этой формулы следует из того, что после перемножения всех скобок в левой части каждое слагаемое будет иметь вид a n mbm , и после приведения подобных членов получится данная формула.

В связи с этим числа Cnm называют биномиальными коэффициентами. По определению полагают Cn0 Сnn 1.

Пример.

(a b)4 a4 4a3b 6a2b2 4ab3 b4 .

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

1.	C m	C n m		свойство симметрии биномиальных коэффициентов.
	n		n
2.	C m		C m C m 1		,
	n 1		n	n
	т.к.		n 1 !			n!		n!

			m!(n m 1)!			m!(n m)!		m 1 !(n m 1)!
							32

vk.com/club152685050 | vk.com/id446425943

3. Cnm 2n , следует из формулы бинома Ньютона при a b 1.

m 0
n	1 n Cnm 0 , следует из бинома Ньютона при
4.	1 n Cnm 0 , следует из бинома Ньютона при	a 1, b 1.
m 0
Замечание. Пусть A конечное множество мощности n. Формула (3)
дает ещё одно доказательство, что мощность булеана множества А равна 2n .
Опр.	Размещением с повторением из n по m называется упорядоченный

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

обозначается символом Anm .

Так как любой элемент размещения с повторением может быть выбран n способами, то Anm n m .

Пример. Сколько четырехзначных чисел можно составить из цифр

{1,2,3}?

Ответ: A34 34 81 .

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

символом Cnm . Можно доказать (доказательство мы опускаем), что Cnm Cnm m 1 .

Пример. Для множества A a,b,c, d сочетаниями с повторениями по три будут следующие:

aaa	bbb		ccc	ddd
aab	bbc		ccd	ddc
aac	bbd		ccb	ddb
aad	bcd
abb
acc
add
abc
adc
				C43 3 1 20
abd		Cnm Cnm m 1		C43 3 1 20
		33

vk.com/club152685050 | vk.com/id446425943

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

Anm A43 43 64 . Попытайтесь объяснить, как соотносятся на этом примере

числа Cnm Cnm m 1 и Anm n m .

Пример. В магазине есть три типа пирожных. Сколькими способами можно выбрать 4 пирожных?

	C 4	C 4	6!	15 .
Ответ: C 4

3	3 4 1	6	4! 2!

Теорема (о числе разбиений множества).

Число разбиений конечного множества X, содержащего n элементов на

непересекающиеся подмножества

X1 , X 2 , ..., X k , содержащие по

n1 , n2 , ..., nk

(n n n

... n

) элементов соответственно равно C n1n2 ...nk

n1!n2

!...nk !

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

правила умножения.

Замечание.

Частным

случаем этой

формулы

является уже знакомая

формула числа сочетаний C n1

C n2

C n1n2

(n n

n) .

n1!n2!

Пример. 28 костей домино раздаются 4 игрокам. Сколько различных раскладов можно сделать? Непосредственное решение может быть таково:

C 7

28!

21!

14!

28!

7! 21!

7! 14!

7! 7!

7!4

§2. Формула включений и исключений

Пусть А – конечное множество, А – его мощность. Пусть A1 , A2 – некоторые подмножества

конечного множества Х.	А2	А1

(1)

A1 A2

т.к. при

сложении

множеств число общих

элементов было включено в сумму дважды, то это число надо исключить.

Формула (1) называется формулой включений и исключений для двух подмножеств. Можно сравнить с формулой сложения вероятностей

P(A1 A2 ) P(A1 ) P(A2 ) P(A1 A2 ) .

vk.com/club152685050 | vk.com/id446425943

Следующая формула легко выводится из (1):

A1 A2 A3 A1 A2 A3 A1 A2 A1 A3 A2 A3 A1 A2 A3

Обобщим формулу (1) на n подмножеств.

Теорема (мощность объединения конечных множеств по формуле

включений и исключений)

Пусть A1, A2 , ... , An

– некоторые подмножества конечного множества Х,

тогда

(2)

Ai Aj

Ai Aj Ak

... ( 1)n 1

A1 A2 ... An

i 1

1 i j n

1 i j k n

Доказательство теоремы проводится методом математической индукции.

Из (2), например, следует:

A1 A2 A3 A1 A2 A3 A1 A2 A1 A3 A2 A3 A1 A2 A3

Следствие 1. Пусть

Ai X \ Ai , i 1, n

–

множество элементов, не

принадлежащих множеству

Ai , тогда число элементов, не принадлежащих ни

одному из множеств A1 A2

... An , равно

i 1

(3)

Ai Aj

Ai Aj Ak

...

i 1

1 i j n

1 i j k n

( 1)n

A A ... A

Пример.

В стае бродячих собак 4

голодные, 3 злые, 3 лохматые. Две

злые – голодные, среди лохматых – одна злая. Ни одна из собак не обладает всеми признаками. Сколько собак в стае?

Решение.			Введем обозначения A1				голодные, A2 злые,			A3
лохматые, тогда
	A1	4		A1 A2		2		A1 A2 A3	0
	A1	4		A1 A2		2		A1 A2 A3	0
	A2	3		A2 A3		1
	A2	3		A2 A3		1
	A3	3		A1 A3	1
	A3	3		A1 A3	1
A A1		A2	A3 – стая
			35

vk.com/club152685050 | vk.com/id446425943

3
A		Ai		Ai Aj	A1 A2 A3	4 3 3 2 1 1 0 6 .
	i 1		1 i j 3

Пример. В группе из 10 человек пятеро хорошо бегают, четверо – стреляют, семеро – плавают. Среди бегунов 3 стрелка и 4 пловца. Среди стрелков трое пловцов. Двое хорошо выполняют все три дисциплины.


Сколько человек не умеет ничего?
Решение. Обозначим			A1 множество				бегунов, A2 стрелков,				A3
пловцов, X группа (универсум)
	A1	5		A1 A2		3		A1 A2 A3		2
	A1	5		A1 A2		3		A1 A2 A3		2
	A2	4		A2 A3	4			Х	10
	A2	4		A2 A3	4			Х	10
	A3	7		A1 A3		3
	A3	7		A1 A3		3

A A1 A2 A3 – спортсмены,

A1 A2 A3 A X A1 A2 A3 10 (5 4 7 3 4 3 2) 2 .

Пример. Дано универсальное множество U и три его подмножества A, B

и C. Известно, что | U | 14 , | A | 7 , | B | 6 , | C | 5 , | A B | 5 , | A C | 3 , | B C | 2 , | A B C | 1 . Найти | A B | , | A B C | , | A B C | .

Решение. Воспользуемся формулами принципа включения и исключения

| A B | | A | | B | | A B | и

| A B C | | A | | B | | C | | A B | | A C | | B C | | A B C |.

1. Найдем | A B | . Имеет место равенство A ( A B) ( A B) . Множества A B

и A B не пересекаются, поэтому | A | | A B | | A B | . Отсюда

| A B | | A | | A B | 7 5 2 .

2. Найдем | A B C | . Аналогично предыдущему случаю

| B C | | A B C | | A B C | . Отсюда | A B C | | B C | | A B C | 2 1 1.

3. Найдем | A B C | . По закону де Моргана A B C A B C . Отсюда,

поскольку U ( A B C) ( A B C) , имеет место соотношение

| A B C | |U | | A B C | .

| A B C | | A | | B | | C | | A B | | A C | | B C | | A B C | 7 6 5 5 3 2 1 9 .

Следовательно, | A B C | 14 9 5 .

vk.com/club152685050 | vk.com/id446425943

Опр. Беспорядком на множестве {1, 2, 3, …, n} называется такая перестановка элементов исходного множества, в которой ни один элемент не стоит на своем месте.

( 1)

Следствие 2. Число беспорядков равно

i 1

k 2

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

Пусть Х – число всех перестановок из

n элементов,

тогда

n !.

Пусть Ai – множество перестановок,

в которых i-й элемент стоит на

своем

месте,

остальные

(n-1) занимают

произвольные

места,

тогда

(n 1)!,

i – й элемент можно выбрать n способами;

Ai Aj

–

множество перестановок, в которых

два элемента стоят на

своих

местах,

остальные

(n-2) занимают

произвольные

места,

тогда

A A

(n 2)!, пару элементов (i, j) можно выбрать

C 2

способами, и т.д.;

– множество перестановок, в которых хотя бы один элемент стоит

i 1

на своем

месте,

тогда

–

количество

беспорядков, которое

можно

i 1

вычислить с помощью формулы (3):

n! n(n 1) Cn2 (n 2)! Cn3 (n 3)! ...( 1)n Cnn 0 !

i 1

(n 2)!

3)! ( 1)n

(n n)!

2!(n

2)!

3!(n 3)!

n!(n n)!

n n!

( 1)m

...( 1)

n !

2! 3! 4!

2! 3!

m 2

§3. Производящие функции

		a0 , a1, a2 , .. .
Рассмотрим числовую последовательность	aк к 0	a0 , a1, a2 , .. .
Опр. Производящей функцией числовой	последовательности

называется символ вида (степенной ряд)


a0 a1t a2t 2	... ant n ... ak t k .
	k 0

aк

к 0

Если этот ряд сходится к функции A(t) , то эта функция также называется производящей функцией последовательности ak :

vk.com/club152685050 | vk.com/id446425943


	A(t) ak t k .									(1)
				k 0
Опр.	Экспоненциальной			производящей				функцией		числовой
последовательности ak называется степенной ряд вида
		a2			ak
	E(t) a0 a1t		t 2	...		t k ...		ak	t k .	(2)

	2!				k!		k 0 k!
Замечания: 1. Если последовательность ak ограничена,										то ряд (1)

сходится при t 1 , а ряд (2) при t .

2. Если A(t) производящая функция последовательности ak , то элементы последовательности находятся как коэффициенты ряда Маклорена:

ak	A(k ) (0)	.
ak		.
	k!
	3.		Если	E(t) экспоненциальная			производящая	функция
последовательности a				k	, то коэффициенты: a	k	E(k ) (0) .
				k		k

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

Примеры.

																						1
1)	1, 1, 1, ... , 1, ...																	t k				1			,
1)	1, 1, 1, ... , 1, ...																	t k				t			,
																		k 0			1	t
																															1
2)	1, 1, 1, 1,											... , ( 1)k , ...									( 1)k t k										1			,
2)	1, 1, 1, 1,											... , ( 1)k , ...									( 1)k t k									1	t			,
																					k 0									1	t
																													1
3)	1, 2, 3, ... , k 1, ...																	(k 1)t k											1				,

																											(1 t)				2
																			k 0								(1 t)
																									1
4)	1, a, a2 , ... , ak , ...																ak t k								1				,
4)	1, a, a2 , ... , ak , ...																ak t k						1 at						,
																			k 0				1 at
		1			1						1									1					1
5)	1,	1	,		1		, ... ,				1		, ...							1	t k ln				1			,
5)	1,		,				, ... ,						, ...								t k ln							,
	2		3								k							k 1		k			1		t
				1				1				1					( 1)		k 1							( 1)				k 1
6)	1,			1		,		1	,			1			, ... ,		( 1)				, ...					( 1)						t k		ln(1 t) ,
6)	1,		2			,	3		,		4				, ... ,			k			, ...								k			t k		ln(1 t) ,
			2				3				4							k						k 0					k
			1				1			1						1						1
7)	1, 1,		1			,	1		,	1				, ... ,		1		, ...				1		t k		et .
7)	1, 1,					,			,					, ... ,				, ...						t k		et .
			2				6		24							k!					k 0	k!

vk.com/club152685050 | vk.com/id446425943

Опр. Функция 1 t n Cnk t k называется производящей функцией

k 0

конечной последовательности числа сочетаний из n по k.

Свойства производящих функций

Пусть A(t) производящая функция последовательности ak , а B(t) производящая функция последовательности bk , , , тогда

1. A(t) B(t) производящая функция последовательности

ak bk .

2. C(t) A(t) B(t) производящая функция последовательности с

общим членом ck a0bk a1bk 1

... ak 1b1 ak b0 .

a0bk

a1bk 1

... ak 1b1

Опр.

Последовательность

ck k 0

ak b0 k 0

называется сверткой последовательностей ak и bk .

Пример 8. Найти

свертку

последовательностей

ak 1, 1,1, ... и

bk 2, 2, 2, ... .

Решение. Так как

A(t) 1 t t 2 ... t n 1 ...

B(t) 2 2t 2t 2 ... 2t n 1

...

то C(t) A(t) B(t)

удвоенная производящая

функция

1 t 2

последовательности натуральных чисел. Следовательно,

последовательность

ck 2, 4, 6, ..., 2k, ... последовательность четных чисел.

§4. Линейные однородные рекуррентные соотношения

с постоянными коэффициентами

Опр.

Рекуррентным

соотношением

(уравнением) называется

соотношение вида

an k F(n, an , an 1, ..., an k 1)

n 0,1, 2, ...

которое позволяет находить все члены последовательности an , если заданы ее первые k членов: a0 , a1, ..., ak 1 (начальные условия).

Замечание. Рекуррентные соотношения часто называют рекуррентными уравнениями (дискретными уравнениями) относительно неизвестной функции

vk.com/club152685050 | vk.com/id446425943

натурального аргумента	ak f (k), k N0 N 0 . В технической литературе
в роли k выступает дискретное время.
Опр. Пусть дана последовательность чисел a0 , a1, ..., aп , ... .
1. Соотношение вида
an k	р1an k 1 р2an k 2 ... рk an 0	(1)

называется линейным однородным рекуррентным соотношением с постоянными коэффициентами pi , i 1, k .

2. Последовательность an , члены которой удовлетворяют соотношению (1), называется рекуррентной или возвратной последовательностью.

Замечание. Рекуррентная последовательность полностью определяется заданием соотношения (1) и ее первых k членов.

Примеры.

1.Числа Фибоначчи an 2 an an 1, здесь a0 , a1 заданы;

2.Геометрическая прогрессия bn 1 q bn ;

3.Найти несколько первых членов последовательности, заданной

соотношением an 2 2an 1 an 0,

a0 1,

a1 2.

Решение. Так как an 2 an 2an 1, то последовательно находим

n 0	a2 1 2 2 3
n 1	a3 2 3( 3) 8
n 2	a4 3 2 8 19
n 3	a5 8 2( 19) 46

и an 1, 2, 3, 8, 19, 46, ... .
Для	нахождения	производящей			функции	рекуррентной
последовательности используют следующий алгоритм.
Умножим соотношение (1)				на t n k и просуммируем по n:

	an k t n k p1			an k 1t n k	... pk ant n k	0 ,
	n 0		n 0		n 0

	amt m p1t			amt m ... pk t k amt m 0 .
	m k			m k 1	m 0

Каждое слагаемое выразим через производящую функцию A(t) amt m :

m 0

<<< < Предыдущая 1 2 34 / 114 5 6 7 8 9 10 11 > Следующая >>>

Соседние файлы в предмете Дискретная математика

#
11.08.20191.66 Mб54Дискретная математика.pdf
#
10.08.2019171.64 Кб26тест дискретка 3.pdf
#
10.08.2019158.13 Кб45Тесты по Дискретной математике 2.pdf
#
10.08.2019184.97 Кб78Тесты по Дискретной математике.pdf