Пособие по терверу

1 Элементы комбинаторики

1.1 Правило произведения

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

Два основных принципа комбинаторики правило суммы и правило произведения.

Правило суммы. Если некоторый объект A можно выбрать m способами, а другой объект B можно выбрать n способами, то выбор \либо A, либо B” можно осуществить m + n способами.

Пример. В первой вазе лежит 6 яблок, во второй 5 груш, в третьей 4 персика. Сколькими способами можно выбрать один из фруктов?

B По правилу суммы, число способов: 6 + 5 + 4 = 15: C

Правило произведения. Если объект A можно выбрать m способами и если после каждого такого выбора объект B можно выбрать n способами, то выбор пары (A; B) в указанном порядке можно осуществить m n способами.

Пример. У одного студента 5 книг, у другого 9. Все книги различные. Сколькими способами студенты могут произвести обмен одной книги на книгу?

B Любую из 5 книг первого студента можно обменять на любую из 9 книг второго студента. Общее число способов обмена: 5 9 = 45. C

Пример. Имеется набор чисел: f1; 2; 3; 4g. Сколькими способами можно расположить числа из этого набора так, что крайние числа имеют одинаковую четность?

B Если крайние числа четные, то имеется два варианта для их расположения (первое число 2, или первое число 4), при этом оставшиеся

11

нечетные числа можно также расположить двумя способами (первым идет 1 или первым идет 3). Всего здесь вариантов, по правилу произведения, 2 2 = 4. Аналогично имеется 4 варианта в том случае, если крайними стоят нечетные числа. Общее число вариантов находится по правилу суммы: 4 + 4 = 8. C

1.2 Основные формулы

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

Пример. Множество состоит из двух элементов, чисел 1 и 2. Тогда имеется один неупорядоченный набор этих элементов: (1; 2) и два упорядоченных набора: (1; 2) и (2; 1).

На упорядоченных множествах рассматривают перестановки и размещения.

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

Пример. Перестановками трех чисел 1; 2 и 3 являются шесть комбинаций: (1; 2; 3); (1; 3; 2); (2; 1; 3); (2; 3; 1); (3; 1; 2); (3; 2; 1).

Число перестановок из n элементов вычисляется по формуле

Pn = n! = 1 2 3 (n 1) n:

Пример. В аудитории 10 мест. Сколькими способами можно разместить в ней 10 студентов?

B Искомое количество дает число перестановок из 10 элементов:

P10 = 10! = 3 628 800. C

Пусть m 6 n.

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

12

Пример. Размещением из 3 элементов по 2, взятых из набора f1; 2; 3g, являются шесть комбинаций: (1; 2); (2; 1); (1; 3); (3; 1); (2; 3); (3; 2).

Число размещений из n элементов по m вычисляется по формуле

Amn = n (n 1) (n 2) (n m + 1):

Пример. Студенту необходимо сдать 4 экзамена в течение 7 дней. Сколькими способами можно составить расписание экзаменов, если учитывать, что в один день он может сдавать только один экзамен?

B Четыре экзамена нужно разместить среди имеющихся семи дней, причем важно, в каком порядке идут экзамены. Количество способов дает число размещений из 7 элементов по 4: A47 = 7 6 5 4 = 840. C

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

Пример. Сочетанием из 3 элементов по 2, взятых из набора f1; 2; 3g, являются три комбинации: (1; 2); (1; 3); (2; 3).

Число сочетаний из n элементов по m вычисляется по формуле

Cnm =	n!
		:
	m!(n m)!

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

B Нужно всевозможными способами выбирать пары участников из имеющихся 10 человек, причем, в выбранной паре не важен порядок участников, важен только состав. Искомое количество дает число сочетаний из 10 по 2:

C2	=	10!	=		9 10	= 45:	C
10	8!2!			2

Числа Cnm называют биномиальными коэффициентами. С их помощью записывается формула бинома Ньютона:

n

X

(a + b)n = Cnkakbn k:

k=0

13

Pn(n1; n2; : : : ; nk) =

