4_ОснМатОбрИнф(Комбинаторика)

4. КОМБИНАТОРИКА
Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиально возможное количество различных вариантов развития событий.
Основная формула комбинаторики
Пусть имеется k групп элементов, причем i-я группа состоит из ni элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n1*n2*n3*...*nk.
Пример 1. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из n1 элементов, а вторая - из n2 элементов. Сколько различных пар элементов можно составить из этих двух групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить n2. Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет n2. Так как в первой группе всего n1 элемент, всего возможных вариантов будет n1*n2. Пример 2. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться? Решение: n1=6 (т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), n2=7 (т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5, 6), n3=4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4, 6). Итак, N=n1*n2*n3=6*7*4=168.
В том случае, когда все группы состоят из одинакового числа элементов, т.е. n1=n2=...nk=n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно nk. Такой способ выбора в комбинаторики носит название выборки с возвращением.
Пример 3. Сколько всех четырехзначных чисел можно составить из цифр 1, 5, 6, 7, 8? Решение. Для каждого разряда четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=54=625.
Рассмотрим множество, состоящие из n элементов. Это множество в комбинаторике называется генеральной совокупностью.
Число размещений из n элементов по m
Определение 1. Размещением из n элементов по m в комбинаторике называется любой упорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.
Пример 4. Различными размещениями из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.
Число размещений в комбинаторике обозначается Anm и вычисляется по формуле:
[ Cкачайте файл, чтобы посмотреть картинку ] 
Замечание: n!=1*2*3*...*n (читается: "эн факториал"), кроме того полагают, что 0!=1.
Пример 5. Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различные и нечетные? Решение: т.к. нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:
[ Cкачайте файл, чтобы посмотреть картинку ] 
Определение 2. Сочетанием из n элементов по m в комбинаторике называется любой неупорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.
Пример 6. Для множества {1, 2, 3}сочетаниями являются {1, 2}, {1, 3}, {2, 3}.
Число сочетаний из n элементов по m
Число сочетаний обозначается Cnm и вычисляется по формуле:
[ Cкачайте файл, чтобы посмотреть картинку ] 
  Пример 7. Сколькими способами читатель может выбрать две книжки из шести имеющихся? Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:
[ Cкачайте файл, чтобы посмотреть картинку ]
Перестановки из n элементов
Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.
Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).
Число различных перестановок из n элементов обозначается Pn и вычисляется по формуле Pn=n!.
Пример 8. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд? Решение: эта задача о числе перестановок семи разных книг. Имеется P7=7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.
Обсуждение. Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно. Во-первых, от того, из какого количества элементов мы можем комбинировать их наборы (насколько велика генеральная совокупность элементов). Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.  И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере.
Пример. На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек? Решение: В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5. Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантовперестановок, которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.


Задача 1
Условие
В столовой предложено на выбор 6 блюд. Каждый день Вася берет некоторый набор блюд (возможно, не берет ни одного блюда), причем этот набор блюд должен быть отличен от всех наборов, которые он брал в предыдущие дни. Какое наибольшее количество дней Вася сможет питаться по таким правилам и какое количество блюд он в среднем при этом будет съедать за день? 
Подсказка
Каждому набору блюд можно сопоставить противоположный набор, состоящий в точности из тех блюд, которых нет в исходном наборе. 
Решение
   Количество дней равно, очевидно, количеству различных наборов из 6 блюд. Для каждого блюда есть две возможности – быть выбранным или невыбранным. Поэтому количество дней равно 26.     Каждому набору блюд можно сопоставить противоположный набор, состоящий в точности из тех блюд, которых нет в исходном наборе. Вместе в исходном и в противоположном наборе – 6 блюд, значит, в среднем приходится по 3 блюда на набор. Поскольку все 64 набора разбиваются на пары противоположных, то в среднем за эти 64 дня Вася съедал 3 блюда.
Ответ
64 дня, в среднем 3 блюда в день.

Варианты задачи 1
Вариант
Условие задачи

1
Сколькими способами можно разбить 14 человек на пары?

2
Сколько существует десятизначных чисел, в записи которых имеется хотя бы две одинаковые цифры? 

3
Сколько существует четырёхзначных номеров (от 0001 до 9999), у которых сумма двух первых цифр равна сумме двух последних цифр?

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

5
Поезду, в котором находится m пассажиров, предстоит сделать n остановок.
а) Сколькими способами могут выйти пассажиры на этих остановках?
б) Решите ту же задачу, если учитывается лишь количество пассажиров, вышедших на каждой остановке.


6
а) Найдите сумму всех трехзначных чисел, которые можно записать с помощью цифр 1, 2, 3, 4 (цифры могут повторяться).
б) Найдите сумму всех семизначных чисел, которые можно получить всевозможными перестановками цифр 1, ..., 7.


7
Параллелограмм пересекается двумя рядами прямых, параллельных его сторонам; каждый ряд состоит из m прямых. Сколько параллелограммов можно выделить в образовавшейся сетке?

8
На окружности отмечено десять точек. Сколько существует незамкнутых несамопересекающихся девятизвенных ломаных с вершинами в этих точках?

