Пак Г.К. - Дискретная математика

Министерство образования Российской Федерации

ИНСТИТУТ ТЕХНОЛОГИИ И БИЗНЕСА

ДИСКРЕТНАЯ МАТЕМАТИКА

Находка

2001

Пак Г.К. Дискретная математика. Учеб. пособие. – Находка: Институт технологии и бизнеса, 2001. - 109с.

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

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

Рецензенты: зав. кафедрой теории функций и функционального анализа ДВГУ, д-р физ.-мат. наук, профессор Фролов Н.Н.,

декан факультета математики и математического моделирования ДВГУ, профессор Осипов В.Б.

ISBN –

Пак Г.К., 2001

Институт технологии и бизнеса, 2001

ОГЛАВЛЕНИЕ

1.3.Декартово произведение…………………………………………………. 10

1.4.Бинарные отношения……………………………………………………... 10

1.5.Функции…………………………………………………………………… 11

1.6.Эквивалентность………………………………………………………….. 12

1.7.Частичный порядок………………………………………………………. 13

1.8.Мощность множества……………………………………………………. 14

1.9.Счетные множества………………………………………………………. 15

1.10.Метод полной математической индукции………………………………. 16

Глава 2. Комбинаторика…………………………………………………………… 19

2.1.Размещения……………………………………………………………….. 19

2.2.Сочетания…………………………………………………………………. 20

2.3. Бином Ньютона…………………………………………………………… 21

2.4.Размещения с повторениями…………………………………………….. 22

2.5.Сочетания с повторениями………………………………………………. 23

3.5.Эквивалентные формулы…………………………………………………. 32

3.6.Элементарная конъюнкция. Элементарная дизъюнкция………………. 33

3.7.Совершенная дизъюнктивная нормальная форма…………………….. 34

3.8.Совершенная конъюнктивная нормальная форма…………………….. 37

4.1.Замыкание множества булевых функций………………………………. 40

4.2.Классы функций, сохраняющих константы……………………………. 41

4.7.Теорема Поста о функциональной полноте……………………………... 45

4.8.Предполные классы………………………………………………………. 46

5.1.Степень вершины графа………………………………………………….. 48

5.2.Способы задания графа………………………………………………….. 49

5.3. Изоморфизм графов……………………………………………………… 49

5.4.Подграф, маршрут, цепь, цикл…………………………………………… 50

5.5.Связность…………………………………………………………………. 51

5.6.Геометрическая реализация графа………………………………………. 52

5.7. Эйлерова характеристика………………………………………………… 52

5.11.Деревья……………………………………………………………………. 58

5.12.Корневое дерево………………………………………………………….. 59

6.1.Алфавитное кодирование……………………………………………….. 65

6.2.Алгоритм Маркова Ал. А. распознавания однозначности декодирования…………………………………………………………….. 66

6.3.Неравенство Макмиллана……………………………………………….. 68

7.1.Машина Тьюринга……………………………………………………….. 75

7.2.Язык конфигураций………………………………………………………. 76

8.1.Интервалы…………………………………………………………………. 85

8.2.Сокращенная ДНФ……………………………………………………….. 87

10.6.Канонические уравнения………………………………………………… 101

10.7.Операции над ограниченно-детерминированными функциями………. 102

10.8.Полные системы………………………………………………………….. 105 Список литературы………………………………………………………………….. 107

ПРЕДИСЛОВИЕ

Учебное пособие содержит первоначальные сведения в объеме типовой программы по теории множеств, комбинаторике, алгебре логики, теории графов и сетей, теории кодирования и декодирования, теории алгоритмов. Теоретический материал сопровождается упражнениями, снабженными ответами или указаниями к их выполнению. Применяются следующие основные обозначения:

N – множество натуральных чисел, т.е. N {1, 2, 3, };

N0 – множество целых неотрицательных чисел, расширенное множест-

во натуральных чисел, т.е. N0 = {0, 1, 2, 3, …};

Z – множество целых чисел, т.е. Z = {0, 1, 2, …};

Q– множество рациональных чисел, Q ={m/n :m, n Z ; n 0};

