Тема 2.  Элементы комбинаторики

План:

1 Правило  суммы и произведения.

2 Перестановки,  размещения и  сочетания без повторений

3. Перестановки,  размещения и  сочетания с  повторениями.

4. Примеры комбинаторных задач из различных областей знаний

Теоретические сведения

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

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

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

С комбинаторными задачами приходится встречаться в самых разных областях знаний и деятельности человека. Это: информатика, математика, физика, биология. лингвистика и др.: Много комбинаторных задач используется при организации и приведения досуга: фокусы, шарады,  лотереи и др. Игра в шахматы, шашки, нарды, карты и др. связаны с комбинаторикой.

Люди с глубокой древности интересовались комбинаторными задачами. Так, в пирамиде Тутанхамона, построенной  более, чем 35 веков  назад обнаружена доска с тремя горизонтальными и десятью вертикалями линиями для игры в “сенет”, прототип игры в шахматы и шашки. Правила в эту игру, к сожалению, обнаружить до сих пор не удалось.

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

1  Правило  суммы и произведения.

Правило суммы:

Пусть множество A содержит m элементов, n(A)=m, множество B содержит k элементов, n(B)=k объединяются в новое множество. Возникает вопрос о числе элементов в объединении этих множеств, n(A∪B). Имеются две возможности:

1. Данные множества не имеют общих элементов. Они не пересекаются, n(A∩B).=0. Поэтому n n(A∪B).= n(A) + n(B)= m + k. Формула справедлива  для любого числа множеств.

2. Данные два множества имеют d общих элементов, n(A∩B).=d . Они пересекаются, n(A∩B).=0. Поэтому  n(A∪B).= n(A) + n(B) – n(A∩B)= m + k.- d

Если учувствуют в объединении три множества: n(A)=m , n(B)=k, n(C)=s, n(A∩B).=d₁, n(B∩C).=d₂, n(A∩C).=d₃,  n(A∩B∩C)=g, то формула имеет вид:

n(A∪B∪C).= n(A) + n(B)+ n(C)- n(A∩B)- n(A∩C)- n(A∩C)+n(A∩B∩C) или

n(A∪B∪C).= m + k +s – d₁ -  d₂ – d₃ +g

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

Правило произведения

Пусть множество A содержит m элементов, n(A)=m, множество B содержит k элементов, n(B)=k из элементов которых необходимо записать множество W, состоящее из  пар, первый элемент которых принадлежит множеству A, второй – множеству B. При этом справедлива формула: n(W)=n(AxB)=n(A)·n(B)=m·k. Множества W yназывается декартовым произведение множеств A и B. Формула справедлива  для любого числа множеств, в том числе при умножении множества само на себя.

2  Размещения,  перестановки,  и  сочетания без повторений.

Перестановки,  размещения и  сочетания считаются основными задачами (операциями) комбинаторики, которые подразделяются на два раздела: “без повторений“, когда элементы множества используются единожды и  “с повторениями“, когда элементы множества могут использоваться не однократно. Операции перестановки и  размещения  в результате их выполнения дают упорядоченных подмножеств. Множества, в которых установлен порядок следования называются кортежами. Длина кортежа – есть число элементов в нем. Сочетания дают не упорядоченное множество.

Размещения без повторения.

Пусть дано множество, содержащее n элементов.

Размещением из n элементов по m называется комбинация (кортеж), содержащая   m элементов, взятых из данного множества, отличающихся либо элементами, либо их порядком следования. Под размещение можно понимать любое упорядоченное множество, состоящее из n элементов, взятых из данного множества. Обозначается: ,

=n(n-1)(n-2) …(n-m+1) – число размещений без повторения

Перестановки без повторений

Перестановкой из n элементов называется любая комбинация (кортеж) из n элементов, отличающаяся от других только порядком следования. Под перестановкой понимается  любое упорядоченное множество, составленное из n  элементов данного множества.  Обозначается P(n), P_n

Р= n(n-1)(n-2) …3·2·1 – число перестановок  без повторения

Произведение n последовательных натуральных чисел называется факториалом и обозначается Р!, 5!, 10!

Сочетания без повторений

