Комбинаторика. Перестановки, сочетания, размещения без повторений. Основные правила комбинаторики

 

Министерство образования и  науки Российской Федерации

 

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

 

«УФИМСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЯНОЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

 

 

 

 

 

Кафедра вычислительной техники и

инженерной кибернетики

 

 

 

 

 

КОМБИНАТОРИКА

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

Основные правила  комбинаторики.

 

 

Реферат

по дисциплине «Математика и статистика»

 

 

 

 

 

 

 

 

 

 

Выполнил студент

гр. БСО-11-01           ___________          Щетинина Л.К.

                                                                      подпись, дата                         инициалы, фамилия

 

Проверила           ___________         Михайловская И.М.

                                                                      подпись, дата                         инициалы, фамилия

 

 

 

 

 

Уфа 2011

Содержание

 

 

1. Введение   ________________________________________________3
2. Основные проблемы комбинаторики  _________________________5
3. Основные правила комбинаторики __________________________10
4. Комбинаторные задачи
1. Метод решения:  перебор возможных вариантов_________ 11

4.2.    Формулы  комбинаторики_____________________________11

5. Список литературы _______________________________________15

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение 

 

Говорят, что некто  усомнился в правах Ньютона на открытие закона всемирного тяготения, утверждая, что падение яблок  на землю наблюдалось испокон  веков. В этой шутке есть доля истины — до того, как та или иная область  знания формируется в особую науку, она сначала проходит длительный период накопления эмпирического материала, потом развивается в недрах другой, более общей науки и лишь затем выделяется в самостоятельную ветвь. А если ей повезет, то из ветви она становится большим, шумящим лесом со своими земляничными полянами и запутанными тропами. Не составляет исключения и история науки про общие законы комбинирования и образования различных конфигураций объектов, получившей название комбинаторики. С задачами, в которых приходится выбирать те или иные предметы, располагать их в определенном порядке и отыскивать среди разных расположений наилучшие, люди столкнулись еще в доисторическую эпоху, выбирая наилучшие расположения охотников во время охоты, воинов во время битвы, инструментов во время работы. Определенным образом располагались украшения на одежде, узоры на керамике, перья в оперении стрелы. По мере усложнения производственных и общественных отношений все шире приходилось пользоваться общими понятиями о порядке, иерархии, группировании. В том же направлении действовало развитие ремесел и торговли. Комбинаторные навыки оказались полезными и в часы досуга. Нельзя точно сказать, когда наряду с состязаниями в беге, метании диска, прыжках появились игры, требовавшие в первую очередь умения рассчитывать, составлять планы и опровергать планы противника. О таких играх английский нот Уордсворт писал:

 

Не нужно нам владеть  клинком.

Не ищем славы громкой.

Тот побеждает, кто знаком

С искусством мыслить  тонкий.

 

Среди предметов, положенных в пирамиду, где 35 веков тому назад был похоронен египетский фараон Тутанхамон, нашли разграфленную доску с тремя горизонталями и 10 вертикалями и фигурки для древней игры «сепет», правила которой мы, вероятно, никогда не узнаем. Позже появились нарды, шашки и шахматы, а также их различные варианты (китайские и японские шахматы, японские облавные шашки «го» и т. д.). В каждой из этих игр приходилось рассматривать различные сочетания передвигаемых фигур и выигрывал тот, кто их лучше изучил, знал выигрывающие комбинации и умел избегать проигрывающих. Таким образом со временем комбинаторика развивалась и выделялась в отдельную отрасль знания.

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

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

В первом приближении  можно сказать, что комбинаторика  изучает способы выборки и  расположения предметов, свойства различных  конфигураций, которые можно образовать из элементов, причем элементами могут быть числа, точки, отрезки, шахматные фигуры и т.д. Характерной чертой комбинаторных задач является то, что в них речь идет всегда о конечном множестве элементов. Чтобы устранить влияние конкретного вида выбираемых и располагаемых предметов, надо воспользоваться общим языком теории множеств, говорить о множествах и их подмножествах, об объединении нескольких множеств и их пересечении.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Основные проблемы комбинаторики.

 

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

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

 

 

 

Рисунок 1. Пятиконечная звезда

 