Пример. (a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4:

Пусть даны элементы, относящиеся к k различным типам. Перестановками с повторениями называются всевозможные комбинации, состоящие из n1 элементов первого типа, n2 элементов второго типа, . . . , nk элементов k-го типа, и при этом n1 + n2 + : : : + nk = n.

Число перестановок с повторениями вычисляется по формуле

n! n1!n2! nk!:

Пример. Сколько различных пятизначных чисел можно записать, используя две цифры \1” и три цифры \2”?

B Требуемые числа получаются в результате перестановок n = 5

цифр, принадлежащих двум типам. Число элементов первого типа (цифра \1”) n1 = 2, число элементов второго типа (цифра \2”) n2 = 3: Искомое количество чисел: P5(2; 3) = 5!=(2!3!) = 10: C

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

Размещением с повторениями из k типов элементов по m называется упорядоченный набор, состоящий из m элементов, причем в одном наборе могут повторяться одинаковые элементы.

Число размещений с повторениями из k типов элементов по m

вычисляется по формуле

Amk = km:

Пример. Требуется найти количество трехзначных чисел, которые можно составить из цифр 1; 2; 5; 8; 9 при условии, что отдельные цифры мо-

гут повторяться.

B Здесь k = 5; m = 3; A35 = 53 = 125: C

Сочетанием с повторениями из k типов элементов по m называется неупорядоченный набор, состоящий из m элементов, причем в одном наборе могут повторяться элементы одного типа.

Число сочетаний с повторениями из k типов элементов по m вычисляется по формуле

	km = Ck 1
C		:
	m+km 1

14

Пример. В фондовом магазине предлагаются акции семи компаний.

Каким количеством способов можно купить десять акций?

B Здесь k = 7; m = 10; C107 = C10+77 1 1 = C166 = 8008: C

1.3 Задания

Задачи для практических занятий

1.1.Имеется три дороги, ведущие из города A в город B, и две дороги, ведущие из города B в город C. Сколько имеется различных путей из города A в город C, проходящих через город B?

1.2.Сколькими способами можно выбрать два числа из набора чисел

f1; 2; 3; : : : ; 10g так, чтобы одно число было меньше 6, а другое боль-

ше 6?

1.3.Сколько диагоналей имеет выпуклый десятиугольник?

1.4.Сколько существует шестизначных чисел, у которых первая и последняя цифра совпадают?

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

1.6.В комнате имеется 5 стульев. Сколькими способами можно разместить на них 5 гостей?

1.7.В соревновании участвуют 20 человек. По результатам определяются занявшие первое, второе и третье места. Сколько существует различных исходов соревнований?

1.8.Из 10 деталей 2 бракованных. Сколькими способами можно выбрать 3 детали из этих 10 так, чтобы среди них была только одна бракованная деталь?

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

1.10.Сколькими способами в группе из 25 студентов можно выбрать трех человек: старосту группы, заместителя старосты и помощника старосты?

1.11.В автобусе 5 пассажиров. Каждый из них должен выйти на какой-то из оставшихся десяти остановок. Сколько имеется различных вариантов выхода?

15

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

1.13.Сколькими способами можно выбрать два числа из набора чисел

f1; 2; 3; : : : ; 10g так, чтобы хотя бы одно число было меньше 6?

1.14.Имеются марки четырех цветов: желтые, зеленые, красные и синие. На почте имеется папка, содержащая достаточно много марок любого из этих цветов. Сколькими способами можно выбрать из этой папки набор, содержащий девять марок?

1.15.В оркестре из семи человек должны быть трубачи, ударники и саксофонисты (хотя бы по одному). Сколько различных составов такого оркестра может быть? (Оркестры считаются различными по составу, если у них различное количество музыкантов какого-либо вида).

Ответы

1.1.6. 1.2. 20. 1.3. 35. 1.4. 90 000. 1.5. 5040. 1.6. 120. 1.7. 6840. 1.8. 56.

1.9.2300. 1.10. 13 800. 1.11. 100 000. 1.12. 369. 1.13. 35. 1.14. 220.

1.15. 15.

Домашнее задание

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

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

1.18.Сколькими способами можно выбрать 4 карты из колоды в 36

карт?

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

1.20.В футбольном турнире участвуют 5 команд. По условию соревнований каждая пара команд должны провести между собой 2 игры. Сколько всего игр будет проведено?

16

1.21.В вазе стоят 5 красных и 4 желтых розы. Сколькими способами можно выбрать из нее 3 розы одного цвета?

1.22.В взводе 3 сержанта и 30 солдат. Сколькими способами можно выделить сержанта и 3 солдата для патрулирования?

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

1.24.Правитель некоторого государства учредил четыре военных ордена. Сколькими способами он может наградить шестью орденами своего военного министра?

1.25.В цветочном киоске 10 видов цветов. Сколькими способами можно составить букет, содержащий 3 цветка (не обязательно различных)?

Ответы

1.16.180 000. 1.17. 720. 1.18. 58905. 1.19. 303600. 1.20. 20. 1.21. 14.

1.22.12 180. 1.23. 1296. 1.24. 84. 1.25. 220.

Дополнительные задачи

1.26.На железнодорожной станции имеется 5 запасных путей. Сколькими способами можно расставить на них 3 поезда?

1.27.На сколько нулей оканчиваются числа: а) 30!; б) 200!?