Сочетанием из n элементов по m, называется любая комбинация, состоящая из n элементов, взятых из данного множества, которые отличаются, по крайней мере, одним элементом. Под сочетанием можно понимать любое подмножество, содержащее n элементов, взятых из данного множества, состоящего из m элементов. Обозначается: ,

– число сочетаний  без повторения

- другая формула, которая легко получается из предыдущей формулы.

При вычислении сочетаний легко усмотреть свойства, которое упрощает вычисления:

С_n^m =C_n^n-m ,     С₁¹ =1,            С_n ⁿ=1,            C_n¹=n,             С_n⁰ =1

3.  Размещения,  перестановки, сочетания с  повторениями.

Примеры ситуаций, приводящих  к рассмотрению  комбинаторных задач  с повторениями:

1. У продавца цветов имеется  гвоздики: 10 – красных, 15 белых,  20 оранжевых. Необходимо составить букеты   по 5 гвоздик каждый, в которых  должны присутствовать гвоздики разного цвета.  Сколькими способами можно это сделать.

2. В компьютерах вся информация шифруется с помощью двух знаков: 0 и 1 кортежами, в которых   8, 16, 32  знака . Естественно нули и единицы повторяются.

3. Из десяти цифр можно составить число, содержащее сколь угодно знаков.

Размещения, с  повторениями

Размещением из n элементов по k с повторениями – кортежи, содержащая m элементов, взятых из данного множества, отличающихся либо элементами, либо их порядком следования, причем элементы в комбинациях могут повторяться от 1 до m раз.

Дано множество X={a,b,c,d}. составить все размещения  из этого четыре элементного множества по два с повторениями. Эта записывается в виде:  Ā _n^k.

Запишем  некоторые  кортежи длины 2. (a; a ), (a; b). (a; c),  (a; d), (b; b) …Всего таковых  кортежей    =  4·4=16. С другой стороны это есть численность декартового произведения  =т(АхА)= 4·4=16

Запишем  некоторые  кортежи длины 3. (a; a; a), (a; a; b) …. Всего таковых  кортежей    =  4·4·4=64

Общая задача. Найти число кортежей дины k, которые можно составить из элементов множества, содержащего n элементов.

– число размещений с повторения из n элементов по k

Перестановки с повторениями

Необходимо составить шеренгу из 20 физкультурников, среди которых 10 имеют белые майки, 4- синие, 6 – красные. Сколькими способами это можно сделать?  Если бы цвета не повторялись, то это можно сделать P(20)=20!. В виду того, что цвета будут повторяться,  то перестановок с повторениями будет меньше в 10!·41·61· раз.

Общая задача. Имеются  элементы  k видов. Причем k₁ вида   n₁ штук, k₂ вида   n₂ штук и т.д. Сколько перестановок можно сделать из этих элементов?

,  где  n = n₁+n₂+…=n  – сумма всех элементов.

Сочетания с  повторениями

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

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

Ситуации такого характера приводят к  сочетаниям с повторениями, Обозначается.

Общая задача. Требуется составить k наборов (кортежей) из элементов данных n  множеств d₁. d₂, d₃,…d_n. Число элементов в каждом из множеств d_i не меньше числа k.

Формула вычисления числа сочетаний с повторениями имеет несколько разновидностей:

=. = . =P(n-1;k).  . Наиболее предпочтительнее первая формула, сведенная к вычислению сочетаний без повторения.

4. Примеры комбинаторных задач из различных областей знаний. Комбинаторика в древней Греции. Комбинаторика в биологии, генетике, химии и др.

В древне Греции философы, служители религии, астрологи, гадалки много внимания уделяли науке нумерологии – науке о числах. Они устанавливали различные закономерности числе, изучали  влияние чисел и их комбинаций на человека, природу, мироздание.

Модель  строения ДНК была расшифрована  методами комбинаторики в 1953 году в Кембридже Ф.Криком и Дж. Уотсоном. Ими была изготовлена спиральная модель ДНК после рассмотрения различных комбинаций связи нуклеотидов, аминокислот  и других  объектов между собой. При этом был открыт генетический код, который содержит информацию о виде растения или животного, в том числе   наследственную и иную информацию.