R– множество вещественных чисел;

C – множество комплексных чисел;

х M означает "x – элемент множества M";

N M означает "N есть подмножество множества M";

N M N M и M N ;

Cnr – число сочетаний из n по r ;

Anr – число размещений из n по r ( r-перестановки из n ); Crn (П) – число сочетаний с повторениями из n по r ;

Arn (П) – число размещений с повторениями из n по r ;

■ – конец доказательства, этот же знак ставится после формулировки теоремы, если её доказательство не приводится;

– из предложения следует ;

– предложения и равносильны;

5

ГЛАВА 1. МНОЖЕСТВА

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

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

ем также, что все встречающиеся множества являются подмножествами некоторого универсального множества U.

Свойства отношения включения:

1)A A (рефлексивность);

2)( A B, B A ) A = B (антисимметричность);

3)( A B, B C ) A C (транзитивность).

Если множество B не является подмножеством множества A , то существует х B такой, что x A . Но если B – пустое множество , то такого элемента нет. Поэтому считаем A для каждого множества A .

Упражнение

Докажите, что

1){ };

2)если A , то A = ;

3){{1, 2},{2, 3}} {1, 2, 3}.

1.1.Способы описания множеств

Способ 1. Перечисление всех элементов множества. Например, запись M2n ={…, 2–2, 2–1, 20, 21, 22 , …} означает, что множество M2n состоит из

всех целых степеней числа 2.

Способ 2. Описание характеристического свойства, которым обладают элементы множества.

6

Способ 3. Описание правил, по которым строятся элементы множества.

Пример. 1. 1 M2n .

2.M2n 2 M2n и /2 M2n .

3.Других элементов в M n нет.

2

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

1.2. Операции над множествами

Пересечением множеств A и B называется множество всех элементов, которые принадлежат A и B одновременно, т.e.

A B ={x: x A и x B }.

Свойства пересечения:

1)A A = A (идемпотентность);

2)A B =B A (коммутативность);

3)( A B ) C = A ( B C ) (ассоциативность);

4)( A B ) A , ( A B ) B ;

5)A ;

6)A B = A A B.

Объединением множеств A и B называется множество всех элементов, которые принадлежат A или B или A и B одновременно, т.е.

A B ={ x: x Aили x B }.

Свойства объединения:

1)A A = A (идемпотентность);

2)A B = B A (коммутативность);

3)( A B ) C = A (B C ) (ассоциативность);

4)A ( A B), B ( A B ) (принцип расширения);

5)A = A ;

6)A B = A B A.

ТЕОРЕМА. 1) A ( B C ) = ( A B ) ( A C ); 2) A (B C ) = ( A B ) ( A C ).

Доказательство. 1) x A (B C ) x A, или x B C x A,

или x B , x C . В обоих случаях по принципу расширения x A B и

(( A B ) ( A C )) ( A (B C )). Из этих двух включений и следует доказываемое равенство (дистрибутивность объединения множеств относительнопересечения слева).

7

Второе утверждение теоремы (дистрибутивность пересечения относительно объединения) доказывается аналогично.

Разностью множеств A и B называется множество всех элементов, которые принадлежат A , но не принадлежат B

A \ B = { x : x A и x B }

(в иных обозначениях CАВ – дополнение B до множества A ). Свойства разности множеств:

1)A \ B A ;

2)( A \B ) B ;

3)( B A ) (( A \ B ) B = A );

4)A \ = A.

ТЕОРЕМА.

1.A \ ( B C ) = ( A \ B ) ( A \C );

2.A \ ( B C ) = ( A \ B ) ( A \C );

3.( A B ) \C = ( A \C ) ( B \C ) (дистрибутивность разности относительно объединения справа);

4.A ( B \C ) = ( A B ) \ ( A C ) (дистрибутивность пересечения относительно разности справа). ■

Упражнение

Докажите, что

1)A \ ( B C ) = ( A \ B ) \C ;

2)A \ ( B \C ) = ( A \B ) ( A C );