9
Пассажир оставил вещи в автоматической камере хранения, а когда пришел получать вещи, выяснилось, что он забыл номер. Он только помнит, что в номере были числа 23 и 37. Чтобы открыть камеру, нужно правильно набрать пятизначный номер. Каково наименьшее количество номеров нужно перебрать, чтобы наверняка открыть камеру?

10
Сколькими способами из полной колоды (52 карты) можно выбрать
   а) 4 карты разных мастей и достоинств?
   б) 6 карт так, чтобы среди них были представители всех четырех мастей?




Задача 2

Условие
В Монголии имеются в обращении монеты в 3 и 5 тугриков. Входной билет в центральный парк стоит 4 тугрика. Как-то раз перед открытием в кассу парка выстроилась очередь из 200 посетителей. У каждого из них, а также у кассира есть ровно 22 тугрика. Докажите, что все посетители смогут купить билет в порядке очереди.

Решение
Набрать 22 тугрика монетами по 3 и 5 тугриков можно единственным способом: две монеты по 5 тугриков и четыре монеты по 3 тугрика. Укажем, как должен действовать кассир. У первого посетителя он просит три монеты по 3 тугрика и дает ему сдачу монетой в 5 тугриков. У второго посетителя кассир просит две монеты по 5 тугриков и дает ему слачу двумя монетами по 3 тугрика. После этого у кассира монет каждого типа стало на одну больше. Продолжая действовать таким же образом, он сможет обслужить любое количество посетителей.

Варианты задачи 2

Вариант
Условие задачи

1
а) Сколькими способами можно разбить 15 человек на три команды по 5 человек в каждой?
б) Сколькими способами можно выбрать из 15 человек две команды по 5 человек в каждой?

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

3
В почтовом отделении продаются открытки 10 видов. Сколькими способами можно купить в нем
  а) 12 открыток;
  б) 8 открыток;
  в) 8 различных открыток?


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

5
Сколькими способами 4 черных шара, 4 белых шара и 4 синих шара можно разложить в 6 различных ящиков?

6
Сколькими способами можно разделить на команды по 6 человек для игры в волейбол группу: а) из 12;   б) из 24 спортсменов?

7
При игре в преферанс каждому из трех игроков раздают по 10 карт, а две карты кладут в прикуп. Сколько различных раскладов возможно в этой игре? (Считаются возможные раздачи без учета того, что каждые 10 карт достаются конкретному игроку.) 

8
Сколькими способами можно составить букет из 17 цветков, если в продаже имеются гвоздики, розы, гладиолусы, ирисы, тюльпаны и васильки? 

9
Нарисуйте все лестницы из 4 кирпичей в порядке убывания, начиная с самой крутой  (4, 0, 0, 0),  и заканчивая самой пологой  (1, 1, 1, 1).

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




Задача 3
Условие
На лотерейном билете требуется отметить 8 клеточек из 64. Какова вероятность того, что после розыгрыша, в котором также будет выбрано 8 каких-то клеток из 64 (все такие возможности равновероятны), окажется, что угаданы    а) ровно 4 клетки?   б) ровно 5 клеток?   в) все 8 клеток?

Решение
8 клеток из 64 могут быть выбраны  [ Cкачайте файл, чтобы посмотреть картинку ]  способами. Следовательно, вероятность того, что выпадет какой-то один определенный способ, равна  [ Cкачайте файл, чтобы посмотреть картинку ]  Число случаев, в которых оказались угаданными ровно k клеток равно числу способов, при которых выбираются k клеток из 8 отмеченных и  8 – k  клеток из 56 неотмеченных, то есть   [ Cкачайте файл, чтобы посмотреть картинку ]   Таким образом, вероятность угадать ровно k клеток равна   [ Cкачайте файл, чтобы посмотреть картинку ]

Ответ
а)  [ Cкачайте файл, чтобы посмотреть картинку ]   б)  [ Cкачайте файл, чтобы посмотреть картинку ]   в)  [ Cкачайте файл, чтобы посмотреть картинку ]


Варианты задачи 3

Вариант
Условие задачи

1
Сколькими способами можно разбить 10 человек на две баскетбольные команды по 5 человек в каждой?

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

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

4
Сколькими способами можно выложить в ряд 5 красных, 5 синих и 5 зеленых шаров так, чтобы никакие два синих шара не лежали рядом?

5
На каждом борту лодки должно сидеть по 4 человека. Сколькими способами можно выбрать команду для этой лодки, если есть 31 кандидат, причем десять человек хотят сидеть на левом борту лодки, двенадцать – на правом, а девяти безразлично где сидеть?

6
На полке стоит 12 книг. Сколькими способами можно выбрать из них 5 книг, никакие две из которых не стоят рядом?

7
Имеется 20 человек – 10 юношей и 10 девушек. Сколько существует способов составить компанию, в которой было бы одинаковое число юношей и девушек?

8
Международная комиссия состоит из 9 человек. Материалы комиссии хранятся в сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно изготовить и как их разделить между членами комиссии, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся не менее 6 членов комиссии?

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

10
На прямой отмечено 10 точек, а на параллельной ей прямой – 11 точек. Сколько существует  а) треугольников;  б) четырехугольников с вершинами в этих точках?



Приложенные файлы

  • doc 8930366
    Размер файла: 106 kB Загрузок: 0

Добавить комментарий