Тема 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. Из десяти цифр можно составить число, содержащее сколь угодно знаков.