3)( A \B ) (B \ A ) = ( A B ) \ ( A B ).

Дополнением множества A называется множество U \ A = A. Свойства дополнения:

(Август де Морган (1806–1871) – английский математик).

Действия над множествами иллюстрируются с помощью кругов Эйлера или диаграмм Венна (см. рис. 1.1-1.5).

Симметрической разностью множеств A и B называется

A B = ( A \B ) ( B \ A ).

Её свойства: 1) A B B A;

2)A (B С) (A B) C;

3)A (B С) (A B) (A C);

4)A = A ;

5)A A = ;

6)A U = A;

7)A B =C B C = A C A B.

Относительно операций сложения и умножения множества образуют коммутативное, ассоциативное кольцо с единицей U и с делителями нуля. Семейство всех подмножеств множества A называется булеаном множества A и обозначается P(А).

Пример. A a,b,c , P(А) , a , b , c , a,b , a,c , b,c , a,b,c .

Упражнения

1.Докажите свойства множеств:

а) A = ( A B ) ( A (–B )); б) A ((– A ) B ) = A B;

в) A B = ( A B ) ( A (– B )) ((– A ) B);

г) A ( A B ) = A .

2.Докажите свойства булеана:

9

1.3. Декартово произведение

Декартовым (прямым) произведением множеств A1 ,..., A n назы-

вается множество всех упорядоченных наборов элементов из A1 ,..., A n

A1 ... Аn= {<a1 ... an>: a1 A1,..., an An},

гдe <a1...an>=<b1...bn> a1=b1 ... an=bn. Если A1 =…= Аn = А,

то A1 ... Аn называется декартовой степенью множества A и обознача-

ется An .

Свойства декартова произведения:

1)A, B, что A B B А;

2)A, B, C, что A (B С) (А B) С;

3)(A B) C (A C) (B C);

4)(A\ B) C (A C)\ (B C), A (B \C) (A B)\(A C);

5)An 1 A An.

Примеры: [а, в] [с, d] – прямоугольник, R2 – плоскость, R3 – трехмерное пространство.

Подмножество R декартового произведения множеств А1,...,Аn называется п-местным отношением на множествах А1,...,Аn. Если R Xn, то имеем п-местное отношение на X.

1.4. Бинарные отношения

Бинарным отношением между элементами множеств A и B на-

зывается любое подмножество R множества A B. Если R A2 , то имеем бинарное отношение на множестве А. Вместо < x , y> R часто пишут хRy.

Пример.

A ={2, 4}, B ={2, 3, 5}, A B ={<2, 2>,<2, 3>,<2, 5>,<4, 2>,<4, 3>,<4, 5>}, R = {<2, 2 >, <2, 3>, <2, 5>}.

Дополнением бинарного отношения R между множествами

A и B называется множество –R = ( A B )\R. Обратным отношением

для R называется R–1 = {< x , y> : <y, x > R}. Образом множества Х

относительно R называется множество R(X)= {y: x X : < x , y > R}.

Здесь R A B, X A , R(X) B . Прообразом Y относительно R называется R–1(Y).

Композицией бинарных отношений R1 A B и R2 B C называется множество R1 R2 = { x , z : y: < x , y> R1, < y, z > R2}. Свойства бинарных отношений:

1)(R–1)–1 = R;

2)(R1 R2)–1 = R1–1 R2–1;

10

3)(R1 R2)–1 = R1–1 R2–1;

4)–(R–1) = (–R)–l;

5)R1 (R2 R3) (R1 R2) R3;

6)(R1 R2 )–1 = R21 R1 1 ;

7)(R S)(X) S(R(X));

8)(R S) T (R T) (S T);

9)(R S) T (R T) (S T) .

Замечание к свойству 9. Обратное не всегда верно. Пример:

A = x , B {y, t}, C {z}, R = < x,y> A B , S= < x, t > A C,

T y, z , t, z B C, R S = (R S) T = , R T= < x, t > ,

S T = < x, z > (R T) (S T) = < x, t > .

1.5. Функции

Областью определения бинарного отношения R называется

R = { x : y: < x, y > R }.

