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

Примечания

  • Björner, Андерс; и Стэнли, Ричард П.; (2010); комбинаторный сборник
  • Bóna, Miklós; (2011); прогулка через комбинаторику (3-й выпуск). ISBN 978-981-4335-23-2, ISBN 978-981-4460-00-2 (pbk)
  • Грэм, Рональд Л.; Groetschel, Мартин; и Lovász, Ласло; редакторы (1996); Руководство Комбинаторики, Томов 1 и 2. Амстердам, NL и Кембридж, Массачусетс: Elsevier (Северная Голландия) и MIT Press. ISBN 0 262 07169 X
  • Lindner, Чарльз К.; и Роджер, редакторы Кристофера А.; (1997); Теория Дизайна, CRC-пресса; 1-й. выпуск (31 октября 1997). ISBN 0-8493-3986-3.
  • Riordan, Джон (1958); введение в комбинаторный анализ, Нью-Йорк, Нью-Йорк: Wiley & Sons (переиздала)
  • Стэнли, Ричард П. (1997, 1999); исчисляющая комбинаторика, тома 1 и 2, издательство Кембриджского университета. ISBN 0-521-55309-1, ISBN 0-521-56069-1
  • Линт фургона, Джейкобус Х.; и Уилсон, Ричард М.; (2001); Курс в Комбинаторике, 2-м Выпуске, издательстве Кембриджского университета. ISBN 0-521-80340-3

История

Основные комбинаторные понятия и исчисляющие результаты появились всюду по древнему миру. В 6-м веке BCE, древний индийский врач Сушрута утверждает в Сусруте Самите, что 63 комбинации могут быть сделаны из 6 различных вкусов, взятых по одному, два за один раз, и т.д., таким образом вычислив все 2 − 1 возможность. Греческий историк Плутарх обсуждает спор между Chrysippus (3-й век BCE) и Hipparchus (2-й век BCE) довольно тонкой исчисляющей проблемы, которая, как позже показывали, была связана с числами Шредера. В Ostomachion Архимед (3-й век BCE) рассматривает загадку черепицы.

В Средневековье комбинаторика продолжала изучаться, в основном за пределами европейской цивилизации. Индийский математик Mahāvīra (c. 850), обеспеченный формулы для числа перестановок и комбинаций, и эти формулы, возможно, было знакомо индийским математикам уже в 6-м веке CE. Философ и астроном раввин Авраам ибн Эзра (c. 1140), установил симметрию двучленных коэффициентов, в то время как закрытая формула была получена позже talmudist и математиком Леви ben Джерсон (более известный как Gersonides) в 1321.

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

В течение Ренессанса, вместе с остальной частью математики и наук, комбинаторика обладала возрождением. Работы Паскаля, Ньютона, Якоба Бернулли и Эйлера стали основополагающими в появляющейся области. В современные времена работы Дж. Дж. Сильвестра (в конце 19-го века) и Перси Макмэхон (в начале 20-го века) положили начало исчисляющей и алгебраической комбинаторике. Теория графов также обладала взрывом интереса в то же время, особенно в связи с четырьмя цветными проблемами.

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

Сочетания

Выбирая размещение, мы должны были выбрать из множества несколько объектов и упорядочить их. В частности, мы выбирали три команды из шести и указывали, какая из них будет первой, какая второй, а какая третьей. Поэтому размещения «Локомотив, Зенит, Краснодар» и «Локомотив, Краснодар, Зенит» отличались друг от друга.

Однако порою этот порядок не имеет значения. Так, существует известная лотерея, где предлагается угадать 7 чисел из 49, которые выпадут во время розыгрыша из барабана. При этом порядок их выпадения не играет никакой роли. Игрок, выбирая эти 7 чисел, с точки зрения математики формирует сочетание из 49 по 7.

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

Количество возможных сочетаний из n по k обозначается буквой С:

Для вычисления количеств сочетаний из n по k сначала найдем количество аналогичных размещений. Оно вычисляется по формуле:

Однако ясно, что, как и в случае с перестановками с повторениями, некоторые сочетания мы посчитали несколько раз. Вернемся к примеру с командами. Если мы выбрали команды Л (Локомотив) , З (Зенит) и К (Краснодар), то мы можем составить ровно 3! = 6 размещений из них:

ЛЗК

ЛКЗ

ЗЛК

ЗКЛ

КЛЗ

КЗЛ

Однако все они соответствуют только одному сочетании – ЛКЗ. Таким образом, считая количество размещений, мы посчитали каждое сочетание не один, а 3! раз. Поэтому для нахождения количества сочетаний в комбинаторике надо поделить число размещений на число перестановок k элементов:

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

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

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

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

