Рабочая тетрадь 1 страница

Пособие для студентов по специальностям 010100 и 510100

ВОРОНЕЖ

Утверждено научно-методическим советом математического

факультета (2 сентября 2003г., протокол №2)

Составители: Михайлова И. В.

Баркова Л. Н.

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

Рекомендуется для студентов 3 курса дневного и 5 курса вечернего отделений.

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

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

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

(правила) сложения и умножения.

Принцип суммы. Пусть множество А содержит п элементов, а множество B - k элементов, причем . Тогда множество содержит п + k элементов.

Замечание 1. Если обозначить - число элементов множества А, то в формализованном виде правило суммы можно сформулировать следующим образом: если то .

Замечание 2. При решении задач удобной бывает следующая формулировка: элемент из А или элемент из В можно выбрать п+ k числом способов, где п - количество способов выбрать элемент из А, k – элемент из В.

Принцип произведения. Пусть заданы два множества и . Тогда декартово произведение

содержит элементов, т.е. , если

Подводя итог сказанному, подчеркнем, что если выбирается или то или другое, то нужно применять правило суммы, а если и то, и другое, то правило произведения. Например, на тарелке лежат 5 яблок и 3 груши. Если выбираем яблоко или грушу, то число способов 5+3=8. Если выбираем и яблоко, и грушу, то 5 • 3 == 15.

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

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

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

Решение. Для размещения семи человек в автомашине необходимо выполнить семь действий (заполнить семь мест), то есть = 7. На одно из этих действий (заполнение места водителя) наложены ограничения. Поэтому это действие будем считать первым и тогда = 3, после чего заполнение любого из оставшихся можно осуществить = 6 способами и т.д. Заполнение последнего места можно выполнить только одним способом, то есть = 1. Согласно принципу умножения, все семь действий можно выполнить 3 способами.

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

Рассмотрим сначала следующую задачу. Из трех букв нужно выбрать какие-то две. Сколько способов выбора? Оказывается здесь спрятаны четыре задачи.

Считать ли ab и одинаковыми вариантами? Если порядок выбора существенен, то варианты выбора будем называть размещениями. Если порядок выбора безразличен, то варианты выбора будем называть сочетаниями.

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

Итак, пусть - множество произвольной природы, содержащее п элементов, n .

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

и при

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

.

Перестановками из п элементов множества В назовем размещения из п элементов множества по n элементов. Число перестановок из п различных элементов .

Сочетаниями из n элементов множества по элементов называются подмножества множества В, содержащие различных элементов множества В. Число сочетаний из n по

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

,

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

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

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

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

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

Если же осуществляется выбор с возвращением, то число вариантов равно . Это - .

В другом случае, если порядок букв не существенен и буквы не повторяются, то, используя формулу сочетаний без повторений, имеем

. Здесь варианты .

И, наконец, число сочетаний с повторениями а варианты: .

Задачи для самостоятельного решения

1. На окружности выбрано десять точек. Сколько существует хорд с концами в этих точках? Сколько ненулевых векторов с концами в этих точках? Сколько векторов с концами в этих точках? Сколько треугольников с вершинами в этих точках? Сколько выпуклых пятиугольников, выпуклых десятиугольников?

2. Даны три карточки с цифрами 1,2,3. Сколько чисел можно составить из этих трех карточек?

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

4. Сколькими способами девушек могут образовать хоровод?

5. Сколькими способами различных шаров можно разместить по различным ячейкам, предполагая, что а) в ячейке может быть более одного шара; в) не может быть более одного шара.

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

7. В розыгрыше лотереи участвуют 3 человека. Каждому из них присвоен порядковый номер. Участники лотереи должны вытащить одну карточку из трех с номерами 1,2,3. Призы выдаются тем, кто вытащит карточку со своим порядковым номером. Каково число вариантов, в которых выигрыш только у одного участника лотереи? В которых ни один не выигрывает? Ответить на вопросы для произвольного

8. Сколько пятибуквенных слов (перестановок), каждое из которых состоит из трех согласных и двух гласных, можно образовать из букв слова УРАВНЕНИЕ.

§ 2. Математическая модель случайного опыта.

Пусть G - некоторый случайный опыт, обладающий свойством устойчивости частот, т.е.

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

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

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

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

Математическая модель такого случайного опыта G называется вероятностным пространством и обозначается Сокращенно ~ , где

- множество исходов опыта G;

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

- вероятность случайных событий (вероятностная мера на измеримом пространстве ). Связь вероятностной и теоретико-множественной терминологии отражена в таблице 1.

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

Пример. Случайный опыт G - выбор наудачу одной кости из полного набора костей домино. Возможные математические модели данного опыта:

Модель 1.

.

- совокупность всех подмножеств .

, (о вероятности см. ниже).

Модель 2.

где означает, что выбран дубль, а - не дубль.

, где - невозможное событие; - достоверное событие.

Рассмотрим несколько возможных результатов опыта G:

1) А- выбран дубль.

2) В - сумма очков на выбранной кости равна 6.