Областью значений бинарного отношения R называется множество

R = {y: x: < x, y > R}.

Бинарное отношение f A В называется функцией из A в B , если

1) f = A , f B,

2) x A : (< x , y1 > = < x , у2 >) ( у1 = у2 ). т.е. для каждого

пишут у = f( x ), f: A B , при этом х называют аргументом, а у – значением функции f в точке x . Функция f называется инъекцией A в B , если из того, что x1 х2 , следует, что f (x1) f (х2) . Если f = B , то f называется сюръекцией A на B . Если f – инъекция и сюръекция одновременно, то говорят, что f осуществляет взаимнооднозначное соответствие между A и В (биекция). Подстановкой множества A называется взаимнооднозначное отображение A на себя. Множество всех функций из A в B обозначается BА. Если в определении функции множество A заменить на декартово произведение А1 ... Аn, то получим определение

п-местной функции.

Упражнение

Докажите, что

1)R–1 = R, R–1 = R;

2)R1 R2 R 1( R1 R2 ) ;

3)f( A B ) = f( A ) f(B ), f( A B ) f( A ) f(B ) для любой функции f;

4)f––1( A B ) = f––1( A ) f––1(B ) , f––1( A B ) = f––1( A ) f––1(B ).

11

1.6. Эквивалентность

Бинарное отношение iA ={< x, x >: x A } называется диагона-

метричным, если < x, y > R < y, x > R; антисимметричным, если

Классом эквивалентности элемента x по эквивалентности R называет-

ся x /R = { у: < x, y > R }.

Пример. М = 1; 2; 3; 4; 5 , R = (1; 1), (1; 2), (2; 1), (2; 2), (3; 3), (4; 4), (5; 5) . Является ли бинарное отношение R рефлексивным, симметричным, транзитивным, иррефлексивным, антисимметричным?

Все пары (1; 1), (2; 2), (3; 3), (4; 4), (5; 5) принадлежат R, по-

этому R рефлексивно. Пары (1; 2) и (2; 1) входят в R, все остальные пары симметричны. Это означает, что R симметрично. Все тройки пар, в которых третья получается “склеиванием” первых двух, входят в R од-

новременно. Это такие тройки пар: (1; 1), (1; 2), (1; 2) , (1; 2), (2; 1), (1; 1) , (1; 2), (2; 2), (1; 2) . Следовательно, R транзитивно. Пара (1; 1)

принадлежит R, поэтому R неиррефлексивно. Для двух разных элементов 1 и 2 обе пары (1; 2) и (2; 1) входят в R, т. е. R неантисимметрично.

ТЕОРЕМА. Множество A распадается на классы эквивалентности элементов множества A по эквивалентности R.

Доказательство. (z x /R) ( x /R = z/R). Действительно, по условию

< x, z > R. Если t z/R, то < z, t > R. Отсюда < x , t > R t x /R z/R x /R. Если t x /R и z x /R, то < x, t > R , < x, z > R <z, t> R t z/R x/R z/R. Из включений z/R x /R z/R и следует искомое равенство.

Пусть z x/R y/R. Тогда z x /R, z y/R x /R = z/R = y/R x /R = y/R. Итак, два класса эквивалентности либо не пересекаются, либо совпадают. Так как < x, x > R, то x x /R и, следовательно, каждый элемент множества A попадает в один из классов эквивалентности. Тем самым доказано, что множество A – это объединение непересекающихся классов эквивалентности. ■

Множество классов эквивалентности множества A по эквивалентности R называется фактор-множеством A по R и обозначается A /R.

12

Упражнение

Докажите, что

1) если R рефлексивно (иррефлексивно, симметрично, антисимметрич-

но), то R 1 тоже рефлексивно (иррефлексивно, симметрично, антисимметрично);

2) если R1 и R2 рефлексивны, то R1 R2 , R1 R2 , R1 R2 тоже рефлек-

сивны;

3) если два слова A и B в некотором алфавите принадлежат бинарному отношению R тогда и только тогда, когда AВ ВА, то R эквивалентно.

