Дискретная математика Сборник заданий 2010. 1 Множества и отношения 1 Основные понятия и определения
![]()
|
3 Комбинаторика3.1 Основные понятия и определенияОсновное правило комбинаторики: k действий вместе могут быть выполнены ![]() Сочетания из n элементов по k (число всех k элементных подмножеств множества из n элементов) ![]() Число всех подмножеств множества А состоящего из n элементов: ![]() Число перестановок n элементов: ![]() Размещение n элементов по k местам (число упорядоченных k элементных подмножеств множества состоящего из n элементов) ![]() Размещения с повторениями из n элементов по k: ![]() Перестановки с повторениями (число способов разбить множество А из n элементов на m непересекающихся подмножеств): ![]() Сочетания из m элементов по n с повторениями ![]() 3.2 ЗаданияЗадание 1Решить задачи, используя знания комбинаторики. 1. Имеется пять видов конвертов без марок и четыре вида марок одного достоинства. Сколькими способами можно выбрать конверт с маркой для посылки письма? 2. Сколькими способами можно выбрать гласную и согласную буквы из слова "камзол"? 3. Бросают игральную кость с шестью гранями и запускают волчок, имеющий восемь граней. Сколькими различными способами они могут упасть? 4. Имеется 6 пар перчаток различных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку и одну на правую руку так, чтобы эти перчатки были различных размеров? 5. Из трех экземпляров учебников алгебры, 7 экземпляров учебника геометрии и 7 экземпляров учебника тригонометрии надо выбрать по одному экземпляру каждого учебника. Сколькими способами это можно сделать? 6. Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал пяти различных цветов? 7. Из состава конференции, на которой присутствуют 52 человека, надо выбрать делегацию, состоящую из 5 человек. Сколькими способами это можно сделать? 8. У мамы 2 яблока и 3 груши. Каждый день, в течении пяти дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано? 9. У отца есть 5 различных апельсинов, которые он выдает своим восьми сыновьям, так, что каждый получает либо один апельсин, либо ничего. Сколькими способами это можно сделать? 10. Из спортивного клуба, насчитывающего 30 членов, надо составить команду из 4 человек для участия в беге на 1000 м. Сколькими способами это можно сделать? 11. Четверо студентов сдают экзамен. Сколькими способами могут быть расставлены им отметки, если известно, что никто из них не получил неудовлетворительной отметки? 12. На школьном вечере присутствуют 12 девушек и 15 юношей. Сколькими способами можно выбрать среди них 4 пары для танцев? 13. Сколькими способами можно выбрать из 15 человек группу людей для работы? В группу могут входить 1,2,3...15 человек. 14. Сколькими способами 12 полтинников можно разложить по 5 различным кошелькам, если ни один из кошельков не должен быть пустым? 15. В комнате студенческого общежития живут трое студентов. У них есть 4 чашки, 5 блюдец и 6 чайных ложек (все разные). Сколькими способами они могут накрыть стол для чаепития (каждый получает по одному экземпляру каждого предмета)? 16. Сколькими способами можно выбрать 6 карт из колоды в 52 карты, так чтобы среди них были карты всех мастей. 17. Студенты на занятии либо записывали лекцию, либо нет. Юношей было 16, не записывающих лекцию – 6. Записывающих девушек ровно столько, сколько юношей, не записывающих лекцию. Сколько студентов было на лекции. 18. В аудитории n лампочек. Сколько существует разных способов освещения, при которых горит ровно k лампочек. Сколько всего способов. 19. Укротитель зверей хочет вывести на арену цирка 5 львов и 4 тигра, при этом нельзя, чтобы два тигра шли друг за другом. Сколькими способами можно расположить зверей (способ расстановки существенен – тигры и львы различны) 20. В скольких точках пересекаются диагонали выпуклого 5-угольника. 21. В колоде 26 карт черной и 26 карт красной масти. Сколькими способами можно выложить в ряд все карты, так, чтобы никакие две карты красной масти не лежали рядом. 22. Сколько существует n – значных натуральных чисел, у которых цифры расположены в неубывающем порядке. 23. Родители готовят подарки детям к Новому году, составляя наборы по 8 шоколадных батончиков. Сколькими способами можно составить наборы, если в распоряжении такие виды: "Mars", "Snickers", "Milky Way", "Topic", "Picnic". 24. Мать купила сыну 2 яблока, 3 груши и 4 апельсина. 9 дней подряд она будет давать их своему сыну каждый день по фрукту. Сколькими способами можно это сделать? 25. Сколькими способами 9 студентов могут занять 9 рабочих мест за компьютерами? 26. Сколькими способами можно составить группу из 20 человек, если имеется 26 кандидатов? 27. Сколькими способами можно разложить 35 разных предметов по 5 различным ящикам, так, чтобы в каждом ящике оказалось по 7 предметов? 28.Сколькими способами можно поставить в 4 бокса 28 разных машин, если в каждом боксе помещается 7 машин? 29. На автобазе 40 автобусов, которые могут быть распределены по 3 различным маршрутам. Сколько существует способов различных комбинаций автобусов? 30. Сколько вариантов оценок может получить студент, если у него 6 экзаменов? Библиографический списокГрей, П. Логика, алгебра и базы данных [Текст]. – М.: Машиностроение. – 1989. Иванилова, Т.Н. Дискретная математика: Учебное пособие [Текст]. – Ч.1-3. – Красноярск: КГТА. – 1995-1997. Кристофидес, Н. Теория графов. Алгоритмический подход [Текст]. – М.: Мир. – 1978. Кузнецов, А.П. Дискретная математика для инженера [Текст]. / Г.М. Адельсон-Вельский, А.П. Кузнецов. – М.: Энергоатомиздат. – 1988. Кук, Д. Компьютерная математика [Текст]. / Г. Бейз, Д. Кук. – М.: Наука. – 19 92. Липский, В. Комбинаторика для программистов [Текст]. – М.: Мир. – 1988. Мендельсон, Э. Введение в математическую логику. – М.: Наука. – 1976. Нефедов, В.Н. Курс дискретной математики [Текст]. / В.Н. Нефедов, В.А. Осипова. – М.: МАИ. – 1992. Новиков, П.С. Элементы математической логики [Текст]. – М.: Наука. – 1973. Рейнгольд, Э. Комбинаторные алгоритмы: теория и практика [Текст]. / Н. Део, Ю. Нивергельт, Э. Рейнгольд. – М.: Мир. – 1980. Яблонский, С.В. Введение в дискретную математику [Текст]. – М.: Наука. – 1979. Содержание 1 Множества и отношения 1 1.1 Основные понятия и определения 1 1.2 Задания 3 Задание 1 3 Задание 2 4 Задание 3 8 Задание 4 9 Задание 5 10 Задание 6 11 Задание 7 11 Задание 8 13 1.3 Примеры выполнения заданий 15 Задание 1 15 Задание 2 15 Задание 3 17 Задание 4 17 Задание 5 18 Задание 6 18 Задание 7 19 Задание 8 19 2 Теория графов 20 2.1 Основные понятия и определения 20 2.2 Задания 22 Задание 1. Ориентированный граф 22 Задание 2. Неориентированный граф 28 2.3 Примеры выполнения заданий 37 Задание 1 37 Задание 2 39 3 Комбинаторика 42 3.1 Основные понятия и определения 42 3.2 Задания 43 Задание 1 43 Библиографический список 45 |