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

 

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

 

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

 

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

 

 

 

 

 

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

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

 

 

 

 

 

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

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

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

 

 

Реферат

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

 

 

 

 

 

 

 

 

 

 

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

гр. БСО-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. Совершенно неожиданно оказалось, что полученное Адамсом решение единственно — никаких других магических шестиугольников не существует.