Иногда для отыскания  той или иной конфигурации оказываются  полезными соображения симметрии. Если не удается найти решение  из простых соображений, в ход пускается тяжелая артиллерия: теория чисел, теория групп и т. д. Бывает, однако, что и она не помогает — искомая конфигурация никак не складывается. Конечно, если задача возникла из практики, то в большинстве случаев можно быть уверенным в существовании решения. Гораздо хуже в этом отношении положение шахматиста, рассчитывающего комбинацию, или специалиста по шифрам, придумывающего новый код с заранее заданными свойствами. Они не знают заранее, существует ли то, что они ищут, не являются ли их труды поисками черной кошки в темной комнате, где кошки и в помине не было.

Таким образом, возникает вторая проблема комбинаторики.

2. Доказать существование или отсутствие конфигурации с заданными свойствами. Во многих случаях, однако, бывает недостаточно найти одну конфигурацию с заданными свойствами, а требуется описать все такие конфигурации и найти их число. Например, можно потребовать найти не одно, а все возможные расположения 10 точек на 5 отрезках, при которых на каждом отрезке лежат по 4 точки. Можно доказать, что кроме изображенной на рис. 1 пятиконечной звезды есть еще пять расположений с таким свойством. Они изображены на рисунке 2. Любое другое расположение с требуемыми свойствами отличается от одного из указанных шести лишь размерами отрезков, но не их взаимным расположением.

 

      

 

Рисунок 2. Возможные  расположения 10 точек на 5 отрезках.

 

Итак, мы пришли к двум проблемам комбинаторики, которые  в XVIII и XIX вв. исчерпывали все содержание этой науки. Перечислим еще три проблемы комбинаторики:

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

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

5. Из всех решений данной комбинаторной задачи выбрать оптимальное по тем или иным параметрам. Например, существует очень много способов прикрепить потребителей каменного угля к шахтам. Экономист будет искать способ, при котором транспортные расходы окажутся минимальными. Одной из классических оптимизационных задач является «задача о коммивояжере», в которой требуется наметить путь бродячего торговца, объезжающего заданные n городов, причем он должен по одному разу побывать в каждом городе и проделать весь путь за наименьшее время. Несмотря па усилия многих специалистов, до сих пор нет достаточно общего и удовлетворительного решения этой задачи.

 

Магические  квадраты.

Покажем пример решения комбинаторных проблем.

На известной гравюре  «Меланхолия» (1514г) немецкого художника  Альбрехта Дюрера присутствует один замечательный математический объект. Это квадрат, разбитый на клетки, в  которые вписаны числа. Нетрудно убедиться, что они удовлетворяют сразу нескольким условиям:

- если сложить все  числа в каждой строке,

- если сложить все  числа в каждом столбце,

- если сложить все  числа в двух диагоналях,

То все эти суммы  окажутся равны одному и тому же числу. Это и называется магическим квадратом.

Начнем с той самой  задачи, которую несколько тысяч  лет тому назад решили китайские  математики. Расположить числа 1, 2, 3, 4, 5, 6, 7, 8, 9 в виде квадрата так, чтобы  сумма чисел по каждому столбцу, строке и диагонали была одной  и той же. Методом прямого перебора решить эту задачу невозможно — 9 чисел можно расположить в виде квадрата 362 880 способами. Поэтому проведем математический анализ задачи. Выясним сначала, какой должна быть искомая сумма. Так как 1+2 + 3 + 4+5 + 6 + 7+8 + 9 = 45, то в каждой из 3 строк сумма чисел должна равняться 15. Это значительно уменьшает необходимый перебор — выбрать 3 слагаемых из данных чисел так, чтобы их сумма равнялась 15, можно лишь 8 способами: (9, 2, 4), (9, 5, 1), (8, 6, 1), (8, 5, 2), (8, 4, 3), (7, 6, 2), (7, 5, 3), 6, 5, 4). А число строк, столбцов и диагоналей в квадрате тоже равно 8. Значит, каждая из написанных комбинаций должна ровно один раз войти в искомый квадрат. Далее замечаем, что только число 5 входит в эти тройки 4 раза. Поэтому оно и должно стоять в центре таблицы на пересечении центральных строки, столбца и двух диагоналей. Числа 8, 2, 6 и 4, входящие в тройки по 3 раза, должны занять углы — они стоят на пересечении строки, столбца и диагонали. Оставшиеся числа 1, 3, 7 и 9 занимают места сверху, снизу, слева и справа от центра. Диагональные тройки (8, 5, 2) и (6, 5, 4) можно расположить 8 различными способами (у нас 2 диагонали, на каждой из которых можно еще переставлять крайние элементы). После выбора положения чисел 8, 2, 6, 4 положение остальных чисел однозначно определено. Мы не только нашли один магический квадрат 3-го порядка но и описали все такие квадраты из чисел 1, 2, 3, 4, 5, 6, 7, 8, 9.

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

