Файл: Дискретная математика - учебное пособие.pdf

31 

направо, так и справа налево, например: 2332, 5555, 1001 и т. д.? С нуля числа 
не могут начинаться. 

Первую цифру можно выбрать 7 способами, так как согласно условию с 

нуля  четырёхзначные  числа  начинаться  не  могут.  Вторую  цифру  можно  вы-
брать 8 способами, поскольку теперь можно использовать и нуль. Для выбора 
третьей  и  четвёртой  цифр  нет  вариантов  для  выбора.  Они  должны  повторять 
первые  две  цифры.  Таким  образом,  в  соответствии  с  правилом  произведения 
всего существует 7·8 = 56 искомых чисел. 
 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·   

 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·   

Упражнения 

1.

 Сколько 3-значных чисел можно составить из цифр 1, 3, 4, 

5, 6, если повторы возможны?  

2.

 Сколько 5-значных чисел можно образовать из цифр 2, 8, 9, 

если повторы возможны?  

3.

 Из всех возможных пятизначных десятичных чисел удали-

ли  все числа,  в  которые  входит хотя бы одна из цифр 0, 1,  2,  6, 7. 
Сколько чисел осталось? Повторы цифр возможны.

4.

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

2, 3, 4, 5, если ни одна из цифр не повторяется в числе более одного 
раза? С нуля числа не начинаются.  

5.

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

5,  6,  7,  если  цифра  младшего  разряда  каждого  числа  является  чет-
ной, старшего – нечетной, а на среднюю ограничений нет?  

6.

  Сколько  существует  четырёхзначных  десятичных  чисел, 

которые делятся на 5 без остатка? С нуля числа не начинаются. По-
вторы цифр возможны.  

7.

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

тичных  чисел  (т. е.  одинаково  читающихся  как  справа  налево,  так 
и слева направо, например, 39793; 68286)? С нуля числа не начина-
ются.  
 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·   

2.4 Правило суммы в комбинаторике 

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

1

  и  Р

2

.  Выясним,  сколько  элементов 

содержится в множестве Р

1

∪

Р

2

. На первый взгляд задача представляется слиш-

32 

ком  простой,  даже  примитивной.  Так  оно  и  есть,  но  только  при 

2

1

P

P ∩

=  ∅. 

В этом случае 

|Р

1

∪

Р

2

 | = |Р

1

| + |Р

2

|, 

т. е. если один элемент множества Р

1

 может быть выбран |Р

1

| способами, а эле-

мент множества Р

2

 – |Р

2

| способами, то выбор «либо элемент множества Р

1

, ли-

бо  элемент  множества  Р

2

»  может  быть  выполнен  |Р

1

| + |Р

2

|  способами.  В этом 

состоит правило суммы для двух непересекающихся множеств [8, с. 250]. 

Правило суммы для n попарно непересекающихся множеств имеет вид: 

|Р

1

∪

Р

2

∪

… 

∪

Р

n 

| = |Р

1

| + |Р

2

| + …+ |Р

n

|, 

где Р

i 

∩

Р

j

 = ∅; i, j = 1, 2, …, n; i ≠ j. 

Если  же  Р

1

∩

Р

2

  ≠  ∅,  то  правило  суммы  представляется  более  сложной 

формулой: 

|Р

1 

∪

Р

2

| = |Р

1

| + |Р

2

| – |Р

1 

∩

Р

2

|. 

В [33, с. 140] эту формулу называют формулой включений и исключений, а 

в [51, с. 32] введён термин «принцип включения-исключения». В [42, с. 140] ее 
рассматривают в качестве частного случая формулы перекрытий. 

В случае трех множеств формула для правила суммы ещё усложняется: 

|Р

1

∪

Р

2

∪

Р

3

| = |Р

1

∪

Р

2

| + |Р

3

| – |(Р

1

∪

Р

2

)

∩

Р

3

| = 

= |Р

1

| + |Р

2

| – |Р

1

∩

Р

2

| + |Р

3

| – |Р

1

∩

Р

3

∪

Р

2

∩

Р

3

| = 

= |Р

1

| + |Р

2

| – |Р

1

∩

Р

2

| + |Р

3

| – (|Р

1

∩

Р

3

| + |Р

2

∩

Р

3

| – |Р

1

∩

Р

2 

∩

Р

3

|) = 