1.7. Частичный порядок

Бинарное отношение называется предпорядком на A , если оно рефлексивно и транзитивно. Рефлексивное, транзитивное и антисимметричное отношение на множестве A называется частичным порядком на A . Частичный порядок часто обозначается символом .

Будем писать x y, если х у и x у. Частичный порядок на множестве A называется линейным, если для любых элементов x и у из A или x у или у x . Множество с заданным на нем частичным порядком (линейным) называется частично (линейно) упорядоченным.

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

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

Примером частично, но не линейно упорядоченного множества может служить множество всех пар натуральных чисел N 2 со следующим порядком: (< x, у > < x , y >) ( x x , у y ). Примером частично упорядоченного множества является множество всех подмножеств данного множества X, упорядоченное по включению M M , если M M , где M, M P(X).

Элемент a частично упорядоченного множества A называется

максимальным, если а x a = x , и минимальным, если x a a =x.

Элемент a из A называется наибольшим элементом, если х A : x а, и наименьшим, если x A : а x . Всякий наибольший элемент является максимальным, а всякий наименьший элемент – минимальным. Обратное, вообще говоря, места не имеет. Например, в тривиальном частично упорядоченном множестве (т.е. в котором a b a = b) всякий

13

элемент является как максимальным, так и минимальным, но не наибольшим и, соответственно, не наименьшим. Верхней (нижней) гранью подмножества B частично упорядоченного множества A называется любой элемент a из A такой, что b a (a b) для любого b B . Точной верхней (нижней) гранью подмножества B A называется наименьшая верхняя (наибольшая нижняя) грань B . Точная верхняя грань множества B обозначается suрВ (супремум), а точная нижняя грань –

inf B (инфимум). Линейный порядок на множестве A называется пол-

ным, если каждое непустое подмножество множества A имеет наименьший элемент. В этом случае множество A называется вполне упорядо-

ченным.

Пусть A и B – частично упорядоченные множества и f – функ-

ция из A в B . Если x1, x2 A : x1 x2 => f(x1) f(x2), то функция называется монотонной. Если f – взаимно однозначное соответствие меж-

ду A и B и f и f –1 монотонны, то f называется изоморфизмом частично упорядоченных множеств A и B , а множества A и B называ-

ются изоморфными.

Упражнения

1.Докажите, что множество всех подмножеств данного множества частично упорядочено отношением включения .

2.Всякое частично упорядоченное множество содержит не более одного наибольшего (наименьшего) элемента. Докажите.

3.Постройте линейный порядок на N2.

1.8. Мощность множества

Множество A называется эквивалентным множествуB, если между A и B можно установить взаимнооднозначное соответствие. В этом случае применяется обозначение A ~ B .

Свойства эквивалентности:

1)A ~ A (рефлексивность);

2)если A ~ B, то B ~ A (симметричность);

3)если A ~ B, B ~ С, то A ~ С (транзитивность).

Мощностью множества A называется класс всех множеств, эк-

вивалентных множеству A, и обозначается он через A или card A. Эквивалентные множества называют равномощными. Обозначим через 0 мощность пустого множества , через 1 мощность множества {0} , че-

рез 2 мощность множества {0, 1},..., n = card {0, 1, ..., n – 1}. Если существует натуральное n такое, что n = card A, то множество называют

конечным, а n – числом элементов множества A, n = | A |. Всякое подмножество конечного множества конечно, объединение конечного числа конечных множеств конечно, прямое произведение конечного числа

14

конечных множеств конечно. Множество, не являющееся конечным,

называется бесконечным.

ТЕОРЕМА. Конечное множество неэквивалентно собственному подмножеству.

1.9. Счетные множества

Множество, эквивалентное множеству N0 ={0, 1, 2, ...}, называ-

ется счетным, и его мощность обозначается .

ТЕОРЕМА. Бесконечное множеств содержит счетное подмножество.

A B {a0}также конечно). Следовательно, существует a1 A \{a0},

что A \{a0, a1} бесконечно, и т.д. Полoжим f(0) = a0, f(1) = a1,... Тогда f осуществляет взаимнооднозначное соответствие между множествами

