Каким числом способов можно заполнить анкету содержащую n вопросов

Рецензент: канд. физ.-мат. наук, ст.н.сотр. НИИ ПМК В.И. Шевченко В настоящем пособии рассматриваются основные понятия и алгоритмы теории графов и теории кодирования. Изучение каждой темы сопровождается необходимым теоретическим материалом и примерами решения типовых задач, а также предлагаются задачи для самостоятельного решения.

Учебно-методическое пособие предназначено для студентов второго курса факультета ВМК специальности «Прикладная информатика (в области принятия решений)», изучающих курс “Дискретная математика”.

УДК 519.17 + 519.711.4 ББК В182 © Нижегородский государственный Университет им. Н.И. Лобачевского, 2008 2 Глава 1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ Пусть A и B – множества, тогда отображение f : A B есть:

1) инъекция, если. любые два различных элемента из A отображаются в различные элементы множества B;

2) сюръекция, если для любого yB существует x A, что f x y ;

3) биекция (взаимно-однозначное отображение), если оно инъективно и сюръективно.

A – число элементов конечного множества A (мощность множества).

Правило равенства: если между конечными множествами A и B существует взаимно-однозначное соответствие, то A B.

Правило суммы: если A и B – непересекающиеся конечные множества, то A B A B.

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

Пусть A a1. an — конечное множество. Размещением (перестановкой) из A по k называется упорядоченное подмножество (ai1. aik ) из k элементов множества A. Число всех размещений из n элементов по k обозначается через k An. При подсчете числа размещений замечаем, что первым элементом может быть любой из n элементов множества A, вторым элементом — любой из ( n -1) n! k оставшихся в A элементов и т.д. Поэтому An n(n 1). (n k 1).

n k! Перестановками элементов множества A a1. an называются всевозможные упорядоченные множества из n элементов a1. an. Перестановки из n элементов — частный случай размещений из n элементов по n, поэтому число n всех перестановок из n элементов An n(n 1). 2 1 n! Сочетанием элементов из множества A по k называется неупорядоченное подмножество (ai1. aik ) из k элементов множества A. Число всех сочетаний k n из n элементов по k обозначается через Сn или. В сочетании, в отличие от k размещения, порядок следования элементов не учитывается и из одного сочетания из n элементов по k получается k! размещений. Получаем n n! k Сn.

k k!n k! Сочетанием с повторениями элементов из множества A по k называется неупорядоченный набор (ai1. aik ) из k элементов множества A, в котором элементы могут повторяться. Число всех сочетаний с повторениями из n элеk ментов по k обозначается через Сn. Пусть в сочетании элемент ai встречается si раз, тогда каждому сочетанию поставим в соответствие набор из n -1 нулей и k единиц: 1. 101. 10. 01. 1. Это соответствие между сочетаниями и наборами s1 s2 sn из n -1 нулей и k единиц взаимно однозначно. Так как число наборов длины n k n k 1, содержащих n -1 нулей и k единиц, имеется, получаем k n k 1 n k 1! k n.

k k!n 1! Пример 1.1. Для A a, b, c всевозможными размещениями по 2 элемента будут пары (a, b), (b, a), (b, c), (c, b), (a, c), (c, a), сочетаниями по 2 элемента будут (a, b), (a, c), (b, c), сочетаниями с повторениями из A по 2 элемента — (a, b), (a, c), (b, c), (a, a), (b, b), (c, c).

Всевозможными перестановками элементов множества A a, b, c являются упорядоченные наборы (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a).

Разбиением множества A называется множество его непустых подмножеств A1. Ak, если выполнены условия:

k 1) Ai Aj для всех i j ; 2) A Ai.

iЧисло всех возможных упорядоченных разбиений множества A мощности n на k подмножеств мощностей n1,n2,,nk равно n n! Pn (n1, n2. nk ).

n, n2. nk = n1!n2. nk! Пример 1.2. Дано множество U из 7 элементов. Каким числом способов в нем можно выбрать три подмножества A, B, C так, чтобы выполнялись условия: AC B 2, A BC 2.