= |Р

1

| + |Р

2

| + |Р

3

| – |Р

1

∩

Р

2

| – |Р

1

∩

Р

3

| – |Р

2

∩

 Р

3

| + |Р

1

∩

 Р

2

∩

Р

3

|. 

(2.2) 

В случае n множеств правило суммы имеет вид: 

|Р

1

∪

Р

2

∪

…

∪

Р

n

| = |Р

1

| + |Р

2

| + … + |Р

n

| – (|Р

1

∩

Р

2

| + |Р

1

∩

Р

3

| + 

… + |Р

n–1

∩

Р

n

|) + (|Р

1

∩

Р

2

∩

Р

3

| + |Р

1

∩

Р

2

∩

Р

4

| + 

… + |Р

n–2

∩

Р

n–1

∩

Р

n

|) – … + (–1)

n–1 

|Р

1

∩

Р

2

∩

…

∩

Р

n

|. 

 · · · · · · · · · · · · · · · · · · · · · · ·  

Пример 2.10

  · · · · · · · · · · · · · · · · · · · · · ·   

Из  100  студентов  английский  язык  знают  28  человек,  немецкий  –  30, 

французский – 42, английский и немецкий – 8, английский и французский – 10, 
немецкий и французский – 5, все три языка – 3 человека. Сколько студентов не 
знают ни одного иностранного языка? (Задача из [17, с. 15].) 

Обозначим: |Р

1

| – число студентов, знающих английский язык; |Р

2

| – зна-

ющих немецкий язык; |Р

3

| – знающих французский язык. Тогда 

|P

1

| = 28;    |P

2

| = 30;    |P

3

| = 42. 

33 

Согласно условию: 
|Р

1

∩

Р

2

| = 8 – число студентов, знающих английский и немецкий языки; 

|Р

1

∩

Р

3

| = 10 – число студентов, знающих два языка – английский и фран-

цузский; 

|Р

2

∩

Р

3

| = 5 – число студентов, знающих немецкий и французский языки; 

|Р

1

∩

Р

2

∩

Р

3

| = 3 – число студентов, знающих три языка.  

По правилу суммы для трёх множеств:  

|Р

1

∪

Р

2

∪

Р

3

| = 28 + 30 + 42 – 8 – 10 – 5 + 3 = 80. 

Таким образом, знают хотя бы один иностранный язык 80 студентов, сле-

довательно, ни одного иностранного языка не знают 20 человек. 
 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·   

 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·   

Упражнения 

1.

  32  учащихся  сдавали  экзамен  по  физике  и  химии.  По  две 

отличные оценки получили 10 человек. На «отлично» физику сдали 
14  человек, химию – 18.  Сколько  учащихся не получили ни  одной 
отличной оценки?  

2.

 10 туристов взяли с собой спички, 15 – зажигалки. Ни спи-

чек,  ни  зажигалок  не  взяли  8  человек.  Всего  в  отряде  30 человек. 
Сколько человек взяли и спички, и зажигалки?  

3.

 Из 25 учащихся физический кружок посещают 12 человек. 

Из них 4 человека посещают еще и химический кружок. Ни физиче-
ский, ни химический кружок не посещают 6 человек. Сколько чело-
век посещают только химический кружок?  
 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·   

2.5 Перестановки без повторений 

Постановка задачи. Пусть дано множество  

А = {а

1

, а

2

, …, а

n

}. 

Запишем  его  элементы  в  некотором  порядке  –  получим  упорядоченную 

последовательность длины n. Если в ней некоторые элементы переставить ме-
стами, то получим другую последовательность длины n. Такие последователь-
ности, отличающиеся одна от другой только порядком следования n элементов, 
называются перестановками без повторений. (В [20] применяется термин «рас-
становки».) Требуется определить, сколько всего существует таких последова-
тельностей? 

34 

Формулу для числа перестановок без повторений можно получить на ос-

нове  правила  произведения.  Составим  какую-либо  перестановку  последова-
тельным  выбором  элементов  из  множества  A.  Выбор  первого  элемента  возмо-
жен n вариантами. После его удаления в множестве останется n – 1 элементов. 
Следовательно,  выбор  второго  элемента  возможен  n – 1  способами,  третий  –  
n – 2 способами и т. д. Последний элемент выбирается единственным способом. 
По правилу произведения получаем: 

