Комбинаторика

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Выполнила: Сапарова Меруерт, 1 курс, ЭК12Р, экономика

Проверила: Туманова М.Е.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Теория вероятностей - математическая наука, изучающая закономерности

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

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

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

Термин «комбинаторика» происходит от латинского слова «combina», что в переводе на русский означает – «сочетать», «соединять».

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

Рождение комбинаторики как раздела математики связано с трудами Б. Паскаля и П. Ферма по теории азартных игр. Большой вклад в развитие комбинаторных методов внесли Г.В. Лейбниц, Я. Бернулли и Л. Эйлер.

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

элемент можно выбрать k способами, а второй элемент m способами, то упорядоченную пару элементов можно составить km способами.

Действительно, пусть  множество A = {a1, a2, . . . , ak} состоит из k элемен-

тов, а множество B = {b1, b2, . . . , bm} - из m элементов.

Тогда можно образовать ровно km пар (ai, bj), взяв первый элемент  из мно-

жества A, а второй - из множества B. С элементом (a1) мы можем образовать m пар: (a1, b1), (a1, b2), . . . , (a1, bm). Столько же пар можно составить с элементом a2 или с любым другим из k элементов множества A. Таким образом, всего возможно km пар, в которых первый элемент выбран из множества A, а второй - из множества B.

С помощью этого утверждения  можно показать, что:

1. при подбрасывании трёх монет возможно 2 · 2 · 2 = 8 результатов;

2. бросая дважды игральную  кость, получим 6 · 6 = 36 результатов;

3. трёхзначных чисел бывает 9 ·  10 · 10 = 900;

4. трёхзначных чисел, все цифры которых различны, существует 9 · 9 · 8

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

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

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

 

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

Размещение – это набор из m различных элементов некоторого n-элементного множества, причем два размещения, отличающиеся порядком следования элементов, считаются различными. Стандартным обозначением для числа размещений m элементов из n является символ . Число размещений вычисляется по формуле

Эту формулу можно переписать в  виде .

Доказательство. Пусть у нас есть элементы  . Пусть   — возможные размещения. Будем строить эти размещения последовательно. Сначала определим   — первый элемент размещения. Из данной совокупности   элементов его можно выбрать   различными способами. После выбора первого элемента   для второго элемента   остается   способов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:

Пример. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?

Решение. Искомое число трехполосных флагов:

 

 

Сочетание – это набор из m различных элементов некоторого n-элементного множества, причем два любых сочетания, отличающиеся порядком следования элементов, совпадают. Стандартным обозначением для числа сочетаний m элементов из n является символ Число сочетаний вычисляется по формуле .

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

Между биномиальными  коэффициентами имеется много важных и интересных соотношений.  Например, .

 

Перестановкой множества  из   элементов называется расположение элементов в определенном порядке.

Так, все различные  перестановки множества из трех элементов   — это

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

Число всех перестановок из   элементов обозначается   (от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле

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

Решение. Искомое число расстановки 8 ладей

 

 по определению!

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

Как видим, в сочетаниях в отличие от размещений не учитывается  порядок элементов. Число всех сочетаний из   элементов по   элементов в каждом обозначается   (от начальной буквы французского слова “combinasion”, что значит “сочетание”).

Числа 

Все сочетания из множества   по два —  .

.

Свойства чисел 

1.  .

Действительно, каждому  -элементному подмножеству данного   элементного множества соответствует одно и только одно  -элементное подмножество того же множества.

2.  .

Действительно, мы можем  выбирать подмножества из   элементов следующим образом: фиксируем один элемент; число  -элементных подмножеств, содержащих этот элемент, равно  ; число  -элементных подмножеств, не содержащих этот элемент, равно  .