ТВ Практические занятия (математики)(1-12)(16.11.14)

10 Занятие 1. Пространство элементарных исходов

2. Из колоды карт (36 штук) извлекаются две карты. Пусть событие А, состоит в том, что извлечен по крайней мере один туз, В — обе карты одной масти, С — карты разного цвета. Описать пространство элементарных исходов

и события А, В, С, если а) выбор производится без возвращения и без учета порядка;

б) выбор производится без возвращения с учетом порядка; в) выбор производится с возвращением без учета порядка; г) выбор производится с возвращением с учетом порядка.

3. Пусть 1, 2, 3, 4 — произвольные события. Выразить через 1, 2,

3, 4 следующие события:

а) произошло первое событие, и только оно; б) произошло не более двух событий; в) хотя бы одно событие не произошло;

г) произошло только одно из первых двух или только хотя бы одно из двух последних.

4. Из колоды карт (36 штук) извлекается одновременно 3 карты. Пусть события — все извлеченные карты красного цвета, — среди извлеченных карт два и только два туза, — среди извлеченных карт два и только два туза.

Описать словесно события: , , , , , .

5.Исследуется на стандартность партия изделий в количестве 5 штук. Указать события противоположные данным:

а) ровно 4 изделия стандартны; б) хотя два изделия стандартны;

в) более половины изделий стандартны г) нет ни одного стандартного.

6.Доказать, что если событие влечет за собой событие , то

7*. Доказать

а)

; б) = ; в) = .

б)

равенство

) (

);

( ) = (

а) = ( ) = ( ) ;

в) (

)

(

)

)

;

)

);

г) (

= ( ) (

= (

д) = ( ) ( ( )).

Занятие

2

Применение формул

комбинаторики при решении

задач

2.1Основные факты и определения

Определение 2.1. Комбинаторика — это раздел математики, изучающий расположение объектов в соответствии со специальными правилами и методы подсчета числа всех возможных способов, которыми эти расположения могут быть сделаны.

Теорема 2.1. Основной принцип комбинаторики. Пусть требуется осуществить одна за другой m операций. Если первую операцию можно осуществить 1 способами, вторую 2 способами, и так до m-й операции, которую можно осуществить способами, то все m операции вместе могут быть выполнены 1 · 2 · . . . · способами.

Определение 2.2. Произвольное –элементное подмножество множества из –элементов называется сочетанием из –элементов по .

Теорема 2.2. Обозначим количество k-элементных подмножеств мно-

жества из n элементов через , тогда справедлива формула =		!	.
		!( − )!

Определение 2.3. Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое натуральное число (номер элемента) от 1 до , где — число элементов множества, так, что различным элементам соответствуют различные номера.

11

12 Занятие 2. Применение формул комбинаторики при решении задач

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

Теорема 2.3. Обозначим через — количество перестановок – элементного множества. Тогда справедлива формула = 1 · 2 · . . . · = !.

Определение 2.5. Упорядоченные –элементные подмножества множества из элементов называется размещениями из элементов по .

Теорема 2.4. Обозначим — число упорядоченных –элементных подмножеств множества, состоящего из элементов. Тогда = ( −! )!.

Определение 2.6. Кортежи длины , которые можно получить из 1 букв

1, 2 букв 2,. . . , букв , называются перестановками с повторениями.

Теорема 2.5. Обозначим количество перестановок с повторением

( 1, . . . ). Тогда ( 1, 2, . . . , ) = ! .

1!··· !

Следствие 2.1. Пусть 1, 2, . . . , — целые неотрицательные чис-

ла, причем 1 + . . . +	= . Количество способов,			которыми		мож-
но осуществить разбиение множества, содержащего элементов						на
подмножеств, количества	элементов в	которых соответственно				равны
1, 2, . . . , определяется формулой ( 1		, 2, . . . , ) =		!	.
			1	!··· !

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

Теорема 2.6. Обозначим через ̃ число всех различных размещений с повторениями из элементов по равно ̃ = .

Определение 2.8. Сочетаниями с повторениями из элементов по элементов называют группы, содержащие элементов, причём каждый элемент принадлежит одному из типов.

Теорема 2.7. Число сочетаний с повторениями из элементов по

равно		= −1	=
	̃	+ −1	+ −1

2.2. Примеры решения задач

13

Теорема 2.8 (Формула включения исключения). Пусть даны множества

1, 2, . . . , . Тогда количество элементов в объединении этих множеств можно найти по формуле:

| 1 2 . . . | = | 1| + | 2| + . . . + | | − | 1 ∩ 2| − | 2 ∩ 3| − . . . −

− | −1 ∩ | + | 1 ∩ 2 ∩ 3| + . . . + | −2 ∩ −1 ∩ | +

+(−1) −1 | 1 ∩ 2 ∩ . . . ∩ | .

2.2Примеры решения задач

При решении комбинаторных задач необходимо правильно выбрать тип тип

комбинаторного соединения. Для этого будет полезна следующая диаграмма,

изображенная на рис. 2.1

Повторяются элементы в соединении

НЕТ!

Соединения без повторений

ДА!

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

Меняется ли

Меняется ли

состав?

состав?

НЕТ!

ДА!

НЕТ!

ДА!

Порядок

Перестановки с

Порядок

Перестановки

важен?

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

важен?

НЕТ!

ДА!

НЕТ!

ДА!

Сочетания с

Размещения с

Сочетания

Размещения

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

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

Рис. 2.1 – Выбор комбинаторного соединения

14 Занятие 2. Применение формул комбинаторики при решении задач

Пример 2.1. Сколькими способами три различные награды могут быть распределены между 10 участниками соревнования?

Решение. В задаче необходимо необходимо определить количество способов которыми можно выбрать 10 элементов три с учетом порядка, т.е. количество размещений из 10 элементов по 3:

	103 =		10!	=	8 · 9 · 10	= 120.
		3!7!			2 · 3

Пример 2.2. Из колоды, содержащей 52 карты, вынули 4 карты. В скольких случаях окажется, что среди вынутых карт

а) ровно один туз; б) хотя бы один туз.

