11

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

Зададим некоторое множество {а1, а2, а3, …, аm}. Любой набор (кортеж, комбинация) элементов этого мн6ожества будем называть соединением. Например: а1 а2, а1 а2 а2\ а2 а3, а1 а2 а3 а1 а2, …

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

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

	размещения с повторениями.
	Формула для вычисления числа размещений:
	Аn	m!			(1)
		m n !
	m
	Формула для вычисления числа размещений с повторениями
	~n	m	n		(2)
	Am

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

Ясно, что сочетания – это частный случай размещений.

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

ния с повторениями

Формула для вычисления числа сочетаний:

	Сmn			m!				(3)
				п! m n !
	Формула для вычисления числа сочетаний с повторениями
	~n			n		m n 1 !		(4)
	Сm	C m n 1
						п! m 1 !

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

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

	это перестановки с повторениями.
	Формула для вычисления числа перестановок Рп = п !			(5)
	Формула для вычисления числа перестановок с повторениями
	рп k1, k 2,..., кп	п!		(6)
		k1!...кп!
	где кi (i=1… п) – число повторений в перестановке i-го элемента.

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

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

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

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

12

2.1.Задачи

№2.1. Сколько различных слов можно получить, переставляя буквы в слове «математика», «информатика», «кукуруза»?

№2.2. В студенческой группе из 25 человек требуется избрать старосту, профорга и физорга. Сколькими способами это можно сделать?

№2.3. В студенческой группе 15 юношей и 10 девушек. Требуется избрать делегацию на конференцию состоящую:

а) из 5 человек, б) из трех юношей и двух девушек.

Сколькими способами это можно сделать?

№2.4. В лифт семиэтажного дома на первом этаже вошли 4 человека. Сколькими способами они могут вый-

ти а) на разных этажах, начиная со второго,

б) на одном и том же этаже, в) на 6-м этаже,

г) два на одном, а два на другом этаже, д) три на одном, а один на другом этаже?

№2.5. В лифт семиэтажного дома на первом этаже вошли 8 человек. Сколькими способами они могут выйти а) на разных этажах, начиная со второго, б) на одном и том же этаже, в) на 6-м этаже,

г) шесть на одном, а два на другом этаже, д) три на одном, а 5 на другом этаже,

е) сколько всевозможных способов выхода из лифта?

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

жества {4, 5, 6, 7}?

№2.7. Сколько нечетных четырехзначных чисел можно получить, используя цифры 1, 2, 3, 4, 5?

№2.8. Номерные знаки автомобилей начинаются с трех букв латинского алфавита, совпадающих по начертанию с русскими. Затем следуют три цифры и еще две буквы. Сколько всего автомобилей можно зарегистрировать по такому принципу?

№2.9. Четверо студентов сдали экзамен. Сколькими способами могут распределиться между ними оценки?

№2.10. Сколько чисел меньших миллиона, можно записать с помощью цифр 9, 8, 7?

№2.11. На товарном складе имеется обивочная ткань шести видов. Требуется обить 36 стульев для общежития. Сколькими способами это можно сделать?

№2.12. В урне 3 белых и 7 черных шаров. Вынимаются 5 шаров. Сколькими способами это можно сделать?

Асколькими способами можно взять 2 белых и 3 черных шара? А сколькими способами можно взять 2 шара одного цвета и 3 шара другого цвета?

№2.13. Ребенок играет с 4 буквами разрезной азбуки А, А, М, М. Сколько различных слов он может получить?

№2.14. Абонент забыл две последние цифры телефонного номера.

а). Какое наибольшее число попыток предпримет абонент, чтобы набрать правильный номер? б). А если он знает, что они различны?

в). А если он знает, что они обе четные?

г). А если он знает, что они различны и обе нечетные? д). А если он знает, что они различны и первая четная?

№2.15. из 25 экзаменационных билетов 5 «хороших». 3 студента берут билеты. Сколькими способами они это могут сделать? Сколько существует способов получения «хорошего » балета

а) одним студентом? б) двумя студентами? в) тремя студентами?

№2.16. Имеется группа из 12 человек. Сколькими способами могут распределиться их дни рождения по месяцам?

№2.17. В партии 50 изделий, из которых 5 бракованных. Отбирается 6 изделий. Сколькими способами среди них могут оказаться 2 бракованных?