Изобразим подмножества A, B, C на диаграмме Венна(см. рис.1.1). Введем обозначения: A1 AC B, A2 ABC, A3 BC.

A A С С B B B B Рис.1.Заметим, что A1 2 (это подмножество размещено в пяти ячейках диаграммы Венна – горизонтальная штриховка), A2 2 (одна ячейка диаграммы – вертикальная штриховка) и A3 3 (две незаштрихованные ячейки диаграммы), т.е.

подмножества A1, A2, A3 задают разбиение множества U. Тогда получаем, что число способов выбора подмножеств A, B, C множества U равно 7! P72, 2, 3 52 23 52 23 42 000.

2! 2!3! Пример 1.3. Сколько различных слов можно составить, переставляя буквы слова «математика» Всего в слове «математика» 10 букв, причем буква «м» встречается 2 раза, буква «а» – 3 раза, буква «т» – 2 раза, буква «е» – 1 раз, буква «и» — 1 раз, буква «к» – 1 раз, тогда число всех различных слов, которые можно составить, равно 10! P102,3,2,1,1,1 151200.

2!3! 2! Пример 1.4. Сколько слов длины 9 в алфавите можно составить при условии, что n1 n2 n3 n4, где ni обозначает число вхождений буквы ai в слово.

Если n1 n2 n3 n4 0, тогда n5 n6 9, и число слов, удовлетворяющих этому условию, равно числу двоичных последовательностей длины 9.

Если n1 n2 n3 n4 1, тогда n5 n6 5, и, рассматривая всевозможные разложения числа 5 на упорядоченную сумму двух слагаемых, получаем, что число слов в этом случае равно P91,1,1,1,0,5 P91,1,1,1,1, 9! 9! 9! + P91,1,1,1,2,3 P91,1,1,1,3,2 P91,1,1,1,4,1 P91,1,1,1,5,0= 2 = 5! 4! 2!3! =96768. Наконец, если n1 n2 n3 n4 2, тогда n5 n6 1, и число слов равно 9! P92,2,2,2,0,1 P92,2,2,2,1,0 2 45 360. По правилу суммы полу2! 2! 2! 2! чаем, что можно составить 512 96768 45 360 142 640 слов.

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

1) никакие две гласные не стояли рядом;

2) не менялся порядок гласных букв;

3) две буквы «с» не шли подряд 4! 1) Имеется P41,1,2 12 перестановок согласных. Для каждого размеще2! ния согласных имеем 5 мест для размещения четырех гласных слова, тогда чисA5 5! ло всех размещений гласных букв слова равно 60. По правилу произ2! 2! ведения получаем 12 60 720 слов.

2) Число размещений согласных букв с учетом того, что буква «c» повторяA8 8! ется дважды равно 840. Очевидно, что на оставшиеся места глас2! 4! 2! ные в указанном порядке размещаются однозначно.

3) Число различных слов, которые получаются перестановками букв слова 8! «комиссия» равно P81,1,1,1,2,2 10 080. Число слов, в которых две бук2! 2! 7! вы «с» идут подряд равно P71,1,1,1,1,2 2 520. Получаем, 2! 10 080 2 520 7 560 слов, в которых две буквы «с» не идут подряд.

n n Бином Ньютона: x yn xk ynk.

k k Формула включений и исключений для n множеств:

i 1 k i1 k 1 <. > <1,2. n>i i 1 k Задачи 1.1. Имеется n1 книг одного автора, n2 – второго, n3 – третьего. Каким числом способов можно выбрать 1) одну книгу;

2) две книги разных авторов;

3) три книги разных авторов;

4) две книги одного автора;

5) три книги одного автора;

6) одну книгу первого автора, две – второго и три – третьего 1.2. Каким числом способов можно заполнить анкету, содержащую n вопросов, если на каждый вопрос можно ответить 1) `да` или `нет`;

