Лабораторная работа 7 Элементы комбинаторики
Цель работы
Целью лабораторной работы является изучение базовых формул и теорем комбинаторики.
Краткие теоретические положения
Правила суммы и произведения
Правило
суммы.
Если объект А может быть выбран
способами, а объект В другими
способами, причем выборы объектов А и
В несовместны, то выбор «либо А либо В»
может быть осуществлен
способами.
Правило
произведения.
Если объект А может быть выбран
способами и после каждого из этих выборов
объект В может быть выбран
способами, то выбор упорядоченной пары
(А, В) может быть осуществлен
способами.
Пример 2.1. На книжной полке стоят 20 книг по алгебре, 12 по теории вероятностей, 7 по математическому анализу и 25 по литературе. Сколькими способами можно выбрать книгу по математике?
Решение. Найдем число способов, которыми можно выбрать книгу по алгебре, или по теории вероятностей, или по математическому анализу. Книгу по алгебре можно выбрать 20 способами, по теории вероятностей 12 способами и по математическому анализу 7 способами. Эти выборы несовместны.
Поэтому по правилу суммы находим, что выбрать книгу по математике можно N = 20+ 12 + 7 = 39 способами.
Пример 2.2.. Сколько трехзначных чисел можно составить из цифр 1, 3, 5, если цифры в числе не повторяются?
Решение.
На месте сотен поставим любую из трех
цифр. После каждого такого выбора на
месте десятков можно поставить любую
из двух оставшихся цифр, так как цифры
в числе не повторяются. Наконец, на месте
единиц можно поставить оставшуюся одну
цифру. Применением правила произведения
найдем число трехзначных чисел, равное
=6.
Упорядоченные
множества длины
,
составленные из элементов n
множества,
называют размещениями
без повторений
из n
элементов
по r.
Их
число выражается формулой
.
Такие размещения называют также упорядоченными выборками r элементов из данных n без возвращения.
Если
,
то говорят о перестановках без повторений
длиныn
(или
из
элементов).
Их
число выражается формулой
.
Сочетаниями из n по элементов без повторений называются r-подмножества n-множества X.
Их
число выражается формулой
.
Или
.
Пример 2.3. В комитет комсомола избрали 9 человек. Из них надо выбрать секретаря и его заместителя. Сколькими способами это можно сделать?
Решение. Из множества, содержащего 9 различных элементов, выбираются 2 элемента. Порядок существен. Элементы не могут повторяться.
Следовательно,
необходимо найти число размещений без
повторений из девяти элементов по два
элемента в каждом, то есть
.
Значит, секретаря и его заместителя
можно выбрать
способами.
Частным случаем размещения является перестановка.
Через
обозначается количество перестановок
в множестве
,
содержащемn
элементов.
Имеет место формула
.
Таким
образом, имеем
,
то есть количество размещений объектов
наn
местах совпадает с количеством
перестановок множества из n
элементов.
Пример 2.4. Сколькими способами можно выстроить 4-х человек в ряд для фотографии.
Решение.
Дано количество это число
перестановок множества из 4 элементов.
Пример 2.5. Сколько хорд можно провести через 6 точек, лежащих на одной окружности?
Решение. Из множества, содержащего 6 различных элементов, выбираются 2 элемента, так как хорда однозначно определяется двумя точками, лежащими на окружности. Порядок элементов роли не играет. Например, [АВ] и [ВА] одна и та же хорда.
Следовательно,
необходимо найти число сочетаний из
шести элементов по два, то есть
.
Значит, можно провести
различных хорд.
Важное
значение имеет формула
мощности для булеана,
то есть для множества всех подмножеств
универсума
Пример 2.6. Сколькими способами можно разделить 4 книги между двумя студентами.
Решение.
Раздел определяется подмножеством
множества книг
,
выданных первому студенту. Поэтому
ответом будет число
.
число
упорядоченных выборок с повторениями
или число размещений из n
по с повторениями.
При
формировании упорядоченной
выборки,
мы строим k-компонентный
вектор
,
где каждая компонента
выбирается из множества
независимо от других компонент, причем
допускается неограниченное число
повторений.
Можно
записать:
.
Поэтому
имеет место формула:
,
доказательство которой осуществляется
методом математической индукции на
основе свойства произведения.
Пример 2.7.
Сколько существует четырехзначных
чисел, составленных из цифр
.
Решение.
Такие
числа представляют собой упорядоченные
выборки с возможными повторениями из
множества
по позициям отрезка
.
Поэтому ответом является число
.
Классическое определение вероятностей. Применение формул комбинаторики для расчета вероятностей
Пусть
производится некоторое испытание,
которое может иметь n
и только n
различных исходов. Будем считать, что
все эти исходы несовместны (не могут
произойти одновременно) и равновероятны.
Каждому событию
,
являющемуся подмножеством пространства
элементарных событий проводимого
испытания, поставим в соответствие
число
,
(1)
где
число
исходов испытания, благоприятствующих
событию А.
Число
называютвероятностью
события при данном испытании.
Пример 2.8. Из 35 экзаменационных билетов, занумерованных с помощью целых чисел от 1 до 35, наудачу извлекается один. Какова вероятность того, что номер вытянутого билета есть число, кратное трем?
Решение. Испытание состоит в том, что извлекается один билет. Так как билет вытягивается наудачу, то все исходы испытания равновероятны и, кроме того, они несовместны. Число возможных исходов испытания равно 35.
Событие A означает, что номер взятого билета кратен трем. Этому событию благоприятствуют 11 исходов испытания {3; 6; 9; ...; 33}.
Следовательно, по формуле (1) искомая вероятность равна
.
Пример 2.8. Группа туристов из пятнадцати юношей и пяти девушек выбирает по жребию хозяйственную команду в составе четырех человек. Какова вероятность того, что в составе этой команды окажутся два юноши и две девушки?
Решение.
Испытание состоит в том, что из двадцати
человек выбирают 4 человека. Так как
выбор осуществляется по жребию, то все
исходы испытания равновероятны и, кроме
того, они несовместны. Число исходов
испытания
,
так как выборка состоит из четырех
элементов и порядок их расположения в
выборке не учитывается.
Пусть
событие A
состоит в том, что в составе выбранных
окажутся два юноши и две девушки. Двух
юношей из 15 можно выбрать
способами и после каждого такого выбора
двух девушек из 5 можно выбрать
способами.
По
правилу произведения событию A
благоприятствует
исходов испытания. Искомая вероятность
вычисляется по формуле
и равна
Пример 2.9. Hа книжной полке произвольно расставлены 4 книги по теории вероятностей и 3 книги по теории множеств. Какова вероятность того, что книги по одному и тому же предмету окажутся рядом?
Решение. Испытание состоит в том, что 7 книг ставятся на полку. Так как они ставятся на полку произвольно, то все исходы испытания равновероятны, кроме того, они несовместны. Семь книг на полке могут быть упорядочены 7! способами.
Следовательно,
число всех исходов испытания
.
Событию
A,
состоящему в том, что книги по одному и
тому же предмету окажутся рядом,
благоприятствует
исходов.
Действительно, комплект книг по теории вероятностей может быть упорядочен 4! способами, и после каждого такого расположения книги по теории множеств могут быть упорядочены 3! способами. Кроме того, сами комплекты книг могут быть упорядочены двумя способами.
Таким
образом, вероятность события равна
Задание
Индивидуальные задания 1
Решить указанный набор задач из общего списка задач приведенного ниже.
|
№ вар. |
Номера задач |
№ вар |
Номера задач |
|
1 |
3,7,20 |
2 |
16,26,37 |
|
3 |
11,45,23 |
4 |
21,29,44 |
|
5 |
43,2,7 |
6 |
13,11,34 |
|
7 |
13,34,28 |
8 |
2,43,18 |
|
9 |
2,12,35 |
10 |
4,34,35 |
|
11 |
5,8,30 |
12 |
6,16,39 |
|
13 |
4,8,32 |
14 |
4,29,42 |
|
15 |
6,9,31 |
16 |
9,19,29 |
|
17 |
8,14,37 |
18 |
7,24,41 |
|
19 |
16,19,22 |
20 |
4,12,11 |
|
21 |
23,24,30 |
22 |
43,13,5 |
|
23 |
41,6,27 |
24 |
48,35,7 |
|
25 |
7,11,43 |
26 |
6,47,43 |
|
27 |
49,50 53 |
28 |
51,52,55 |
|
29 |
30,47,54 |
30 |
19,31,53 |
|
31 |
22,29,50 |
32 |
24,39,55 |
|
33 |
17,6,52 |
34 |
47,45,50 |
Список задач
|
№ |
Задание |
|
1 |
На железнодорожной станции имеются 5 светофоров. Сколько может быть дано различных комбинаций их сигналов, если каждый светофор имеет три состояния: «красный», «желтый» и «зеленый»? |
|
2 |
Сколькими способами можно распределить 6 различных учебников между четырьмя студентами? |
|
3 |
Сколькими способами можно разложить в два кармана 9 монет разного достоинства? |
|
4 |
Сколько «слов», каждое из которых состоит из семи различных букв, можно составить из букв слова выборка. |
|
5 |
В классе 30 учеников. Ежедневно для дежурства выделяются два ученика. Можно ли составить расписание дежурств так, чтобы никакие два ученика не дежурили вместе дважды в течение учебного года? |
|
6 |
Сколькими способами можно переставлять буквы слова логарифм так, чтобы второе, четвертое и шестое места были заняты согласными буквами? |
|
7 |
Сколько четырехзначных нечетных чисел можно составить из цифр числа 3694, если каждую цифру можно использовать не более одного раза? |
|
8 |
На прямой взяты 5 точек, а на параллельной ей прямой 7 точек. Сколько существует треугольников, вершинами которых являются эти точки? |
|
9 |
Сколькими способами можно распределить поровну 6 различных учебников между двумя студентами? |
|
10 |
Пять девушек и трое юношей играют в городки. Сколькими способами они могут разбиться на две команды по 4 человека, если в каждой команде должно быть, хотя бы по одному юноше? |
|
11 |
Из состава конференции, на которой присутствуют 52 человека, нужно выбрать делегацию, состоящую из 5 человек. Сколькими способами это можно сделать. |
|
12 |
Сколько букв алфавита можно составить из пяти сигналов в каждой букве, если три сигнала импульсы тока, а два паузы? |
|
13 |
Сколько четырехзначных чисел имеется в пятеричной системе счисления? |
|
14 |
В почтовом отделении продаются открытки десяти видов. Сколькими способами можно купить здесь набор из восьми открыток, если открыток каждого вида имеется не менее восьми штук? |
|
15 |
Трое юношей и две девушки выбирают место работы. Сколькими способами они могут это сделать, если в городе есть три завода, где требуются рабочие в литейные цехи (туда берут лишь мужчин), две ткацкие фабрики (туда приглашают женщин) и две фабрики, где требуются мужчины и женщины? |
|
16 |
Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5? |
|
17 |
Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если каждую из этих цифр можно использовать не более одного раза? |
|
18 |
Сколькими способами 7 человек могут разместиться в очереди в кассу? |
|
19 |
В классе изучают 10 предметов. В понедельник 6 уроков, причем все уроки разные. Сколькими способами можно составить расписание на понедельник? |
|
20 |
Сколько имеется пятизначных чисел, которые делятся на 5? |
|
21 |
На
одной из боковых сторон треугольника
взято
треугольника соединена прямыми с точками, взятыми на противоположной стороне, а) Сколько точек пересечения этих прямых образуется внутри треугольника? б) На сколько частей делят треугольник эти прямые?
|
|
22 |
Сколько есть двузначных чисел, у которых обе цифры четные? |
|
23 |
Сколько есть пятизначных чисел, у которых все цифры нечетные? |
|
24 |
Сколько четырехзначных чисел можно написать с помощью цифр 0, 1, 2, 3, 4, 5? |
|
25 |
Из двух спортивных обществ, насчитывающих по 100 фехтовальщиков, нужно выбрать по одному фехтовальщику для участия в состязаниях. Сколькими способами это можно сделать? |
|
26 |
Имеется 5 видов конвертов и 6 видов марок. Сколько способов отправить некоторый конверт с маркой? |
|
27 |
Сколькими способами можно выбрать гласную и согласную буквы из слова «камзол»7 |
|
28 |
Бросают игральную кость с шестью гранями и запускают волчок, имеющий 8 граней. Сколькими способами они могут упасть? |
|
29 |
На вершину горы ведут 5 дорог. Сколькими способами можно подняться на дорогу и спуститься с нее? Тот же вопрос, если подниматься и спускаться нужно разными путями. |
|
30 |
На ферме 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор сделан, сколькими способами его можно сделать еще один раз? |
|
31 |
Сколько можно составить трехцветных полосатых флагов, если имеется материя трех различных цветов? Тот же вопрос, если одна из полос должна быть красной. |
|
32 |
У одного человека 7 книг по математике, а у другого 9. Сколькими способами они могут поменять книгу одного на книгу другого? |
|
33 |
5 мальчиков и 5 девочек садятся в ряд на 10 расположенных подряд стульев, причем мальчики садятся на места с нечетными номерами, а девочки на места с четными номерами. Сколькими способами это можно сделать? |
|
34 |
Автомобильные номера составляются из одной, двух или трех букв и четырех цифр. Найти число таких номеров, используя 32 буквы русского алфавита. |
|
35 |
Сколько
разных делителей имеет число
|
|
36 |
Сколькими способами из 30 учащихся можно выбрать делегацию, состоящую из 3 учащихся? |
|
37 |
В комнате 10 лампочек. Сколько всего разных способов освещения комнаты, при которых горит ровно 6 лампочек? Сколько всего может быть различных способов освещения комнаты? |
|
38 |
Дано 8 точек, никакие 3 из которых не лежат на одной прямой. Сколько прямых можно провести, соединяя точки попарно? |
|
39 |
Сколько имеется четырехзначных чисел, у которых каждая следующая цифра больше предыдущей? |
|
40 |
Сколько имеется четырехзначных чисел, у которых каждая следующая цифра меньше предыдущей? |
|
41 |
Сколькими способами могут разместиться 5 покупателей в очереди в кассу? |
|
42 |
На собрании должны выступить 4 человека А, В, С, D, Сколькими способами их можно разместить в списке ораторов, если В не может выступать до того момента, пока не выступит А? |
|
43 |
На собрании должны выступить 4 человека А, В, С, D, Сколькими способами их можно разместить в списке ораторов, если В должен выступать непосредственно перед А? |
|
44 |
Из колоды 52 карты извлечено 5 карт. В скольких случаях среди выбранных карт окажется не менее одного туза? |
|
45 |
Из колоды 52 карты извлечено 5 карт. В скольких случаях среди выбранных карт окажется ровно один туз? |
|
46 |
Из колоды 52 карты извлечено 5 карт. В скольких случаях среди выбранных карт окажется ровно два туза? |
|
47 |
Из колоды 52 карты извлечено 5 карт. В скольких случаях среди выбранных карт окажется не менее чем два туза? |
|
48 |
В местком избрано 9 человек. Из них нужно выбрать председателя, зампредседателя, секретаря и культорга. Сколькими способами это можно сделать7? |
|
49 |
Из группы, состоящей из 7 мужчин и 4 женщин необходимо выбрать 6 человек так, чтобы среди них было не менее двух женщин. Сколькими способами это можно сделать? |
|
50 |
У англичан принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если общее число имен 300, а ему дают не более трех имен? Порядок (первое имя, второе имя, третье имя) существенен. |
|
51 |
Из спортивного клуба, насчитывающего 30 членов, надо составить команду из 4 человек для участия в беге на 1000 м. Сколькими способами это можно сделать? А сколькими способами можно составить команду для участия в эстафете 100+200+400+800? |
|
52 |
У отца есть 5 попарно различных апельсина, которые он выдает своим сыновьям так, что каждый получает либо один апельсин, либо ничего. Сколькими способами это можно сделать?. |
|
53 |
Рота состоит из 3 офицеров, 6 сержантов и 60 рядовых. Сколькими способами можно выделить из них отряд, состоящий из одного офицера, двух сержантов и 3 рядовых? |
|
54 |
В комнате студенческого общежития живут трое студентов. У них есть 4 чашки, 5 блюдец и 6 чайных ложек (все предметы отличаются друг от друга). Сколькими способами они могут накрыть стол для чаепития (каждый получает одну чашку, одно блюдце и одну ложку)? |
|
55 |
Сколькими способами можно выбрать 6 человек из 10, если данные двое из этих 10 не могут быть выбраны вместе? |
точек, на другой —
точек. Каждая из вершин при основании
?Индивидуальное задание 2
Решить указанный набор задач из общего списка задач приведенного ниже.
|
№ вар. |
Номера задач |
№ вар. |
Номера задач |
|
1 |
7,20 |
2 |
16,2 |
|
3 |
11,4 |
4 |
21,9 |
|
5 |
2,7 |
6 |
13,11 |
|
7 |
13,3 |
8 |
3,18 |
|
9 |
2,12 |
10 |
4,5 |
|
11 |
5,9 |
12 |
6,16 |
|
13 |
4,3 |
14 |
4,24 |
|
15 |
6,9 |
16 |
9,19 |
|
17 |
8,14 |
18 |
7,24 |
|
19 |
16,19 |
20 |
4,12 |
|
21 |
23,24 |
22 |
3,13 |
|
23 |
4,6 |
24 |
8,7 |
|
25 |
7,11 |
26 |
6,14 |
|
27 |
9,5 |
28 |
5,25 |
|
29 |
3,5 |
30 |
19,3 |
|
31 |
22,2 |
32 |
24,5 |
|
33 |
17,6 |
34 |
7,5 |
Список задач
|
№ |
Текст задания |
|
1 |
Какова вероятность того, что при случайном расположении в ряд кубиов, на которых написаны буквы А, Г, И, Л, М, , Р, Т, получится слово алгоритм? |
|
2 |
Какова вероятность того, что при случайном расположении в ряд кубиков, на которых написаны буквы А, А, А, Н, Н, С получится слово ананас? |
|
3 |
Найдите вероятность того, что наудачу выбранное 5-значное число составлено только из нечетных цифр. |
|
4 |
Какова вероятность того, что наудачу выбранное двузначное число не содержит ни одной двойки? |
|
5 |
Отряд учащихся из 25 человек участвует в военизированной игре. В отряде 5 следопытов и 4 связиста. В разведку надо направить четырех человек. Какова вероятность того, что в разведгруппу будут включены 2 связиста и 2 следопыта, если включение в разведгруппу равновероятно для любого ученика? |
|
6 |
На карточках написаны целые числа от 1 до 15 включительно. Наудачу извлекаются две карточки. Какова вероятность того, что сумма чисел, написанных на этих карточках, равна десяти? |
|
7 |
Для дежурства на вечере путем жеребьевки выделяются 5 человек. Вечер проводит комиссия, в составе которой 10 юношей и 2 девушки. Найдите вероятность того, что в число дежурных войдут обе девушки. |
|
8 |
В коробке находятся 4 красных и 6 зеленых карандашей. Из нее случайно выпали 3 карандаша. Какова вероятность того, что два из них окажутся красными? |
|
9 |
Имеется 6 билетов в театр, из которых 4 билета на места первого ряда. Какова вероятность того, что из трех наудачу выбранных билетов два окажутся на места первого ряда? |
|
10 |
Билет в партер стоит 50 коп., на бельэтаж 40 коп. и на ярус 30 коп. Найдите вероятность того, что взятые наудачу два билета стоят вместе не дороже 80 коп. |
|
11 |
Из 60 вопросов, включенных в экзамен, студент подготовил 50. Какова вероятность того, что из предложенных ему трех вопросов он знает два? |
|
12 |
На один ряд из семи мест случайным образом рассаживаются 7 учеников. Найдите вероятность того, что 3 определенных ученика окажутся рядом. |
|
13 |
Из букв слова событие, составленного с помощью разрезной азбуки, извлекаются наудачу и складываются друг за другом в порядке их извлечения 3 карточки (буквы). Какова вероятность получить при этом слово быт? |
|
14 |
Из пяти видов открыток, имеющихся в автомате, наудачу выбираются 3 открытки. Какова вероятность того, что все отобранные открытки будут разные? |
|
15 |
Во время спортивной игры по команде ведущего «становись!» 10 учеников в случайном порядке образовали строй в одну шеренгу. Какова вероятность того, что ученики А и В окажутся отделенными друг от друга тремя учениками? |
|
16 |
Группа, состоящая из пяти юношей и семи девушек, распределяет по жребию 4 билета в театр. Какова вероятность того, что в числе получивших билеты окажется больше девушек, чем юношей? |
|
17 |
В одном ящике имеется 12 однотипных деталей, из которых 4 нестандартные, в другом 15 деталей и 3 из них нестандартные. Из каждого ящика наудачу извлекается по 2 детали. Найдите вероятность того, что из первого ящика извлекли 2 нестандартные, а из второго ящика 2 стандартные детали. |
|
18 |
Из урны, содержащей 9 белых, 9 черных, 9 синих и 9 красных шаров, наудачу извлекаются 3 шара. Какова вероятность того, что извлеченными окажутся белые или черные шары? |
|
19 |
Из полного набора костей домино наудачу отобрали 4 кости, после чего кости возвратили в игру. Затем наудачу снова отобрали 4 кости. Какова вероятность того, что среди отобранных первый раз костей было 3 «дубля», а среди отобранных второй раз только 2? |
|
20 |
Имеется 5 шариков, которые случайно разбрасываются по 7 лункам. Найти вероятность, что в первых 5 лунках будет по одному шарику. |
|
21 |
Четыре шарика случайно и независимо разбрасываются по 4 лункам. Найти вероятность, что в первой лунке будет 3 шарика, второй один, а в третьей и четвертой шариков не будет. |
|
22 |
В лифт семиэтажного дома вошли 3 человека, которые случайно и независимо друг от друга выходят на этажах, начиная со второго. Найти вероятность, что все они выйдут на разных этажах. |
|
23 |
В урне находится 3 белых, 4 черных и 2 красных шара. Все шары извлекаются и их цвет записывается. Найти вероятность, что в такой записи белый цвет встретится раньше черного. |
|
24 |
В розыгрыше первенства по баскетболу участвуют 18 команд, среди которых имеется пять команд экстра-класса. Команды случайным образом делятся на две подгруппы. Найти вероятность, что в первой подгруппе окажутся все 5 команд экстра-класса. |
|
25 |
Колода из 52 карт случайным образом делится на две колоды по 26 карт. Найти вероятность, что в каждой колоде будет по 2 туза. |
Контрольные вопросы
Привести теоремы суммы и произведения.
Привести формулу сочетаний.
Привести формулу размещений.
Привести формулу мощности булеана.
Привести формулу числа перестановок.
Привести формулу классического определения веротности.