№2.18. Буквенный замок содержит 5 дисков, расположенных на одной оси. Каждый диск разделен на 5 секторов с буквами. Замок открывается при определенной комбинации букв, установленных на каждом диске. Какое наибольшее число попыток потребуется для открытия замка, если код неизвестен?

№2.19. Сколько натуральных чисел, меньших 100, при а) возведении в квадрат дают число, оканчивающееся на 1; б) возведении в куб дают число, оканчивающееся на 11?

№2.20. Сколько двузначных чисел делится на 18?

№2.21. Сколько трехзначных чисел делится на 36?

13

№2.22. На восьми карточках написаны числа: 2, 4, 6, 7, 8, 11, 12, 13. Берутся две карточки. Сколько дробей возможно получить? А сколько из них сократимы?

№2.23. Имеются отрезки длиной 1, 3, 5, 7, 9. Сколько треугольников из них можно получить?

№2.24. Из 10 вопросов студент знает 5. Берется 3 вопроса. Сколько существует комбинаций, при которых студент знает а) все три вопроса; б) 2 вопроса; в) хотя бы один вопрос?

№2.25. Имеются 5 лотерейных билета стоимостью по 1 рублю, З. билета стоимостью по 3 рубля и 4 билета стоимостью по 5 рублей. а). Сколькими способами можно выбрать три билета? б). А сколько из них содержат хотя бы два билета одной стоимости?

№2.26. Монета подбрасывается 10 раз. Сколько возможных комбинаций положения монеты? А комбинаций, при которых орел выпадет три раза?

№2.27. При игре в преферанс трем игрокам раздается по 10 карт 4 мастей, а две карты остаются в прикупе. У одного игрока на руках оказалось 6 карт бубновой масти. Он сносит две карты других мастей и берет прикуп. Сколько возможно комбинаций прикупа? А сколько возможно комбинаций набора карт бубновой масти у игрока, взявшего прикуп?

№2.28.В розыгрыше первенства по лапте участвуют 18 команд, среди которых 5 команд считаются сильными. Команды разбиваются по жребию на две группы по 9 команд в каждой.

а) сколькими способами это можно сделать?

б) сколькими способами все сильные команды окажутся в одной группе?

в) сколькими способами две сильных команды окажутся в одной группе, а три в другой?

№2.29. В урне находятся 15 пронумерованных шаров. Из урны вынимается шар, его номер записывается и шар возвращается в урну. Произведено 5 испытаний.

а) сколькими способами могут расположиться записанные номера? б) сколькими способами записанные номера окажутся различными?

№2.30. На бочонках лото написаны числа от 1 до 90. Берутся сразу два бочонка.

а) сколькими способами это можно сделать?

б) сколькими способами может оказаться, что на обоих бочонках числа меньшие 40?

в) сколькими способами может оказаться, что на одном бочонке число меньшее 40, а на другом большее 40?

№2.31. В 8 лунок бросается 8 шариков. Сколькими способами они смогут разместиться? А сколькими способами могут разместиться 4 шарика в одной лунке, три в другой, а один в третьей?

№2.32.. В КВН участвуют 8 юношей и 4 девушки. Сколькими способами они могут составить две команды по 6 человек, если в каждой команде должна быть хотя бы одна девушка?

№2.33. Студенту необходимо сдать 4 экзамена за 12 дней. Сколькими способами он сможет это сделать, если известно, что в день сдается не более одного экзамена и последний экзамен сдается в 12 –й день?

№2.34. Рота состоит из 4 офицеров, 8 сержантов и 80 рядовых. Сколькими способами можно укомплектовать отряд, состоящий из одного офицера, трех сержантов и шестнадцати рядовых?

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

№2.36. На танцевальном вечере присутствует 12 девушек и 15 юношей. Сколькими способами можно составить 4 пары для танца?

№2.37. В меню столовой имеются 3 первых блюда, 5 вторых и 4 третьих блюда. Сколькими способами можно составить обед из трех блюд разного вида? А из двух вторых и двух третьих блюд?

№2.38. В урне находятся m пронумерованных шаров. Из урны к раз достается один шар, записывается его номер и возвращается в урну. Сколькими способами могут разместиться записанные номера?

А сколькими способами может оказаться, что записанные номера различны?

2.2Ответы, указания, решения к разделу 2

№2.1. 1) 151200. 2) 9979200. .

3) Решение. Т.к. слова получаются в результате перестановок букв, при этом буква «к» встречается 2 раза, буква «у» 3 раза, а всего слово содержит п = 8 букв, то мы имеем перестановки с повторениями. По формуле (6)