2) `да`, `нет`, `не знаю` 1.3. Сколько слов длины n можно составить, если в алфавите k букв Сколько среди них палиндромов, т.е. слов, читающихся одинаково слева направо и справа налево 1.4. Сколько в k-буквенном алфавите имеется слов длины n, в которых любые две соседние буквы различны 1.5. Сколько матриц с m строками и n столбцами можно составить из элементов 0 и 1 1.6. Сколько матриц с m попарно различными строками и n столбцами можно составить из элементов 0 и 1 1.7. Каким числом способов можно на обычной шахматной доске разместить белую и черную ладьи так, чтобы они не атаковали друг друга 1.8. Каким числом способов можно на шахматной доске поместить черного и белого королей так, чтобы они не атаковали друг друга 1.9. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра:

1) больше предыдущей;

2) меньше предыдущей 1.10. В комнате n лампочек.

1) Сколько всего может быть различных способов освещения комнаты 2) Сколько всего может быть разных способов освещения комнаты, при которых горит ровно k (k n ) лампочек 1.11. Сколько имеется вариантов выбора трех призеров среди n участников конкурса:

1) с указанием занимаемых ими мест;

2) без указания мест 1.12. Дано множество U из n элементов и в нем подмножество A из k элементов. Найти число подмножеств B U, удовлетворяющих условию:

1) B A; 6) | B A | 2.

2) B A; 7) | B A | 2;

1.13. Сколько делителей у числа 2048 2310 2880 Сколько делителей k ks имеет число p11. ps, где p1. ps –различные простые числа, k1. ks – целые неотрицательные 1.14. Сколькими способами можно расставить восемь ладей на обычной шахматной доске так, чтобы они не угрожали друг другу, т.е. чтобы никакие две из них не стояли на одной вертикали или горизонтали 1.15. Из колоды, содержащей 52 карты, вынули 10 карт. Сколькими способами это можно сделать В скольких случаях среди этих карт окажется:

1) хотя бы один туз;

2) ровно один туз;

3) ровно четыре туза;

4) не менее двух тузов;

5) ровно два туза 1.16. Имеется колода из 4n карт четырех мастей, по n карт каждой масти, занумерованных числами 1,2. n. Каким числом способов можно выбрать пять карт так, чтобы среди них оказались:

1) пять карт одной масти с последовательными номерами;

2) четыре карты с одинаковыми номерами;

3) три карты с одним номером и две карты с другим;

4) пять карт одной масти;

5) пять карт с последовательными номерами;

6) в точности три карты из пяти с одинаковыми номерами;

7) две карты с одинаковыми, остальные с разными номерами 1.17. Сколько имеется пятизначных десятичных чисел, у которых:

1) все цифры различны;

2) есть одинаковые цифры;

3) все цифры различны, причем последняя не 0;

4) все цифры разные, причем первая не 9, последняя не 0;

5) две первых цифры различны, а две последних –одинаковы;

6) сумма цифр четна 1.18. Каким числом способов можно разместить n различных предметов по k различным ящикам Сколько таких размещений, если в каждый ящик укладывается не более одного предмета 1.19. Если компьютерный пароль содержит пять символов, которые могут быть цифрой или буквой латинского алфавита, то сколько имеется паролей, начинающихся с буквы 1.20. На книжной полке требуется расположить 4 различные книги по математике, 5 различных книг по программированию и 2 различные книги по истории. Сколькими способами это можно сделать, если:

1) нет ограничений по расстановке;

2) все книги по одному и тому же предмету должны стоять вместе;

3) все книги по одному и тому же предмету должны стоять вместе, но книги по математике и программированию не должны стоять рядом 1.21. На книжной полке требуется расположить 4 одинаковые книги по математике, 5 одинаковых книг по программированию и 2 одинаковые книги по истории. Сколькими способами это можно сделать 1.22. Каким числом способов из 10 человек можно выбрать три комиссии, если в первой и во второй комиссиях должно быть по 3 человека, а в третьей человек, и ни один из членов первой комиссии не должен входить во вторую и третью 1.23. Сколько различных слов можно составить, переставляя буквы в слове “программа” 1.24. Каким числом способов можно разместить 7 студентов в трех комнатах общежития, если в одной комнате имеется одно, в другой – два, в третьей – четыре свободных места 1.25. Среди сотрудников фирмы семнадцать человек знают английский язык, десять – немецкий, семеро – французский. Три человека знают английский и французский, два – немецкий и французский, четверо – английский и немецкий.