Р

n

 = n(n–1)(n–2)·…·3·2·1 = n!, 

где Р

n

 – число перестановок из n элементов без повторений. 

Таким образом, формула для числа перестановок из n элементов без по-

вторений имеет вид: 

Р

n

 = n!. 

(2.3) 

 · · · · · · · · · · · · · · · · · · · · · · ·  

Пример 2.11

  · · · · · · · · · · · · · · · · · · · · · ·   

Сколько 4-разрядных чисел, не содержащих повторяющихся цифр, можно 

составить из элементов множества {1, 2, 3, 4}? Перечислить их.

На  место  старшего  разряда  цифру  из  множества  {1,  2,  3,  4}  можно  вы-

брать четырьмя вариантами, из оставшихся – тремя, затем – двумя, после чего 
останется одна цифра:  

4·3·2·1 = 4! = 24, 

то есть всего четырёхзначных чисел, состоящих из цифр множества {1, 2, 3, 4}, 
и не содержащих повторов, существует 24. Это числа: 

1234, 1243, 1324, 1423, 1432, 1342, 2134, 2143, 2314, 2413, 2341, 2431, 
3124, 3142, 3214, 3412, 3421, 3241, 4132, 4123, 4312, 4213, 4321, 4231. 

 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·   

 · · · · · · · · · · · · · · · · · · · · · · ·  

Пример 2.12

  · · · · · · · · · · · · · · · · · · · · · ·   

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

тобус,  если  под  словом  понимать  любую  последовательность  букв,  даже  бес-
смысленную, например, абвосту, вбтсаоу, увтсбоа и т. д.? 

В слове  автобус  все  буквы  разные,  следовательно,  по  формуле  (2.3)  для 

числа перестановок без повторений получаем: 

7! = 1·2·3·4·5·6·7 = 5040. 

 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·   

35 

 · · · · · · · · · · · · · · · · · · · · · · ·  

Пример 2.13

  · · · · · · · · · · · · · · · · · · · · · ·   

Сколько  новых  четырёхзначных  чисел,  не  начинающихся с  нуля,  можно 

образовать за счёт перестановок цифр в числе 2630? 

В заданном числе 4 цифры. Следовательно, по формуле числá перестано-

вок  без  повторений  можно  получить  4! = 1·2·3·4  =  24  перестановки,  из  них 
23 перестановки  –  новые  числа.  Но  не  все  они  являются  искомыми.  Из  них 
необходимо  удалить  все  числа,  начинающиеся  с  нуля,  поскольку  такие  числа, 
как 0236, 0623 и др. нельзя считать четырёхзначными. Если нуль не учитывать, 
то из цифр множества {2, 3, 6} можно образовать 3! = 6 трехзначных чисел без 
повторов.  Столько  существует  бесповторных  четырёхзначных  чисел,  начина-
ющихся с нуля. Удалим их из найденных 23 чисел. Тогда ответ к сформулиро-
ванной задаче примет вид: 23 – 6 = 17. 

Эта задача легко решается и без обращения к формуле числа перестано-

вок, вполне достаточно только правила произведения. 

Так  как  нулю  запрещается  занимать  место  старшего  разряда,  то  выбор 

первой цифры возможен тремя способами. И для второй цифры существует три 
варианта выбора – за счёт возврата нуля. На третье место можно выбрать одну 
цифру из двух. Оставшаяся цифра займёт место младшего разряда. Таким обра-
зом, по правилу произведения количество искомых чисел равно: 

3·3·2·1 – 1 = 17. 

 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·   

 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·   

Упражнения 

1.

 Сколько  существует  10-значных  десятичных  чисел,  если 

каждая цифра входит в число точно один раз и если каждое число 
начинается с упорядоченной последовательности 298 и оканчивает-
ся упорядоченной последовательностью 345?  

2.

 Сколько новых чисел, не начинающихся с нуля, можно по-

лучить, переставляя цифры в числе 12340?  

3.

 Сколько существует способов записи выражения 

A + b + c + d + e + f 

(здесь  плюс  –  знак  арифметического  суммирования),  если  учесть 
коммутативность операции арифметического сложения?