1      2      3     4

5      6      7     8

9     10    11    12

13   14    15    16

если на каждой его  большой диагонали поменять местами  числа, симметричные относительно центра квадрата, т. е. числа 1 и 16, 6 и 11, 4 и 13, 7 и 10. В результате получим

16     2       3      13

5      11     10      8

9       7       6      12

4      14     15      1

В том, что полученный квадрат 4-го порядка магический, легко  убедиться. Еще более замечательным является магический квадрат 4-го порядка, найденный в индийской надписи XI или XII вв. п. э.:

 

 

7     12       1        14

2     13       8        11

16    3        10      5

9      6        15      4

Квадрат сохраняет свойство быть магическим и после того, как его строки одна за другой перемещаются сверху вниз (сначала первая под четвертой, затем вторая под  бывшей первой и т. д.) или столбцы аналогично перемещаются слева направо. Иными словами, если сделать ковер из таких квадратов, то, вырезав его любую часть из 4 строк и 4 столбцов, получаем снова магический квадрат. Всего существует 880 типов магических квадратов 4-го порядка. Существуют методы построения магических квадратов и более высокого порядка. Такими построениями занимались один из основателей теории чисел П. Ферма, выдающийся английский математик А. Кели, известный современный математик О. Веблен. Удалось построить, например, магические квадраты, которые после удаления нескольких крайних полос снова дают магические квадраты, магические кубы, в которых все квадратные грани, параллельные паре боковых граней, представляют магические квадраты с одной и той же суммой и т. д.

 

Во многих случаях  никакие предварительные расчеты  но позволяют найти конфигурацию элементов с заданными свойствами. Тогда остается единственный путь перебирать все варианты в надежде хотя бы случайно найти желаемую комбинацию. Как рассказывает известный американский популяризатор Мартин Гарднер, в 1910 г. некий Клиффорд У. Адаме решил построить магический шестиугольник. Он взял набор из 19 шестиугольных

плиток, написал на них  числа от 1 до 19 и начал составлять из них всевозможные шестиугольники, надеясь наткнуться на магический. Этим высокополезным делом он занимался... 47 лет, и только в 1957 г. нашел один такой многоугольник. Затеряв бумажку с решением, он лишь в 1962 г. восстановил решение и после полувека изысканий опубликовал следующий ответ (рисунок 3).

 

        

 

Рисунок 3. Магический шестиугольник.

 

 Из рисунка видно, что суммы по всем направлениям этого многоугольника равны 38. Совершенно неожиданно оказалось, что полученное Адамсом решение единственно — никаких других магических шестиугольников не существует.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 Основные правила комбинаторики.

 

Комбинаторные задачи бывают различных видов, но большинство  задач решаются с помощью основных правил – правила суммы и правила  произведения. 

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

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

При использовании правила  суммы в последней формулировке надо следить , чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В (или, как мы говорили раньше, чтобы ни одна комбинация не попала сразу в два класса). Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь m+n-k, где k – число совпадений.

Пример. Пусть из пункта А в пункт В можно добраться самолетом, поездом и автобусом, причем между этими пунктами существуют 2 авиамаршрута, 1 - железнодорожный и 3 - автобусных Следовательно, общее число маршрутов между пунктами А и В равно 2 + 1 + 3 = 6

Второе правило, называемое правилом произведения, несколько сложнее.  Часто при составлении комбинации из двух элементов известно, сколькими способами можно выбрать первый элемент, и сколькими способами второй, причем число способов выбора второго элемента не зависит от того, как именно выбран первый элемент. Пусть первый элемент можно выбрать m способами, а второй n способами. Тогда пару этих элементов можно выбрать mn способами. Иными словами:

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

Для доказательства правила  произведения заметим, что каждый из m способов выбора объекта А можно скомбинировать с n способами выбора объекта В. А это и приводит к mn способам выбора пары (А,В).

Пример. Сколькими различными способами можно распределить четыре шара по двум лункам, в которые помещается ровно один шар. Очевидно, первую лунку можно заполнить четырьмя способами, так как при выборе первой лунки имеется четыре шара. Вторую лунку можно заполнить тремя шарами, так как после заполнения первой лунки осталось три шара. Заметим, что с каждым из четырех способов заполнения первой лунки может совпасть любой из трех способов заполнения второй. Поэтому общее число способов распределения двух лунок равно 4x3 = 12