Решение. а) Туза можно выбрать четырьмя способами. Не туза можно выбрать 483 способами. Тогда согласно правилу умножения искомое количество способов равно

4	·	3	=	4 · 48!	=	4 · 46 · 47 · 48			=	69184
		48		3!45!		2	·	3

б) Искомое количество способов равно разности общего количества способов и количества способов при которых не будет ни одного туза.

Общее количество способов: 524 . Количество способов при которых не будет ни одного туза: 484 .

Окончательно 524 − 484 = 76145

Пример 2.3. Имеется 4 различных флага. На флагштоке поднимается сигнал, состоящие не менее чем из двух флагов. Сколько различных сигналов можно поднять на флагштоке (порядок флагов учитывается)?

Решение. Количество сигналов, которые можно подать используя ровно два флага, можно найти как количество размещений из 4 по 2 (расположение флагов существенно): 42. Аналогично для трех — 43. Для четырех флагов — это будет количество перестановок из 4 элементов: 4!.

Согласно правилу сложения получим

42 + 43 + 4! = 2!2!4! + 3!1!4! + 4! = 6 + 4 + 24 = 34.

9 (3, 3, 3) =

2.2. Примеры решения задач

15

Пример 2.4. На книжной полке расставляют 6 различных книг, среди которых есть двухтомник А.С. Пушкина Сколькими способами их можно расставить на полке, чтобы книги двухтомника стояли рядом, не обязательно по порядку?

Решение. Будем рассматривать двухтомник как одну книгу, причем их рядом можно поставить двумя способами. Теперь мы имеем пять книг, которые можно расставить 5! способами. Таким образом, мы имеем 2 · 5! = 240

Пример 2.5. Человек имеет 6 друзей и в течении 4 дней приглашает к себе 3 из них так, что компания ни разу не повторяется. Сколькими способами может он это сделать?

Решение. Из семи друзей троих можно выбрать 63 = 20 способами. Далее, на каждый день необходимо выбрать приглашенных одним из этих 20 способов (с учетом порядка): 420 = 116280.

Пример 2.6. Сколькими способами можно выстроить 9 человек разного роста в колонну по 3 человека, если в каждой шеренге люди выстраиваются по росту?

Решение. Необходимо 9 человек разбить на три группы по три человека. В каждой группе людей по росту можно расставить единственным способом. Следовательно, искомое количество способов согласно следствию 2.1 равно

3!3!3!9! = 1680.

Пример 2.7. Сколькими способами можно переставить буквы в слове «пурпур» так, чтобы одинаковые буквы не шли друг за другом?

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

Общее количество способов найдем используя формулу для числа перестановок с повторениями. Всего букв в слове — 6, букв «п» —2, «у» —2, «р» — 2, следовательно имеем

6!

6 (2, 2, 2) = 2!2!2! = 90.

16 Занятие 2. Применение формул комбинаторики при решении задач

Количество способов при которых хотя бы две одинаковые буква стоят ря-

дом найдем используя формулу включения-исключения. Для этого обозначим

1 — количество способов если буквы «п» стоят рядом, 2 — количество способов если буквы «у» стоят рядом, 1 — количество способов если буквы «р» стоят рядом. Используя метод примера 4 этого занятия, объединим вместе буквы «п», тогда | 1| = 5 (1, 2, 2) = 30. Аналогично можно получить, что | 2| =

| 3| = 30. Объединяя по две пары одинаковых цифр вычислим количество эле-

ментов в пересечениях | 1		2| = | 1	3|	= | 2	3|	= 4 (1, 1, 2) = 12.
А пересечение всех трех	множеств вычислим, применяя формулу для количе-

ства перестановок, предварительно объединив попарно все одинаковые буквы

| 1	2			3| = 3! = 6 Используя формулу включения-исключения, получим
1		2		3		= | 1| + | 1| + | 1| −	1	2		−	1	3		−	2	3		+

+	1	2	3		= 30 + 30 + 30 − 12 − 12 − 12 + 6 = 60

Окончательно имеем искомое количество способов перестановки букв

90 − 60 = 30.