Решение. Посчитаем число сочетаний из 6 по 3:

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

Ответ: 20

Пример. Сколько комбинаций чисел может составить игрок, играющий в лотереи «5 из 36», «6 из 45», «7 из 49»?

Решение. В каждом из этих случаев игрок выбирает сочетание нескольких чисел. Посчитаем их число:

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

Ответ: 376992; 8145060; 85900584

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

Решение. Для того чтобы провести прямую, достаточно выбрать любые 2 точки из 8. Общее количество прямых будет равно числу сочетаний из 8 по 2:

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

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

Если бы, например, точки АВС лежали бы на одной прямой, то при выборе сочетаний АВ, ВС и АС мы получали бы одну и ту же прямую:

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

Это же условие гарантирует, что, выбрав любые 3 и 8 точек, мы сможем построить треугольник с вершинами в этих точках, а выбрав 4 точки, получим четырехугольник. Поэтому для подсчета количества треугольников и четырехугольников следует искать число сочетаний по 3 и 4:

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

Ответ: 28 прямых, 56 треугольников и 70 четырехугольников.

Пример. В одной урне находится 10 различных шаров с номерами от 0 до 9, а в другой – 8 различных шаров с первыми восемью буквами алфавита. По условиям лотереи ведущий вытаскивает из первой урны два шара с числами, а из второй – три шара с буквами. Для победы в лотерее надо угадать выпавшие шары. Сколько комбинаций шаров может выпасть в игре?

Решение. Посчитаем отдельно, сколькими способами можно выбрать 2 шара с цифрами из 10 и 3 шара с буквами из 8:

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

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

56•45 = 2520

Ответ: 2520

Заметим, что выбирая, например, сочетание из 49 по 7, мы одновременно выбираем и сочетание из 49 по 49 – 7 = 42. Действительно, игрок, обводящий в кружок в лотерейном билете свои 7 счастливых чисел, одновременно и определяет остальные 42 числа, какие числа он НЕ считает счастливыми. Для наглядности запишем число сочетаний в обоих случаях:

Получили одну и ту же дробь, в которой отличается лишь последовательность множителей в знаменателе. Можно показать, что и в общем случае число сочетаний из n по k совпадает с количеством сочетаний из n по (n– k):

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

Исторический очерк

Основная статья: История комбинаторики

Джероламо Кардано написал математическое исследование игры в кости, опубликованное посмертно. Теорией этой игры занимались также Тарталья и Галилей. В историю зарождавшейся теории вероятностей вошла переписка заядлого игрока Шевалье де Мерэ с Пьером Ферма и Блезом Паскалем, где были затронуты несколько тонких комбинаторных вопросов. Помимо азартных игр, комбинаторные методы использовались (и продолжают использоваться) в криптографии — как для разработки шифров, так и для их взлома.

Треугольник Паскаля