Без комбинаторных задач не было бы информатики, компьютера, сотового  телефона. Например, установления кодов в ЭВМ для записи информации, такими, что бы они ни были избыточными и были достаточными для записи любой информации. Соединение элементов в ЭВМ, установление связей в кристалле, и микросхеме  рассчитывается с помощью комбинаторных задач.

С точки зрения теории множеств, комбинаторика изучает подмножества конечных множеств, и операции над ними.

Приведем несколько  общих таковых задач:

1.Найти конфигурацию элементов, обладающих заранее заданными свойствами.

2. Доказать существование или отсутствие конфигурации с заданным свойством.

3. Найти число конфигураций с заданным свойством

4. Описать все способы решения указанных выше задач.

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

К перечисленным задачам подходят такие ситуации как:

1.Соеденить некоторое число точек на плоскости  не пересекающими  (пересекающими в одной, двух и более точках)  линиями.

2. Транспортные задачи, связанные перевозками.

3. Задачи массового обслуживания

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

Практические  замятия. Решение комбинаторных задач

Требования к знаниям умениям и навыкам Студент должен знать:  основные комбинаторные объекты (типы выборок); формулы и правила количества выборок (для каждого из типов  выборок) уметь: определять тип комбинаторного объекта (тип выборки); рассчитывать  количество выборок заданного типа в заданных условиях.

Практические задания

1. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, если каждая цифра в запись числа входит только один раз?
2. Решение. Искомое число трехзначных чисел  Р=3!=2-3 = 6.
3. Сколько можно составить сигналов из 6 флажков различного цвета, взятых по два?
4. Решение. Искомое число сигналов М =6-5 = 30.
5. 3. Сколькими   способами   можно   выбрать две детали из ящика, содержащего 10 деталей?
6. Ответ: Искомое число способов С= 45.
7. 4. Их села N в село D ведет k дорог, а из села D в село Q  ведет s дорог. Сколько существует различных способов поездки из села N в cело Q.
8. Имеется  по 10 различных конвертов, открыток и марок. Сколькими способами можно составить комплект: конверт, марка, открытка?
9. Сколько необходимо издать словарей для перевода с одного языка на другой для 10 языков.

10.Из  колоды  в 36 карт составляется пара черная – красные масти. Сколькими способами это можно сделать.

11.Из  колоды  в 36 карт вытаскивается одна карта. Какова вероятность того, что вытащенная карта туз

12.Из  колоды  в 36 карт вытаскивается две карты подряд.  Какова вероятность того, что первая ката будет дама, вторая – туз?

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

Решение.  Всего возможных вариантов равно 6·6=36. Благоприятствующие исходы наступят при выпадение следующих пар очков: 2-2, 2-4, 2-6, 4-2, 4-4, 4-6, 6-2, 6-4, 6-6. Всего получилось 9 таких вариантов. р=9/36=1/4=0,25

14.В группе 6 мужчин и 4 женщины. Наудачу отобрали 7 человек. Найти вероятность того, что среди отобранных лиц окажется 3 женщины.

Ответ: Р=(С₄³ · С₆⁴ ) / С₁₀⁷ =0,5

15.В группе спортсменов находится  7 человек перворазрядников и 3 второго разряда по шахматам. Наудачу отбирают поочередно троих человек Какова вероятность того, что все отобранные лица будут спортсмены первого разряда.

Ответ: Р= 7/10 · 6/9 · 5/8 = 7/24

16. Сколькими способами можно рассадить 5 человек на одной скамейке.

17.Сколькими способами можно выбрать из 20 человек 10 человек для участии в олимпиаде по информатике?

18.Сколько различных четырехзначных чисел можно составить из цифр 0,1,2,3,5,:6 если: цифры не повторяются, если цифры повторяются.

19.Сколькими различными  способами можно выбрать несколько буква из фразы: “Око за око, зуб за зуб”. Решение. Буква “о”  входить 4 раза. Ее можно выбрать  4 раза или ни разу, потному для этой буквы существует 5 способов выбора. Аналогично для буквы “л” – 3 способа и т.д.  5·3·5·3·3·3=2025.

Дополнительные задания можно взять из [5, с 256] и [12, с 67]