Комбинаторные задачи.

 

1. Метод решения: перебор возможных вариантов.

Способы:

1. способ кодировки
2. способ построения дерева возможных вариантов
3. способ набора точек и отрезков
4. способ табличный

 

2. Формулы комбинаторики.

Формулы для размещений, сочетаний и перестановок без повторений. 

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

В теории вероятностей принято  говорить не о комбинациях, а о  выборках. Поэтому мы будем придерживаться термина «выборка». В комбинаторике рассматриваются виды выборок — перестановки, размещения, сочетания.

Генеральная совокупность без повторений — это набор некоторого конечного числа различных элементов:

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

Выборкой объема будем называть произвольную группу из т элементов данной генеральной совокупности. Наглядному представлению такой выборки может служить последовательность из т шаров, выбранная из имеющегося множества.

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

Минимальным признаком, отличающим одну выборку объема т от другой выборки такого же объема, может быть:

1) их различие по  крайней мере одним элементом

2) их различие порядком расположения элементов.

Назовем такие выборки размещениями без повторений из п элементов по т.

Отсюда следует определение  понятия:

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

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

Число размещений из п элементов по m договоримся обозначать . Попробуем определить это число.

Пусть мы имеем п элементов. Первый элемент можно выбрать п способами. Второй приходится выбирать из оставшихся (п-1) элементов, поэтому второй элемент можно выбрать (п-1) способом. Тогда по правилу произведения пары двух элементов можно образовать п(п-1) способами. Третий элемент придется отбирать из числа оставшихся (п-2) элементов. Это можно сделать (п-2) способами. Тогда опять по правилу произведения тройки элементов можно образовать п (п-1)(п-2) способами. Аналогично четверки можно образовать п (п- 1) (п- 2) (п- 3) способами, а размещения по m элементов п (п — 1) (п — 2)…(п-(т- 1)) способами. Таким образом,

Преобразуем полученную формулу, умножая и деля правую часть на произведение:

. Тогда выведенная формула имеет вид:

 

.

 

В случае, когда т = п, одно размещение от другого отличается только порядком расположения элементов. Такие размещения называются перестановками без повторений. Таким образом, мы можем дать определение перестановкам без повторений.

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

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

Обозначим число  перестановок объема п символом Р_п. Тогда по определению

Среди размещений без повторений из п элементов по m (m < п) можно выделить такие, которые отличаются одно от другого  только первым признаком, а именно по крайней мере одним элементом. Значит:

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

Число таких сочетаний  обозначается символом . Разумеется, при т = п .

Характерный пример сочетаний без повторений — всевозможные варианты состава делегации в количестве, например, четырех человек от коллектива, в котором 15 человек.

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

,

откуда

.

 

Примеры использования  полученных формул:

Задача 1. На тренировках занимаются 12 баскетболистов. Сколько может быть образовано тренером разных стартовых пятерок?

Решение: Так как при  составлении стартовой пятерки тренера интересует только состав пятерки, то достаточно определить число сочетаний из 12 элементов по 5:

.

 

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

Решение: Ясно, что в  этом случае на каждой горизонтали  и каждой вертикали шахматной  доски может быть расположено  только по одной ладье. Число возможных  позиций — число перестановок из 8 элементов:

.

3. Для научной экспедиции необходимо укомплектовать следующий команду: начальник экспедиции, первый его заместитель, второй заместитель, два сотрудника и один стажер. Начальник и его заместители может быть отобрана из числа 25 кандидатов наук, два сотрудника — из числа 20 специалистов, в совершенстве знающих характер предстоящей работы, и стажер — из числа 8 наиболее подготовленных студентов. Сколькими способами можно укомплектовать команду экспедиции?

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

Обязанности у обоих  сотрудников примерно одинаковые. Они  могут выполнять их по очереди. Следовательно, пара сотрудников может быть укомплектована способами. Аналогичное положение и со стажером – его можно подобрать способами.

Значит по правилу  умножения всю экспедицию можно  укомплектовать способами.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список литературы.

 

1. Н.Я. Виленкин. Популярная комбинаторика. - М.: Наука, 1975.
2. Н.Я. Виленкин. Комбинаторика. - М.: Наука, 1969.
3. П.В. Грес. Математика для гуманитариев. - М.: Юрайт, 2000.
4. Я.С. Бродский. Статистика. Вероятность. Комбинаторика. - М.: Оникс, 2008.
5. Энциклопедия для детей. Метематика. Том 11. – М.: Аванта+, 1998.