N0 и {a0, a1, ...}. ■

ТЕОРЕМА. Множество бесконечно тогда и только тогда, когда оно эквивалентно некоторому собственному подмножеству. Доказательство. Пусть A бесконечно, B = {b0, b1 , ...} – его счетное подмножество. Тогда A = (B ( A \ B )) ~ (B \{b0}) ( A \ B ) = A \{b0}

Обратное очевидно. ■

ТЕОРЕМА. Подмножество счетного множества счетно или конечно. Доказательство. Достаточно доказать для N0 . Пусть I N0 и I беско-

нечно. Построим f: N0 I. Возьмем в качестве f(0) наименьший эле-

мент множества I, в качестве f(1) наименьший элемент множества I\{f(0)} и т.д.; f осуществляет взаимнооднозначное соответствие между

N0 и I.

ТЕОРЕМА. Если A и B счетны, то A B счетно.

15

Способ нумерации Ai :

1 2 3 4 5 6 7 …

1 2 3 4 5 6 7 …

1 2 3 4 5 6 7 …

ТЕОРЕМА. Если A бесконечно, B – конечное или счетное множест-

Упражнение

Докажите, что

1)множество целых чисел Z счетно;

2)множество рациональных чисел Q cчетно;

3)множество пар < x, у >, где x, у Q счетно;

4)множество многочленов от одной переменной с целыми коэффициентами счетно;

5)множество алгебраических чисел, т.е. являющихся корнями многочленов от одной переменной с целыми коэффициентами, счетно.

1.10.Метод полной математической индукции

Индукция – переход от частного к общему, дедукция – переход от общего к частному. Для конечного множества полная индукция – синоним полного перебора. Только совершив полный перебор элементов конечного множества, можно сделать общий вывод, обладают ли каким-либо свойством элементы этого множества. Принцип математической индукции позволяет осуществить в некоторых случаях полный перебор элементов бесконечного множества.

Доказательство утверждения A(n) методом полной математической индукции заключается в следующем:

1)Проверяется справедливость утверждения дляn = 1 (база индукции).

2)Предполагается справедливость этого утверждения для n k, где

k 1(гипотеза индукции).

16

3) С учетом этого предположения устанавливается справедливость его для n k 1(индукционный переход).

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

некоторого утверждения, зависящего от n р ( p Z ), проводится сле-

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

1)Устанавливается справедливость утверждения для n = р.

2)Предполагается справедливость утверждения для n k p.

3)Исходя из этого предположения, устанавливается его справедливость для n k 1.

Пример. Докажите, что n5 n делится на 30 для натурального числа n.Доказательство проведем методом полной математической индукции по числу n. При n = 1 получаем, что 0 делится на 30. База индукции есть. Предположим, что при n k, утверждение верно, т.е. k5 – k

делится на 30. Пусть n = k+1. Тогда (k+1)5 – (k+1) = k5 +5 k4 +10 k3 + 10 k2 + 5 k + 1 – k – 1 = (k5 – k) + 5 k (k + 1)(k2 + k +1). Первое из слагае-

мых делится на 30 по гипотезе индукции. Так как либо k, либо k + 1, либо k2 + k +1 делится на 3, а произведение двух последовательных целых чисел k (k + 1) делится на 2, то и второе слагаемое делится на 30. Утверждение доказано методом полной математической индукции.

Пример. Докажите, что 13 + 23 + 33 + … + n3 = n2 (n + 1)2/4.

База индукции. При n = 1 выражения, записанные слева и справа, принимают значение 1. Это значит, что база индукции есть.

Гипотеза индукции. Предположим, что при n = k, где k 1, имеет

место равенство

13 + 23 + 33 + … + k3 = k2 (k + 1)2/ 4.

Право перехода. Пусть n = k + 1. Тогда

13 + 23 + 33 + … + k3 + (k + 1)3 = k2 (k +1)2/ 4 + (k +1)3 = = (k + 1)2 ( k2/ 4 + k + 1) = (k + 1)2 (k + 2)2/ 4.