В первой модели А = {(0.0), (1,1), (2,2), (3,3). (4.4), (5,5), (6,6)};

В ={(0,6), (1.5), (2.4), (3,3)}.

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

Вернемся к наиболее содержательной первой модели. Так как события в модели являются подмножествами, то к ним можно применять все теоретико-множественные операции. Например,

В \ А = {(0,6). (1,5), (2,4)}, , {(0,0), (1,1), (2,2), (3,3), (4.4), (5,5), (6,6), (0,6), (1.5), (2,4)}, \ A - не дубль.

Задачи для самостоятельного решения

1. Мишень состоит из десяти кругов, ограниченных концентрическими окружностями с радиусами . Событие - попадание в круг радиуса при одном выстреле по мишени. Описать множество исходов данного опыта. Что означают события , , ,

.

2. Электрическая цепь состоит из элементов. Пусть событие А означает, что цепь безотказно работает в течение контрольного промежутка времени, а события - то же для -ого элемента;

А. Выразить событие А и через события для цепей с параллельным и последовательным соединением элементов.

В. Выразить через указанные ниже события: В - отказали все элементы, С - отказал хотя бы один элемент, D - безотказно работал один и только один из элементов, Е - отказали только два элемента..

3. Случайный опыт – испытание трех приборов. События: А - хотя бы один из трех проверяемых приборов бракованный; В - все приборы доброкачественные. Что означают события a) ; b) c) d) .

4. Опыт состоит в однократном бросании игральной кости. Описать возможные для данного опыта множества исходов. В каждой из предложенных моделей указать события: А - число очков, выпавших на верхней грани игральной кости, кратно трем; В - на верхней грани выпало нечетное число очков: С - число очков больше трех; D - число очков меньше семи; Е - число очков 0,5; F - число очков от 0,5 до 1,5. Установить пары совместных событий. Описать события

5. Пусть А и В - произвольные события, наблюдаемые в опыте G.

Проверить следующие равенства

a) ;

b)

6. Пусть число исходов равно Указать минимальное и максимальное возможные значения для числа всех случайных событий.

7. Может ли быть: a) число исходов конечно, а число всех случайных событий бесконечно; b) число всех случайных событий конечно, а число исходов бесконечно; c) число исходов больше, чем число всех событий.

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

2.2. Классическая схема (модель). Рассмотрим опыт G, число возможных исходов которого конечно и все исходы равновозможны, т.е. непредпочтительны друг перед другом или имеют одинаковые шансы к появлению. Тогда

,

Обратимся к примеру п.2.1. В первой модели вероятность того, что выбранная наудачу кость окажется дублем

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

В этой же модели

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

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

Максвела-Больцмана - все размещений различных частиц по различным ячейкам равновероятны.

Бозе-Энштейна - все способов заполнения различных ячеек неразличимыми частицами равновероятны (в статистической механике показано, что это предположение справедливо для фотонов, атомных ядер и атомов, содержащих четное число элементарных частиц)

Ферми-Дирака - все способов распределения равновероятны (эта модель применима к электронам, нейтронам и протонам).

Задачи для самостоятельного решения

1. Куб, все грани которого окрашены, распилен на тысячу кубиков одинакового размера. Полученные кубики тщательно перемешаны. Определить вероятность того, что наудачу извлеченный кубик будет иметь: а) три окрашенные грани; b) только две окрашенные грани; с) только одну окрашенную грань; d) не имеет окрашенных граней.

2. Ребенок играет с 10 буквами разрезной азбуки А,А,А,Е,И,К,М,М,Т,Т. Какова вероятность того, что при случайном расположении букв в ряд он получит слово МАТЕМАТИКА?

Для решения задачи рекомендуем построить две модели: в одной все десять карточек считать различными, в другой - карточки с одинаковыми буквами неразличимы. Получив, естественно, одно и то же значение вероятности, объясните это.

3. У человека N ключей, из которых только один подходит к его двери. Он последовательно испытывает их, выбирая случайным образом (без возвращения), найти вероятность того, что этот процесс закончится на k -ом испытании.

4. Абонент забыл две последние цифры номера телефона и потому набрал их наудачу, помня лишь то, что а) эти цифры различны; в) эти цифры нечетные. Найти вероятность того, что номер набран правильно.

5. В шахматном турнире участвуют 20 человек, которые по жребию распределяются на две группы по 10 человек. Найти вероятность того, что а) двое наиболее сильных игроков будут играть в разных группах; в) четверо наиболее сильных игроков попадут по два в разные группы.

6. Из урны, содержащей шары с номерами 1,2,.....9, пять раз наугад вынимают шар и каждый раз возвращают обратно. Найти вероятность того, что из номеров вынутых шаров можно составить возрастающую последовательность.

7. Десять студентов договорились о поездке за город, но не договорились о вагоне. Поэтому каждый из них выбирает для себя вагон случайным образом. Найти вероятность того, что а) все попадут в разные вагоны; в) все попадут в первый вагон; с) все попадут в один вагон, считая число вагонов .

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