Дискретная_математика-Сборник_задач

	б) из х0			в х12
		0	1	2	3	4
			2		3	9
						2
	в) из х1			в х13
		1	2	3	4	5
			12	2	9	13
			33
					2
						10

	5	6	7	8	9	10	11	12
							10
	4						3
		8
			9
				3
		8			4
						1		11
		5
			2			10
								9
								3
	6

6	7	8	9	10	11	12	13
	6
3	4
					3
				9
			8
		14	8
			5				9
						1	11
			5
				2		10
							3

-21-

3. КОМБИНАТОРИКА

Для решения задач из этого раздела необходимо проработать теоретический материал из [7, с. 9-62]. В данном сборнике задач используется следующая терминология.

k-расстановка – всякое упорядоченное или неупорядоченное множество, содержащее k элементов.

k-размещение из n элементов (размещение из n элементов по k) – упорядочен-

ная k-расстановка, составленная из элементов n-элементного множества

(k n). Два k-размещения из элементов одного и того же множества отличаются друг от друга составом или порядком следования элементов; число таких размещений определяется формулой

	Ak	n!		(3.1)
		(n k)!
	n

n-перестановка (перестановка из n элементов) – частный случай k-размещения из n элементов, когда k = n, иначе говоря, это n-размещение из n элементов. Две n-перестановки из элементов одного и того же множества отличаются друг от друга только порядком следования элементов. Число n-перестановок определяется формулой

Pn = n!

(3.2)

k-сочетание из n элементов (сочетание из n элементов по k) – всякая неупо-

рядоченная k-расстановка, являющаяся подмножеством n-элементного множества (k n). Два сочетания из элементов одного и того же множества могут отличаться друг от друга только составом элементов (порядок следования элементов значения не имеет). Число k-сочетаний из n элементов определяется формулой

	Ck	n!		(3.3)
		k!(n k)!
	n

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

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

Число таких размещений

k	(3.4)
An nk

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

-22-

P(n1, n2	,...,nk )	n!		,	(3.5)
		n1!n2!...nk
			!

где n1 + n2 + … + nk = n.

Неупорядоченная k-расстановка с повторениями, которая может включать в себя элементы n типов, называется k-сочетанием с повторениями из элементов n типов (сочетанием с повторениями из элементов n типов по k). Число таких соче-

таний

		k	Ck		(k n 1)!
	Cn P(k, n 1)						(3.6)
					k!(n 1)!
			k n 1

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

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

Процедуру определения типа расстановки можно представить в виде следующей таблицы:

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

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

-23-

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

Пример 3.1. Сколько существует четырехзначных чисел, больших или равных 1000, в которых цифра 3 встречается ровно 1 раз?

Решение. Четырехзначные числа можно рассматривать как расстановки из элементов 10 типов (цифр 0, 1, 2, …, 9) по 4, причем порядок следования элементов имеет значение, и все цифры, кроме цифры 3, могут встречаться несколько раз.

Так как цифра 3 в каждой расстановке может встречаться только один раз и занимает при этом ровно одно из четырех возможных мест, то все множество расстановок можно разбить на 4 непересекающихся подмножества (в расстановках из i-го подмножества цифра 3 занимает i-ое место слева). Пусть цифра 3 стоит на первом месте слева, тогда остальные разряды могут быть заполнены любыми из оставшихся 9 цифр, т.е. могут рассматриваться как размещения с повторениями из элементов 9 типов по 3. По формуле (3.4) число таких размещений равно 93 = 729.

Пусть теперь цифра 3 стоит на втором, третьем или четвертом месте слева. Из трех свободных мест первое слева может быть заполнено любой из оставшихся 9 цифр, кроме 0, т.е. существует 8 способов заполнения этого места. На каждое из следующих двух мест можно поставить любую из 9 цифр. Так как количество вариантов заполнения каждого из этих разрядов не зависит от того, как были заполнены остальные разряды, то можно воспользоваться правилом произведения: число расстановок в каждом из этих подмножеств равно

8 9 9 = 648.

По правилу суммы общее число рассматриваемых расстановок равно

729 + 3 648 = 2673.

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

Решение. Поскольку порядок следования элементов имеет значение и каждая расстановка включает в себя все 8 элементов пяти типов, причем некоторые элементы повторяются, то эти расстановки являются перестановками с повторениями из элементов 5 типов. Их количество определим по формуле (3.5):

P(2, 2, 2, 1, 1)	8!		7! 5040.
	2!2!2!1!1!

ЗАДАЧИ

3.1.Сколько элементов содержит декартово произведение А В С, если

|A| = 12, |B| = 5, |C| = 8?

3.2.Из города А в город В ведут 5 дорог, из В в С – 3 дороги. Сколько дорог ведут их А в С через В?

3.3.Имеется 5 видов конвертов без марок и 4 вида марок одного достоинства. Сколько существует способов выбора конверта с маркой?

-24-

3.4.На вершину горы ведут 5 дорог. Сколькими способами турист может подняться на гору и спуститься с нее? То же, если подъем и спуск должны идти разными путями?