Получили значение выражения слева доказываемого равенства при n = k+1. Утверждение доказано методом полной математической индукции.

Пример. Для каждого b > 1 и натурального n > 1 верно неравенство Бернулли bn 1 + n (b – 1).Докажите.

n = 1; b b. Верное неравенство. n = k, гдеk 1; bk 1+k (b – 1). n = k + 1; bk+1 = bk b b (1+ k (b – 1)) = b + kb – k = (k + 1)(b – 1) + 1.

Упражнение

Докажите методом полной математической индукции:

1)1 + 2 + 3 + … + n = n (n + 1)/ 2;

2)1 + 3 + 5 + … + (2n – 1) = n2;

3)12 + 22 + 32 + … + n2 = n (n + 1)(2n + 1)/ 6;

17

4)14 + 24 + 34 + … + n4 = n2 (n + 1)2 (2n + 1)2/ 36;

5)1/ 1 2 + 1/ 2 3 + 1/ 3 4 + … + 1/ n (n + 1) = n / (n + 1);

6)2n > n;

7)2n > n2, n 5;

8)np – n делится на p, p – простое число;

9)4n + 15n – 1 делится на 9;

10)если |Х| = m , то |Хn| = mn; (Х – множество, |Х| – число элементов);

11)если Х1 , …, Хк – конечные попарно непересекающиеся множест-

ва, то |Х1 … Хк| = |Х1| + … + |Хк|.

18

ГЛАВА 2. КОМБИНАТОРИКА

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

Правило суммы. Если объект A может быть выбран m способами, а объект В другими n способами, то выбор "либо A , либо B " может быть осуществлен m n способами.

Правило умножения. Если объект A может быть выбран m способами и после каждого из таких выборов объект B в свою очередь может быть выбран n способами, то выбор "A и B" в указанном порядке может быть осуществлен mn способами.

Набор элементов ai1 , ,air из множества M a1, ,an называ-

ется выборкой объема r из n элементов. Выборка называется упорядоченной, если порядок следования элементов в ней задан. Упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными.

Упражнение

Докажите правила суммы и умножения как теоремы.

2.1. Размещения

Размещением из n по r называется упорядоченная выборка объема r из n различных элементов ((n – r)-перестановка). Например, все размещения из четырех объектов A,B,C,D по 2:

AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC.

Мы имеем (n – 1) размещений, в которых на первом месте стоит первый элемент; (n – 1) размещений, в которых на первом месте стоит второй элемент; (n – 1) размещений, в которых на первом месте стоит третий элемент, ; ;(n 1) размещений, в которых на первом месте стоит n-й

элемент, т.е. An2 n(n 1). Возникает гипотеза, что

Ank = n (n – 1)(n – 2)(n – 3) ... ( n – k +1).

Перейдем к нахождению Ank 1 при такой гипотезе. Каждое раз-

мещение из n по k может дать n k размещений из n по k 1, после присоединения одного из объектов, не вошедших в него, отсюда

Ank 1 (n k) Ank n(n 1)(n 2)(n 3) (n k).■

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

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

Anr n!/(n r)!. Договоримся также, что 0! 1.

Упражнения

1.Выведите формулы Anr nAnr 11, Anr Anr 1 rAnr 11.

2.Пусть | X | n, |Y | m. Докажите, что число всех взаимноодно-

значных отображений X в Y равно Amn.

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

2.2. Сочетания

Сочетанием из n по r называется неупорядоченная выборка объема r из n элементов, т.е. любое подмножество, состоящее из r элементов, взятых из множествa n элементов. Число всех различных сочетаний

из n по r обозначается Cnr. Заметим, что Cn0 1, Cn1 n, Cnn 1.

Доказательство. Фиксируем один из объектов. Все сочетания разбиваются на два класса: класс сочетаний, не содержащих фиксированный

элемент (в нем Cnr 1 сочетаний), и класс сочетаний, содержащих фикси-

рованный элемент (в нем Cnr 11 сочетаний). Отcюда и следует формула Паскаля. ■

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