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

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

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

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

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

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

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

Люди с глубокой древности  интересовались комбинаторными задачами. Так, в пирамиде Тутанхамона, построенной  более, чем 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.Определить число выпускаемых  лотерейных биолитов, что бы были  заинтересованы покупатели и  авторы лотереи..

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

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

При решении задач  комбинаторики используют следующие  правила:

Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m + n способами.

Правило произведения. Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана m*n способами.

Пример. Наряд студентки состоит из блузки, юбки и туфель. Девушка имеет в своем гардеробе четыре блузки, пять юбок и трое туфель. Сколько нарядов может иметь студентка?

Решение. Пусть сначала студентка выбирает блузку. Этот выбор может быть совершен четырьмя способами, так как студентка имеет четыре блузки, затем пятью способами произойдет выбор юбки и тремя способами выбор туфель. По принципу умножения получается 4*5*3=60 нарядов (комбинаций).

Термин «комбинаторика»  был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Разделы комбинаторики

Перечислительная комбинаторика 

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

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

Типичным примером задач данного  раздела является подсчёт количества перестановок. Другой пример — известная Задача о письмах.

Структурная комбинаторика 

К данному разделу относятся  некоторые вопросы теории графов, а также теории матроидов.

Экстремальная комбинаторика 

Примером этого раздела может  служить следующая задача: какова наибольшая размерность графа, удовлетворяющего определённым свойствам.

Теория Рамсея 

Основная статья: Теория Рамсея

Теория Рамсея изучает наличие регулярных структур в случайных конфигурациях элементов. Примером утверждения из теории Рамсея может служить следующее:

в группе из 6 человек всегда можно найти трёх человек, которые  либо попарно знакомы друг с другом, либо попарно незнакомы.

В терминах структурной комбинаторики  это же утверждение формулируется  так:

в любом графе с 6 вершинами  найдётся либо клика, либо независимое множество размера 3.