1) Сколько человек работает в фирме, если каждый знает хотя бы один язык, а два человека знают все три языка 2) Сколько сотрудников, не знающих ни одного иностранного языка, если в фирме работает тридцать человек и никто из них не знает всех трех языков 1.26. На одной из кафедр университета работают тринадцать человек, причем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский, семеро – немецкий, шестеро – французский. Пятеро знают английский и немецкий, четверо – английский и французский, трое – немецкий и французский.

1) Сколько человек знают все три языка 2) Сколько человек знают ровно два языка 3) Сколько человек знают только английский язык 1.27. Из 100 опрошенных студентов 50 программируют на алгоритмическом языке Си++, 53 — на Паскале, 42 — на Бейсике, 15 студентов могут программировать на Си++ и на Бейсике, 20 студентов — на Паскале и Бейсике, 25 — на Си++ и Паскале, а 5 студентов программируют на всех трех языках.

1) Сколько студентов не могут программировать ни на одном из перечисленных языков 2) Сколько студентов программируют хотя бы на одном из перечисленных языков 3) Сколько студентов программируют только на Паскале 4) Сколько студентов не программируют ни на Си++, ни на Паскале 1.28. Дано множество U из n элементов. Каким числом способов в нем можно выбрать три подмножества A, B, C так, чтобы выполнялись заданные условия:

1) n 7, | (A B) C | 6, | C (A B) | 2;

2) n 6, | A B | 5, | A (B C) | 1;

3) n 7, | (A B) C | 4, | C (A B) | 1;

4) n 6, | (A B) C | 4, | A B C | 1;

5) n 8, | A B C | 4, | A B | 1.

1.29. Рассматриваются слова в алфавите a1,a2,,aq. Через ni обозначается число вхождений буквы ai в слово. Требуется подсчитать число слов длины n, удовлетворяющих данным условиям:

1) q 5, n 8, n1 n2 n3 2 ;

2) q 4, n 8, n2 n1 2 ;

3) q 3, n 9, n1 n2 n3;

4) q 3, n 9, 2n1 n2 n3 ;

5) q 5, n 7, n1 n2 n3 2, n4 3.

Глава 2. ТЕОРИЯ ГРАФОВ 2.1. Основные понятия теории графов Граф G (V, E) задается непустым множеством вершин V и множеством ребер E, состоящим из пар элементов V. Если рассматриваются неупорядоченные пары, граф называется неориентированным, если упорядоченные – ориентированным. Если ребро a,b принадлежит графу, то вершины a и b называют смежными. Ребро вида (a,a) называется петлей. Неориентированный граф без петель называют обыкновенным. Во всех задачах этого раздела, где термин “граф” употребляется без уточнения, имеются в виду обыкновенные графы.

Графы G1 (V1, E1) и G2 (V2, E2) называют изоморфными, если существует биекция f : V1 V2, такая, что для любых a,bV1 a,b E1 тогда и только тогда, когда f (a), f (b) E2. Эта биекция f называется изоморфизмом графа G1 на граф G2. Если графы G1 и G2 изоморфны, то пишем, что G1 G2. Отношение изоморфизма графов есть отношение эквивалентности, так как оно рефлексивно, симметрично и транзитивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны.

Степень вершины a – количество смежных с ней вершин, обозначается через d(a). Набор степеней графа – упорядоченная по неубыванию последовательность степеней вершин.

Теорема 2.1.1. Пусть в графе G (V, E) V n, E m, тогда d(a) 2m.

aV Дополнительный граф к графу G (V, E) – такой граф G (V, E ), у кото рого V V, а a,b E тогда и только тогда, когда a,b E.

Подграф графа G (V, E) – такой граф G’ (V ‘, E’), что V ‘ V, E’ E.

Остовный подграф графа G (V, E) – такой граф G’ (V ‘, E’), у которого V ‘ V, E’ E, т.е. остовный подграф получается из исходного графа удалением только ребер без удаления вершин.