получим P8	(3, 2) =	8!	= 3360.
	3! 2!

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

это будут размещения из 25 по 3. Тогда по формуле (1) получим А253 =	25!	= 23*24*25 = 13800 .
	25 3 !

№ 2.3 а) Т.к. требуется подсчитать число комбинаций, каждая из которых содержит 5 элементов, взятых из данных 25, то это либо размещения, либо сочетания. Т.к. перестановка делегатов внутри делегации не дает новую комбинацию, то это будут сочетания из 25 по 5. Тогда по формуле (5) получим

14

С	5		25!	= 21*22*23*5 = 53130 .
	25		5! 25 5 !

б). Т.к. в состав делегации требуется включить 3 юношей из 15, то это можно сделать С153 способами. Т.к. в состав делегации требуется включить 2 девушки из 10, то это можно сделать С102 способами. Каждый из способов делегирования юношей комбинируется с каждым способом делегирования девушек, то всего может быть

С153 * С102 = 20475 способов составить делегацию.
№ 2.4. а) А64 ,	б) 6, в) 1, г) С42 * С22 * А62 , д) 120.
№ 2.5. а) 0 , б)	в), г), д) см. -. № 2.4.	~ 8
е) это размещения с повторениями из 6 по 8. По формуле (2) получим			= 6	8	= 1679616
		А 6
№ 2.6. Это сочетания с повторениями из 4 по 3. по формуле (4) получим с~ 3 с 3						= 20
			4		6

№2.7. 375.

№2.8. 248832000. Указание. Считать, что всего букв (заглавных) 12. Каждая серия начинается с 000.

№2.9. 64.

№2.10. 1093. Указание. Для упрощения вычислений рекомендуется использовать формулу суммы геометрической прогрессии:

		an	q 1
sn				.
		q 1

№ 2.11. 2176782336.

№ 2.12. 252, 35, 56. Указание. См. № 2.3. № 2.13. 6.

№ 2.14. а)100, б) 90 , в) 25, г) 20, д) 45. № 2.15. 13800, а) 5, б) 60, в) 60.

2.16. 1212 .

№ 2.17. 1489950. см № 2.3. № 2.18. 3125. см. № 2.5.

№ 2.19. а) 20, б) 1. Указание. Чтобы куб числа оканчивался на 1, само число должно оканчиваться на 1.

№ 2.20. 5.

№ 2.21. Решение.

Первое трехзначное число, делящееся на 36 - это а1 =108. Разделив 999 на 36, мы получим в остатке 27. Значит последнее трехзначное число, делящееся на 36 - это ап = 972. Рассматриваем числа, делящиеся на 36 как арифметическую прогрессию с разностью d = 36, Получим ап = а1 + d(п-1). Отсюда п = (ап – а1) / d +1 = ( 972

–108) / 36 +1 = 25.

№2.22. 56, 20.

№2.23. 6. Указание. Из любых ли отрезков можно составить треугольник?

№2.24. 10, 50, 110.

№2.25. а) 220.,

б). Решение. Выбрать хотя бы два билета означает выбрать два билета или выбрать три билета. I. Выбрать два билета.

1). Выбрать два билета стоимостью по одному рублю (таких билетов 5, а других 7) можно С52 * С71 = 70 способами.

2). Выбрать два билета стоимостью по три рубля (таких билетов 3, а других 9) можно С 32 * С91 = 27 способами..

3). Выбрать два билета стоимостью по пять рублей (таких билетов 4, а других 8) можно С42 * С81 = 48 способами.

Выбрать два билета одинаковой стоимости можно 70+27+48=145 способами.

11. Выбрать три билета одинаковой стоимости можно С53 + С33 + С43 = 15 способами.

Таким образом, выбрать хотя бы два лотерейных билета одинаковой стоимости можно 145 + 15 = 160 способами.

№2.26. 1024, 120.

№2.27. Решение. Т.к. в преферансе участвуют в игре всего 32 карты, а 10 карт у игрока, то в прикупе может оказаться любая карта из 22. Число комбинаций прикупа С222 = 231.

Комбинаций бубновой масти 3.

№2.28. 153, 1430, 34320.

№2.29. 155, А155 .

№2.30. 4005, 741, 1950.

№2.31. 88, С84 * С43 * 1 * А83 .

№2.32 С41 * С85 + С42 * С84 + С43 * С83.

№2.33. А124.

№2.34. С41 * С83 * С8016.