Пример 2.8. В почтовом отделении продаются открытки восьми видов в неограниченном количестве. Сколькими способами можно купить 7 открыток

а) всего; так чтобы

б) все открытки были одинаковыми; в) все открытки были разными;

г) среди открыток присутствовало ровно три вида?

Решение. а) Используем формулу для количества сочетаний с повторениями. Имеем 8 типов элементов из них выбирается 6 элементов. Получаем количество способов равное

̃86 = 137 = 7!6!13! = 1716.

б) Так как все открытки должны принадлежать одному типу, то ответ 8.

2.3. Задания для аудиторной работы

17

в) В данном случае типы не должны повторяться, следовательно мы имеем дело с сочетаниями из 8 по 6 без повторений

87 = 6!2!8! = 28.

г) Выберем три типа открыток 83 = 3!5!8! = 56. Далее, так как каждый из этих типов должен встречаться хотя бы один раз, то выберем по одной открытке из

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

для количества сочетаний с повторениями ̃33 = 53 = 3!2!5! = 10. Окончательно используя правило умножения, получим 56 · 10 = 560.

Пример 2.9. Сколько различных решений имеет уравнение:

0 + 1 + . . . + 9 = 23?

а)в целых неотрицательных числах; б) в положительных чисел.

Решение. Будем каждую переменную считать типом элементов, т.е. если

3 = 3, 8 = 20, будем считать что в соединение входят три элемента третьего типа и двадцать элементов восьмого типа. Так как порядок элементов не важен (не важно в каком порядке мы будем раскладывать единички по неизвестным), то мы имеем дело с сочетания с повторениями.

а) Искомое количество равно ̃239 = 319 .

б) В этом случае мы выделим по одной единичке в каждую неизвестную, после чего останется распределить 14. Следовательно интересуемое нас число решений равно ̃149 = 229 .

2.3Задания для аудиторной работы

1.Сколькими различными способами можно рассадить 11 человек за круглым столом?

2.За стол рассаживаются 5 девушек и 6 юношей. Сколькими способами это можно сделать так, что бы ни какие две девушки не сидели рядом? Рассмотреть случаи прямого стола и круглого.

18Занятие 2. Применение формул комбинаторики при решении задач

3.Для участия в чемпионате 2n команд делят на две группы по команд каждая. Сколькими способами можно выполнить деление, что бы

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

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

каждую?

4.В чемпионате играют n команд, каждая команда играет с другой по одной игре. Сколько игр будет сыграно?

5.По ячейкам размещают одинаковых частиц. Каким количеством способов это можно сделать:

а) всего; так, чтобы

б) каждая ячейка была занята ( > ); в) в каждой ячейке было не больше одной частицы( < ); г) заняты были две и только две ячейки; д) занято было не больше двух ячеек

е) хотя бы одна ячейка осталась свободной; 6. По каналам связи передаются различных телеграмм. Сколь суще-

ствует способов отправки телеграмм а) всего; так, чтобы

б) по каждому каналу прошла хотя бы одна телеграмма ( > ); в) по каждому каналу прошло не более одной телеграммы ( < ); г) было занято не более трех каналов.

7. Код некоторого замка состоит из 6 цифр (порядок цифр важен). Сколько существует разных кодов, таких что:

а) содержит все цифры одинаковые; б) содержит все цифры различные;

в) содержит одну и только одну пару одинаковых цифр; г) содержит три различные пары одинаковых цифр; д) содержит одну и только одну тройку одинаковых цифр; е) содержит две различные тройки одинаковых цифр; ж) ни какие две одинаковых цифры не стоят рядом?

2.4. Задания для самостоятельной работы

19

8.Есть три вагона и 10 человек. Сколькими способами их можно рассадить по вагонам?

9.В гости пришли 10 человек в калошах. Когда они шли домой, каждый взял себе по 2 калоши. Сколькими способами это можно сделать? А если каждый взял себе одну правую и одну левую?

10.Сколькими способами можно разложить 8 белых, 5 зеленых и 11 черных шаров можно разложить в 4 коробки?

11.Имеется 10 белых, 12 зеленых и 9 синих шаров. Сколькими способами их можно разложить по трем урнам, так, что бы в каждой урне было не менее трех шаров каждого цвета.

13.Сколькими способами можно из 28 костей домино можно выбрать две так, что бы их можно было приставить одинаковыми половинами.

14.Каким количеством способов можно за дней сдать экзаменов? Рассмотреть случаи:

а) количество экзаменов, которые можно сдать за один день неограниченно; б) в один день можно сдать только один экзамен ( ≥ ); в) за один день разрешено сдавать только один экзамен, а на подготовку

необходим хотя бы один день ( ≥ − 1).

2.4Задания для самостоятельной работы

1.Сколько различных ожерелий можно составить из 11 различных жемчу-

жин?

2.Каким количеством способов можно упорядочить числа 1, 2, 3, 4, 5 . . . , = 2 − 1 так, чтобы четные числа занимали места с

а) четными номерами; б) нечетными номерами?

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

4.Каким количество способов можно расселить 10 студентов по четырем комнатам: двум двухместным, трехместной и четырехместной?