1. Элементы комбинаторики
 Скачать 0.83 Mb.
|
|
5 1. Элементы комбинаторики омбинаторика – раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисление элементов) и отношения на них. Комбинаторика отвечает на вопрос о том, сколько различных комбинаций, подчиненных определенным условиям, можно составить из заданных объектов. Основные понятия комбинаторики Перестановки. Пусть n объектов необходимо расположить в различных порядках следования друг за другом. Каждый способ расположения этих объектов называется перестановкой. Общее количество перестановок из n объектов определяется выражением Размещения без повторений Пусть из общего количества объектов необходимо отобрать группу из m объектов с учетом порядка их следования. Каждый способ выбора этих объектов называется размещением без повторения. Общее количество возможных групп будет ! ( 1) ... ( 1) ( )! m n n A n n n m n m Размещения с повторениями. Пусть n – количество различных видов объектов. В группу нужно отобрать m объектов с учетом порядка их следования, при этом элемент каждого вида К 6 можно использовать несколько раз. Тогда общее число таких групп определяется выражением m m n A n Сочетания получаются, если из общего количества n объектов необходимо отобрать группу из m объектов без учета порядка их следования. Число таких групп равно ! !( )! m n n C m ПРИМЕР 1. Мама оставила дочке к чаю три конфеты Комильфо, Рафаэлло и Ферреро Роше. Сколькими способами девочка может их съесть за чаем Решение Дочь может съесть свои три конфеты в различных порядках. Общее количество способов равно числу перестановок из трех объектов 3 3! 1 2 3 6 P Перечислим всевозможные способы 1) КР, ФР 3) Р, К, ФР 5) ФР, Р, К 2) К, ФР, Р 4) Р, ФР, К 6) ФР, КР ПРИМЕР 2. В студенческой группе 25 человек. Сколькими способами группа может выбрать старосту и профорга Решение Из 25 человек нужно отобрать двоих, причем порядок отбора имеет значение, т.к. староста и профорг ‒ различные должности. Общее количество способов равно количеству размеще- ний из 25 элементов по 2: 7 2 25 25! 25 24 23 1 25 24 600. (25 2)! 23 1 A ПРИМЕР 3. Студент вовремя проведения финала КВН познакомился с девушкой из другого вуза и записал номер ее телефона на клочке бумаги. Впоследствии он обнаружил, что две последние цифры номера оторвались. Сколько времени ему понадобится, чтобы наверняка дозвониться до новой знакомой, если на набор каждого номера уходит по 45 секунд Решение Каждая из двух последних цифр номера может принимать значение от 0 дои цифры могут повторяться. Общее количество возможных номеров равно количеству размещений с повторениями из 10 цифр по 2 цифры 2 2 10 10 Если каждый номер набирать 45 секунд, то студенту потребуется не более 100 45 секунд, или 1 часа 15 минут. ПРИМЕР 4. Для прохождения производственной практики на Московском НПЗ из группы, состоящей из 20 студентов, необходимо отобрать 5 человек. Сколькими способами это можно сделать Решение Поскольку порядок отбора студентов не имеет значения (все пятеро попадут на НПЗ), то общее количество способов равно количеству сочетаний из 20 элементов по 5: 5 20 19 18 17 16 19 3 17 16 15504. 3 2 1 20! 20 19 18 1 20 19 18 17 16 5!(20 5)! 5! 15 14 1 5 4 3 2 1 C 8 Задачи к разделу 1 1.1. Из города А в город Введут дорога из города В в город С ‒ 7 дорог. Сколькими способами можно из города А проехать в город С через город В 1.2. В финале конкурса должны выступить 6 пианистов. Порядок их выступления решили определить жребием. Сколько существует вариантов жеребьевки 1.3. Код цифрового замка на портфеле содержит три набора по 10 цифр каждый (от 0 до 9). Рассеянный профессор забыл установленный им ранее код замка. Какое максимальное время придется потратить ученому, чтобы открыть портфель, если на проверку каждого кода уходит 5 секунд 1.4. В чемпионате России по футболу приняли участие 16 команд. Сколькими способами они могут поделить призовые места 1.5. В чемпионате России по футболу участвуют 16 команд. Две последние по итогам сезона переходят во вторую лигу. Сколькими способами команды могут перейти во вторую лигу 1.6. В симпозиуме приняли участие 16 ученых. При встрече они все обменялись рукопожатиями. Сколько всего состоялось рукопожатий 1.7. Каждый из 72 студентов первого курса, присутствующих на лекции, поговорил по мобильному телефону с двумя своими товарищами, находящимися в той же аудитории. Какую сумму при этом заработали компании сотовой связи, если каждый разговор стоил 10 рублей 9 1.8. Сколькими способами из колоды в 32 карты, можно отобрать 8 карт так, чтобы среди них оказалось ровно три туза 1.9. После окончания первого курса 23 студента призывного возраста факультета экономики и менеджмента имеют более двух академических задолженностей и подлежат отчислению. Военкомат должен призвать на военную службу 9 человек. Сколькими способами это можно сделать 1.10. Полководец Суворов перед походом через Альпы решил женить 10 своих холостых солдат. В деревне, через которую шла армия, оказалось подходящих по возрасту девушек. Сколькими способами Суворов может осуществить задуманное 1.11. В автомобильных номерах каждого региона России должно быть три цифры и три буквы. Каково максимальное число номеров для каждого региона (В номерах используются лишь те буквы, которые имеются в латинском алфавите. 1.12. На стоянке такси стоят 9 машин. Сколькими способами их могут занять четыре пассажира Сколько существует способов рассадки, если пассажиры должны сидеть в разных автомобилях 1.13. Для игры в лотерее «Спортлото» необходимо отметить в карточке чисел из 36. Сколькими способами можно заполнить карточку лотереи 1.14. Сколько различных трехбуквенных слов можно составить из слова КАРАКАТИЦА 10 1.15. Сколькими способами можно рассадить 8 кроликов в четыре разные клетки Рассмотреть случаи а) все кролики одинаковы (те имеет значение лишь их количество, попавшее в каждую из клеток б) кролики различаются по именам. 1.16. В буфете университета продаются пирожные 4 видов Наполеон, Эклер, Песочное и Корзиночка. Студенка решила вместо обеда купить 7 пирожных. Сколькими способами она может это сделать. Сколько нужно словарей, чтобы переводить с любого из пяти языков на любой другой из них 1.18. Какой коэффициент окажется перед слагаемым, содержащим множитель 16 4 a b , если раскрыть скобки в выражении 20 (2 ) a b ? 1.19. В урне лежит 3 красных, 6 черных и 7 белых шаров. Сколькими способами можно вынуть 5 шара. (Способы отличаются количеством выбранных шаров того, или иного цвета. 1.20. Группа из 25 студентов сдает экзамен по математике. Сколько существует исходов экзамена. (Рассмотреть задачу сточки зрения деканата, для которого нет различия между студентами, и сточки зрения группы. 1.21. Студент решил позвать одну из своих 5 подруг на концерт и послал каждой из них по письму с приглашением Сколько вариантов похода на концерт есть у студента 11 2. Алгебра событий обытие, относящиеся к результату некоторого испытания (эксперимента, которое при выполнении некоторого комплекса условий может либо произойти, либо не произойти, называется случайным событием Событие, которое в результате испытания – обязательно наступит, называется достоверным событием – никогда не может наступить, называется невозможным со- бытием Случайные события обычно обозначаются латинскими буквами A, B, C, D, …; достоверные события – , невозможные – . Суммой двух событий A и B называется событие C = A + B , или иначе, C = A B), которое произойдет, если произошло хотя бы одно из этих событий A или B (риса. Произведением двух событий A и B называется событие C = A B , (или C = A B), которое произойдет, если произошли одновременно оба события A ирис. б. Разностью двух событий A и B называется событие C = A – B (или C = A \ B), которое произойдет, если произошло событие, ноне произошло событие B (рис. в. С А В А В А В 12 Риса Рис. б A B Рис. в A \ B Событие = \ A называется противоположным событию. Оно наступает тогда и только тогда, если не происходит событие A риса. Если каждое появление события A влечет за собой появление события B, то говорят, что из A следует B , и пишут A B , или A B рис. б. Если одновременно имеют место два соотношения A B и B A, то события A и B называют равносильными и записывают События A и B называются несовместными в данном испытании, если они не могут произойти одновременно, те. A B = . Риса Событие Рис. б A B Полной группой событий называются такие события А, В, С, …, что при всякой реализации заданного комплекса условий обязательно происходит хотя бы одно из них, то есть А+ В + С + … = А В А А B 13 A B C Замечание 1. В соответствии сданным определением события в полной группе могут быть совместными. В литературе встречается определение полной группы событий, включающее требование об их несовместности. ПРИМЕР 1. Бросается игральная кость. Событие А ‒ выпало четное число очков, событие В ‒ выпало не более трех очков, событие С ‒ выпало пять очков. Образуют ли эти события полную группу Решение Имеем А = {2, 4,6}; В = {1, 2,3}; С = {5} Тогда А+ В + С = {1,2,3,4,5,6}. То есть события А, В, С образуют полную группу. При этом Аи В ‒ совместные события. Замечание 2. Действия над событиями могут быть проиллюстрированы с помощью диаграмм B енна, которые и представлены на рис и 2. ПРИМЕР 2. Пусть А, В и С – события, означающие попадание точки соответственно в области А, В и С (риса. Что означает событие А В+ С A B C а) б) Рис. 3. Иллюстрации к примеру 2 14 Решение Событие А В+ С означает попадание в область (АВ)С, которая заштрихована на рис. б. ПРИМЕР 3. Староста студенческой группы факультета АиВТ представил в деканат отчет, в котором говорилось В группе учатся 27 студентов, из которых 15 юношей и 12 девушек. Не имеют задолженности по математике 18 студентов, из них 9 юношей. Занимаются спортом 17 человек, среди которых 10 юношей и 6 успевающих. Трое юношей не имеют задолженностей и не занимаются спортом. Однако, хорошо знающий математику декан факультета, тут же указал старосте на ошибку в подсчетах. В чем состояла ошибка старосты Решение Изобразим группу студентов на диаграмме Венна. Заштрихованная часть представляет юношей. Длинной пунктирной линией ограничена часть студентов без задолженности по математике, коротким пунктиром ‒ спортсмены. Соответствующие области занумерованы. Например, область (1) ‒ юноши, не сдавшие математику и не занимающиеся спортом, (5) ‒ девушки, спортсменки и без задолженностей. Таким же образом будем обозначать количество студентов соответствующей категории. Согласно докладу старосты (1) + (2) + (4) + (6) = 15 (всего юношей) (3) + (5) + (7) + (8) = 12 (всего девушек) (2) + (4) = 9 (юноши, сдавшие математику) (3) + (5) = 9 (девушки, сдавшие математику) (4) + (6) = 10 (юноши ‒ спортсмены) (5) + (7) = 7 (девушки ‒ спортсмены) 15 (4) + (5) = 6 (успевающие спортсмены) (2) = 3 (юноши ‒ не спортсмены и без долга) Рис. 3. Иллюстрация к примеру 3 Из последних шести соотношений легко находится, что (4) = 6, (6) = 4, (5) = 0, (7) = 7, (3) = 9. Подставив их впервые два равенства, получим (1) + 3 + 6 + 4 = 15 (1) = 2 9 + 0 + 7 + (8) = 12 (8) = ‒ 4. Получено противоречие. Из доклада старосты следует, что количество девушек, имеющих долг по математике и не занимающихся спортом, отрицательно. Староста, действительно, ошибся. Задачи к разделу 2 2.1. В семье четверо детей. Совместны ли события A ‒ в семье не менее двух сыновей B ‒ в семье не менее двух дочерей Образуют ли эти события полную группу 2.2. Монета бросается пять раз. Будут ли несовместными события A ‒ не менее трех раз выпал орел B ‒ решка выпала, по крайней мере, два раза Образуют ли эти события полную группу (3) (1) (2) (6) (4) (5) (7) (8) 16 2.3. Бросаются две игральные кости. Будут ли несовместными события хотя бы на одной кости выпало не более четырех очков. B ‒ сумма выпавших очков не менее одиннадцати. Образуют ли события полную группу 2.4. Какие из написанных ниже утверждений верны для призвольных событий A, B, C: а) ABC AB + AC + BC, б) ABC A + в) AB + AC + BC A + B + C, где, ж) AB A B , з) ( ) A B C AC BC 2.5. Судно имеет одно рулевое устройство, 4 котла и 2 турбины. Событие А означает исправность рулевого устройства, В исправность го котла (k = 1, 2, 3, 4), событие С исправность той турбины (i = 1, 2). Событие D судно управляемо обеспечивается при исправности рулевого управления, хотя бы одного из котлов и хотя бы одной турбины. Выразить событие D через события А, В и С На уборку картошки поехали 92 студента. Большинство из них для дневного перекуса взяло с собой бутерброды, но мамы некоторых самых счастливых) студентов вместо бутербродов испекли им пирожки с мясом. Известно, что у 47 человек были с собой бутерброды с колбасой, ус сырому с ветчиной. Бутерброды и с сыром, и с колбасой взяли 28 студентов с колбасой и с ветчиной – 31 студент с сыром и с ветчиной – 26 студентов. Все три вида бутербродов взяли 25 человек. Сколько было чадолюбивых мам, которые испекли своим детям пирожки 2.7. В группе аспирантов каждый знает хотя бы один иностранный язык. Шестеро знают английский, шестеро – немецкий, семеро – французский. Четыре аспиранта знают английский и немецкий языки, трое – немецкий и французский, двое ‒ английский и французский. Один человек знает все три языка. Сколько аспирантов в группе Сколько из них знают только английский язык только французский 2.8. Электрические цепи составлены по схемам, изображенным на риса, б, в, г. Событие А (k = 1, 2) элемент исправен, событие В (i = 1, 2) элемент b i исправен, событие С исправен элемент c. Для каждой из схем записать событие Е по цепи проходит тока также противоположное событие (цепь разорвана Рис. 4. К задаче 2.8 A 2 b 1 b 2 b 1 b 2 с a) б) a 1 a 2 A 1 A 2 a 1 a 2 A 1 A 2 с b 1 с b 1 b 2 A 1 A 2 в) г) a 1 a 2 a 1 a 2 18 2.9. Деканат решил проконтролировать посещение лекции по высшей математике четырьмя нерадивыми студентами. Каждый из них на выбранной для контроля лекции может либо присутствовать, либо не нет. Рассматриваются события A на лекции был ровно один из 4-x студентов B на лекции был хотя бы один из этих студентов C на лекции было не менее х студентов D на лекции было ровно 2 студента E на лекции было ровно 3 студента F на лекции были все 4 студента. Описать события 1) A + B; 2) AB; 3) B + C; 4) BC; 5) D + E + F; 6) Совпадают ли события BF и CF ; BC и D ? 2.10. Нефтеналивной порт имеет 5 причалов. События A занято четное число причалов, В занят хотя бы один причал. Описать события и AB. 2.11. Что представляют собой события Си+ С, если аи, б) B C ив и A C? 2.12. При каких условиях справедливы соотношения а) A + B |