3.5.Сколькими способами можно указать на шахматной доске два квадрата – белый и черный? То же, если нет ограничений на цвет квадратов?

3.6.Сколькими способами можно указать на шахматной доске белый и черный квадраты, если они не должны лежать на одной и той же вертикали и горизонтали?

3.7.В букинистическом магазине лежат 6 экземпляров романа И.С. Тургенева «Рудин», 3 экземпляра романа «Дворянское гнездо», 4 экземпляра романа «Отцы и дети», 5 томов, содержащих романы «Рудин» и «Дворянское гнездо», 7 томов с романами «Дворянское гнездо» и «Отцы и дети». Сколькими способами можно сделать покупку, содержащую по одному экземпляру каждого из романов?

3.8.У некоторых народов принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если общее число имен равно 300, а ему дают не более 3 имен?

3.9.В профсоюзный комитет выбрано 9 человек. Из них нужно избрать председателя, заместителя, секретаря и спортивного организатора. Сколькими способами можно это сделать? То же, если должностей 9?

3.10.4 студента сдают экзамен. Сколькими способами им могут быть поставлены оценки, если никто из них не получил неудовлетворительной оценки?

3.11.В селении проживают 2000 жителей. Доказать, что по крайней мере двое из них имеют одинаковые инициалы.

3.12.На полке находятся m + n различных книг, из которых m книг имеют черные переплеты, а n книг – красные. Сколько существует перестановок этих книг, при которых книги в черных переплетах занимают m первых мест? Сколько существует положений, когда все книги в черных переплетах стоят рядом?

3.13.У одного человека есть 7 книг по математике, а у другого – 9 других книг. Сколькими способами они могут произвести обмен, если 2 книги одного меняются на 2 книги другого?

3.14.В почтовом отделении продаются открытки 10 сортов. Сколькими способами можно купить 12 открыток? 8 открыток? 8 различных открыток?

3.15.Секретный замок с шифром имеет 5 дисков с 12 буквами на каждом. Какое максимальное количество времени может потребоваться человеку, не знающему секретного слова, чтобы открыть замок, если на каждую попытку он тратит 6 секунд?

3.16.Найти число способов расстановки 8 ладей на шахматной доске, чтобы они не били друг друга.

3.17.В магазине продается 4 сорта пирожных. Сколькими способами можно купить 7 пирожных?

3.18.Каким количеством способов можно заполнить карточки «Спортлото» 6 из

49?

-25-

3.19.В «Спортлото» 6 из 49 играют C496 человек. Все они заполнили карточки поразному. Сколько человек угадают 6, 5, 4, 3, 2 и 1 номер?

3.20.Сколько четырехзначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, если: а) ни одна из цифр не встречается более одного раза; б) цифры могут повторяться; в) числа должны быть нечетными (цифры могут повторяться)?

3.21.Из города А в город В ведет k дорог, а в город С – s дорог. В город D из города В ведет m дорог, а из города С – n дорог. Города В и С дорогами не соединяются. Сколько различных автобусных маршрутов можно провести между городами А и D?

3.22.В осеннем семестре студентам читаю лекции по 8 дисциплинам. Сколькими способами можно составить расписание на понедельник, если в этот день должны читаться 3 лекции?

3.23.Дано n точек, никакие три из которых не лежат на одной прямой. Сколько прямых можно провести, соединяя эти точки попарно?

3.24.На плоскости проведено n прямых так, что никакие две из них не параллельны и никакие три не пересекаются в одной точке. Найти количество точек пересечения этих прямых и определить, сколько треугольников образуют эти прямые?

ЛИТЕРАТУРА

1.Ренин С.В. Дискретная математика. Конспект лекций для студентов института социальной реабилитации. – Новосибирск: изд-во НГТУ, 2011.

2.Судоплатов С. В., Овчинникова Е. В. Дискретная математика. – Новосибирск:

Изд-во НГТУ , 2010.

3.Кузнецов О. П. Дискретная математика для инженера. – СПб: Лань, 2007.

4.Новиков Ф. А. Дискретная математика для программистов. – СПб: Питер, 2007.

5.Плотников А. Д. Дискретная математика. – М.: Новое знание, 2006.

6.Шапорев С. Д. Дискретная математика. – СПб: БXВ-Петербург, 2006.

7.Виленкин Н.Я. Комбинаторика. – М.: Наука, 1969.

8.Кофман А. Введение в прикладную комбинаторику. – М.: Наука, 1975.

9.Кристофидес Н. Теория графов. – М.: Мир, 1978.

10.Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. – М.,

Мир, 1965.

-26-

11.Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математи-

ке. – М.: Физматлит, 2009

12.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической ло-

гике и теории алгоритмов. – М.: Физматлит, 2006

13.Ренин С.В. Сборник задач и упражнений по основам теории систем. – Новоси-

бирск: Изд-во НЭТИ, 1985.

14.Ренин С.В. Спецглавы математики. Сборник задач и упражнений. – Новоси-

бирск: Изд-во НГТУ, 2000.

-27-