Блез Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления: «треугольник Паскаля». Хотя этот способ был уже известен на Востоке (примерно с X века), Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника. Наряду с Лейбницем, он считается основоположником современной комбинаторики. Сам термин «комбинаторика» придумал Лейбниц, который в 1666 году (ему было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном искусстве». Правда, термин «комбинаторика» Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику. Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» () множество сведений по комбинаторике.

В этот же период формируется терминология новой науки. Термин «сочетание» (combination) впервые встречается у Паскаля (, опубликован в 1665 году). Термин «перестановка» (permutation) употребил в указанной книге Якоб Бернулли (хотя эпизодически он встречался и раньше). Бернулли использовал и термин «размещение» (arrangement).

После появления математического анализа обнаружилась тесная связь комбинаторных и ряда аналитических задач. Абрахам де Муавр и Джеймс Стирлинг нашли формулы для аппроксимации факториала.

Окончательно комбинаторика как самостоятельный раздел математики оформилась в трудах Эйлера. Он детально рассмотрел, например, следующие проблемы:

  • задача о ходе коня;
  • задача о семи мостах, с которой началась теория графов;
  • построение греко-латинских квадратов;
  • обобщённые перестановки.

Кроме перестановок и сочетаний, Эйлер изучал разбиения, а также сочетания и размещения с условиями.

Задача об экипаже корабля

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

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

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

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

Где ai — командиры, bi — инженеры и ci — врачи. При этом в ходе тестирования каждого человека было выяснено, что командир a1 психологически хорошо ладит с инженерами b1 и b3, a2 — с b1 и b2, а вот врач c3 несовместим с инженером b1 и т. д. Вопрос, которые изначально ставился перед руководителем проекта — сколько экипажей можно составить при таких условиях. Из составленной диаграммы видно, что всего таких экипажей может быть 10. Но что было бы, если вопрос о психологической совместимости не имел веса? Тогда получается, что после выбора командиров ai, существовало бы по 3 альтернативы для каждого из них в выборе инженера. Соответственно, для пары командира и инженера также имелось бы 3 варианта врачей. Тогда количество комбинаций достигнет 4*3*3 = 36 экипажей.

Современное развитие

В начале XX века начала развиваться комбинаторная геометрия: были доказаны теоремы Минковского — Радона, Радона, Хелли, Юнга, Бляшке, а также строго доказана изопериметрическая теорема. На стыке топологии, анализа и комбинаторики были доказаны теоремы Борсука — Улама и Люстерника — Шнирельмана. Во второй четверти XX века были поставлены проблема Борсука и проблема Нелсона — Эрдёша — Хадвигера. В 1940-х годах оформилась теория Рамсея. Отцом современной комбинаторики считается Пал Эрдёш, который ввёл в комбинаторику вероятностный анализ

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

Развитие комбинаторики

Значимые подвижки в вопросах комбинаторики случились с появлением в 20 в. вычислительных машин, программирования, а главное — дискретной математики. В этот период комбинаторика получает пик своего бурного развития и становится полноценной наукой. Комбинаторные методы начинают использоваться повсеместно:

  • решение транспортных задач;
  • составление расписаний;
  • подготовка планов производства и продажи товаров;
  • в теории случайных процессов;
  • в математической статистике и теории вероятностей;
  • в подготовке и проведение экспериментов;
  • в шахматах;
  • в термодинамике;
  • в геометрии;
  • и во многих других областей.

История

Первые предпосылки комбинаторики как науки появились в 16 в. Способствовало развитию данной области знаний в большой степени увлечение людей азартными играми: в карты, кости, лотереи проигрывали не просто золото и драгоценности, а дворцы и имения. Поэтому, задаваясь вопросом, например, о том, как часто можно выбросить удачный набор очков на костях или получить два туза, люди постепенно пришли к основам комбинаторики и вероятности. Помогла ли комбинаторика кому-то выигрывать больше или терять меньше? Вопрос интересный, но его рассмотрение выходит за пределы данной статьи.

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

Первый математик, активно увлекавшийся вопросами комбинаторики — это итальянец Тарталья (1499-1557 гг.) После него в изучение данных вопросов активно погрузились такие именитые ученые, как Паскаль, Ферма, Бернулли, Лейбниц, Эйлер и др. Однако стоит заметить, что комбинаторика по прежнему оставалась если не забавной игрой с числами, то теорией, которая используется исключительно в азартных играх и не имеет права применяться где-либо еще.

Задача о лото

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

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

Как-то раз Нина, играя в лото, задумалась. Она часто наблюдала, как ведущий достает из мешка один и тот же номер. Но в то же время первые два бочонка оказывались одинаковыми значительно реже. Тогда она задалась вопросом, сколькими способами можно последовательно достать из мешка два бочонка? Элементы комбинаторики помогают ответить на ее вопрос.

Комбинаторика и ее основные принципы

Очень часто приходится решать задачи, в которых надо посчитать количество возможных вариантов для той или иной ситуации. Например, сколько позиций может возникнуть на шахматной доске после первого хода обоих игроков? Сколько разных паролей длиною в десять символов можно записать, если ни один символ не использовать дважды? Сколько разнообразных комбинаций чисел может выпасть при игре в лотерею «6 из 49»? На все эти вопросы помогает ответить специальный раздел математики, называемый комбинаторикой. Почти всегда комбинаторную задачу можно сформулировать так, чтобы ее вопрос начинался словами «сколькими способами…».

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

Очевидно, что если в конечном множестве содержится n элементов, то есть ровно n способов выбрать один из них.

Пример. В классе 15 человек. Сколькими способами учитель может назначить одного из них ответственным за чистоту доски?

Ответ. Таких способов ровно 15.

В комбинаторике существует два основных правила. Первое из них называется правилом сложения.

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

Несмотря на формулировку, по сути это очень простое правило.

Пример. В магазине продается 14 телевизоров Panasonic и 17 телевизоров Sony. Петя хочет купить один телевизор. Сколько у него вариантов покупки?

Решение. По правилу сложения Петя может выбрать один из 14 + 17 = 31 телевизоров.

Ответ: 31 телевизор.

Особое значение имеет второе правило, которое называют правилом умножения.

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

Проиллюстрируем это правило.

Пример. В секции бадминтона 15 мальчиков и 20 девочек. Тренер должен отправить на соревнования смешанную пару. Сколько вариантов действий у него?

Решение. Тренер может составить 15•20= 300 разнополых пар из своих воспитанников.

Ответ: 300

Пример. Пете нужно купить технику для компьютера. В магазине продается 20 различных клавиатур, 25 моделей геймпадов и 30 компьютерных мышей. Купить надо по одному экземпляру каждого из этих устройств. Сколько вариантов покупки есть у него?

Решение. Сначала подсчитаем число возможных пар «клавиатура-геймпад». Их количество равно 20•25 = 500. Теперь составим «тройку» из одной из 500 пар и одной из 30 мышей. Число троек равно 500•30 = 15000.

Ответ: 15000

Правила сложения и умножения можно комбинировать.

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

Решение. Очевидно, что слов из одной буквы можно составить ровно 30. Количество двухбуквенных слов равно количеству пар, которые можно составить из этих букв, то есть 30•30 = 900. Трехбуквенных слов можно составить 30•30•30 = 27000. Всего же слов длиною не более 3 букв будет

30 + 900 + 27000 = 27930

Ответ: 27930

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

[править] Основные операции

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

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

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

Составление разбиений — это разложение натурального числа на натуральные слагаемые, сумма которых равна самому числу.

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

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

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

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

Древний период


Гексаграмма из «Книги Перемен»

Магический квадрат на гравюре Дюрера «Меланхолия»

Комбинаторные мотивы можно заметить в символике китайской «Книги Перемен» (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний мужского и женского начал, а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо. Историки отмечают также комбинаторные проблемы в руководствах по игре в Го и другие игры. Большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты.

Классическая задача комбинаторики: «сколько есть способов извлечь m элементов из N возможных» упоминается ещё в сутрах древней Индии (начиная примерно с IV века до н. э.). Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона. Во II веке до н. э. индийцы знали, что сумма всех биномиальных коэффициентов степени n равна 2n{\displaystyle 2^{n}}.

Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, если оно и существовало, до нас не дошло. Хрисипп (III век до н. э.) и Гиппарх (II век до н. э.) подсчитывали, сколько следствий можно получить из 10 аксиом; методика подсчёта нам неизвестна, но у Хрисиппа получилось более миллиона, а у Гиппарха — более 100000. Аристотель при изложении своей логики безошибочно перечислил все возможные типы трёхчленных силлогизмов. Аристоксен рассмотрел различные чередования длинных и коротких слогов в стихотворных размерах. Какие-то комбинаторные правила пифагорейцы, вероятно, использовали при построении своей теории чисел и нумерологии (совершенные числа, фигурные числа, пифагоровы тройки и др.).

Задача о суеверном руководителе

Жил да был на свете руководитель, который верил, что число 8 приносит ему сплошные неудачи. Поэтому он решил избавиться от всех чисел, которые содержали бы восьмерку. Работало под его началом 600 человек. У каждого был идентификационный номер пропуска на работу, состоящий из трех чисел. Недолго думая, руководитель решил исключить и из номеров пропусков число 8. И тут он задумался, а хватит ли разных чисел на 600 человек из диапазона от 000 до 999, которые не включали бы 8?

Очевидным решением данной задачи является выписывание вручную всех чисел от 000 до 999 и вычеркивание тех из них, в которых присутствует восемь. Можно ли решить поставленную задачу более простым способом? Если для 999 чисел задача с перебором всех вариантов выглядит выполнимой, то диапазон от 000000 до 999999 потребует значительно больших усилий. Именно для экономии сил и времени призваны формулы комбинаторики.

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

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

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

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

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

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

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

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

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

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

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

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

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

Вероятностная комбинаторика

Этот раздел отвечает на вопросы вида: какова вероятность присутствия определённого свойства у заданного множества.

Топологическая комбинаторика

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

Инфинитарная комбинаторика

Инфинитарная комбинаторика (англ.) — применение идей и методов комбинаторики к бесконечным (в том числе, несчётным) множествам.

Смежные области

Комбинаторная оптимизация

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

Кодирование теории

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

Дискретная и вычислительная геометрия

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

Комбинаторика и динамические системы

Комбинаторные аспекты динамических систем — другая появляющаяся область. Здесь динамические системы могут быть определены на комбинаторных объектах. Посмотрите, например

граф динамическая система.

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

Там увеличивают взаимодействия между комбинаторикой и физикой, особенно статистической физикой. Примеры включают точное решение модели Ising и связь между моделью Potts с одной стороны, и цветным и полиномиалами Tutte, с другой стороны.

Размещения, перестановки и сочетания

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

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

Перестановки из n элементов

Определение 3. Перестановкой
из n элементов
называется любой упорядоченный набор
этих элементов.

Пример 7a. Всевозможными перестановками
множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3,
2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).

Число различных перестановок из n элементов обозначается Pn и
вычисляется по формуле Pn=n!.

Пример 8. Сколькими способами семь книг
разных авторов можно расставить на полке в один ряд?Решение:эта задача о числе
перестановок семи разных книг. Имеется P7=7!=1*2*3*4*5*6*7=5040
способов осуществить расстановку книг.

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

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

Пример 9. На родительском собрании
присутствует 20 человек. Сколько существует различных вариантов состава
родительского комитета, если в него должны войти 5 человек?Решение: В этом примере нас
не интересует порядок фамилий в списке комитета. Если в результате в его
составе окажутся одни и те же люди, то по смыслу для нас это один и тот же
вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5.
Иначе будут обстоять дела, если каждый член комитета изначально отвечает за
определенное направление работы. Тогда при одном и том же списочном составе
комитета, внутри него возможно 5! вариантов перестановок, которые имеют значение. Количество
разных (и по составу, и по сфере ответственности) вариантов определяется в
этом случае числом размещений
из 20 элементов по 5.

Задачи для самопроверки
1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5,
6, если цифры могут повторяться?
Т.к. число четное на третьем месте может стоять 0, 2, 4, 6, т.е. четыре цифры. На втором месте может стоять любая из семи цифр. На первом месте может стоять любая из семи цифр кроме нуля, т.е. 6 возможностей. Результат =4*7*6=168.
2. Сколько существует пятизначных чисел, которые одинаково читаются слева
направо и справа налево?
На первом месте может стоять любая цифра кроме 0, т.е. 9 возможностей. На втором месте может стоять любая цифра, т.е. 10 возможностей. На третьем месте тоже может стоять любая цифра из, т.е. 10 возможностей. Четвертая и пятая цифры определены заранее, они совпадают с первой и второй, следовательно, число таких чисел 9*10*10=900.
3. В классе десять предметов и пять уроков в день. Сколькими способами можно
составить расписание на один день?
4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе
20 человек?

n = C204 = (20!)/(4!*(20-4)!)=(16!*17*18*19*20)/((1*2*3*4)*(16!))=(17*18*19*20)/(1*2*3*4)=4845.

5. Сколькими способами можно разложить восемь различных писем по восьми
различным конвертам, если в каждый конверт кладется только одно письмо?
В первый конверт можно положить 1 из восьми писем, во второй одно из семи оставшихся, в третий одно из шесть т.д. n = 8! = 1*2*3*4*5*6*7*8 = 40320.
6. Из трех математиков и десяти экономистов надо составить комиссию,
состоящую из двух математиков и шести экономистов. Сколькими способами это
можно сделать?

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

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

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

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

  1. Составить выборку объектов с учетом каких-либо свойств.
  2. Доказать или опровергнуть существование выборки при определенных условиях.
  3. Найти число возможных вариантов комбинаций.
  4. Найти все комбинации и определить алгоритм их перечисления.
  5. Найти оптимальное решение той или иной задачи при заданных условиях.

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

Средневековье

В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями.

В Западной Европе ряд глубоких открытий в области комбинаторики сделали два еврейских исследователя, Авраам ибн Эзра (XII век) и Леви бен Гершом (он же Герсонид, XIV век). Ибн Эзра подсчитывал число размещений с перестановками в огласовках имени Бога и обнаружил симметричность биномиальных коэффициентов, а Герсонид дал явные формулы для их подсчёта и применения в задачах вычисления числа размещений и сочетаний.

Несколько комбинаторных задач содержит «Книга абака» (Фибоначчи, XIII век). Например, он поставил задачу найти наименьшее число гирь, достаточное для взвешивания любого товара весом от 1 до 40 фунтов.

Комбинаторные задачи с решениями

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

Типы задач Что требуется найти Методы решения
Магический квадрат Фигура, в которой сумма чисел в рядах и столбцах должна быть одинакова (его разновидность – латинский квадрат). Рекуррентные соотношения. Решается подобная же задача, но с гораздо меньшим множеством элементов по известным правилам и формулам.
Задача размещения Стандартная производственная задача (например, в лоскутной технике) — найти возможные способы разложения количества продуктов в ячейки в определенном порядке. Включения и исключения. Как правило, применяется при доказательстве различных выражений.
Задачи про торговцев Суть — найти все возможные пути прохождения людей из пункта А в пункт В. Траектории. Для этого вида задач характерно геометрическое построение возможных способов решения.
Михаил Фирсов
Оцените автора
( Пока оценок нет )
Добавить комментарий