1.28.В учреждении 20 отделов. Любые два отдела соединены телефонной линией. Сколько всего телефонных линий?

1.29.Сколькими способами можно расставить на полке 7 различных книг, если две определенные книги должны стоять рядом?

1.30.Сколько четырехзначных чисел содержат цифру 3?

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

1.32.Сколькими способами можно расставить последовательные 10 чисел так, чтобы четные числа имели четные номера?

1.33.На фондовой бирже продаются акции 5 предприятий. Сколькими способами можно приобрести 20 акций?

17

1.34.В доме, имеющем 4 стены, решено сделать 4 окна. Сколько имеется различных вариантов распределения окон по стенам? (Стены между собой не различаются, также и окна не различаются между собой).

1.35.Сколько существует на плоскости путей из точки (0; 0) в точку (3; 5)? (Каждый шаг состоит в переходе на одну единицу вправо или на одну единицу вверх.)

Ответы

1.26.60.1.27. а) 7; б) 49. 1.28. 190. 1.29. 1440. 1.30. 3168. 1.31. 34 650.

1.32.14 400. 1.33. 10 626. 1.34. 35. 1.35. 56.

18

2 Вероятность события

2.1 Случайные события

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

Пример. Если брошена игральная кость, то событие {выпало число очков, равное 2} является элементарным; сложным событием является, к примеру, событие {выпало четное число очков}.

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

Пример. При бросании игральной кости множеством элементарных событий является набор шести элементов f1; 2; 3; 4; 5; 6g; сложное событие {выпало четное число очков} является подмножеством, состоящим из трех элементов f2; 4; 6g.

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

Пример. Если брошена игральная кость, то событие {появление любого числа очков от 1 до 6} является достоверным событием.

Событие называется невозможным, если оно заведомо не произойдет ни при одном осуществлении данной совокупности условий. Невозможное событие описывается пустым множеством ?.

19

Пример. Если брошена игральная кость, то событие {выпало число очков, равное 7} является невозможным событием.

Объединением (или суммой) событий A+B является событие, которое происходит всякий раз, когда происходит хотя бы одно из событий A

или B.

Пересечением (произведением) событий AB называется событие, которое происходит только тогда, когда происходят оба события A и B.

Событие A называется противоположным событию A, если оно состоит в непоявлении события A.

Пример. Если брошена игральная кость и рассматриваются события:

A = {выпало четное число очков}; B = {выпало число очков, больше 4}, то A+B = {выпало число очков, одно из \2”, \4”, \5”, \6”}; AB ={выпало число очков, равное \6”}; A = {выпало нечетное число очков}.

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

Несколько событий A1; A2; : : : ; An называются попарно несовместными, если появление любого из них исключает появление каждого из остальных.

Пример. Если брошена игральная кость, то несовместными являются события: A = {выпало четное число очков} и B = {выпало число очков, равное 5}.

Если при каждом испытании, при котором происходит событие A, происходит и событие B, то говорят, что A влечет за собой событие B (или

A входит в B). Обозначение: A B.

Пример. Брошена игральная кость. События: A = { выпала цифра 4};

B ={выпало четное число}. Тогда A B.

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

Примеры.

1.Появление \герба” или \цифры” при выбрасывании монеты.

2.Выпадение \1” или \6” при выбрасывании игральной кости.

20