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

Размещения

      Рассмотрим следующую задачу.

      Задача.   9   карточек пронумерованы числами   1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 .   Из этих карточек четыре наугад взятых карточки выкладываем в ряд. Сколько при этом можно получить различных четырехзначных чисел?

      Решение.Сначала слева направо пронумеруем места в ряду, куда выкладываем карточки: первое место, второе, третье, четвертое.

      На первое место можно положить одну из   9   карточек. Для этого есть   9   способов. В каждом из этих   9   способов на второе место можно положить одну из оставшихся   8   карточек. Таким образом, существует

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

способа, чтобы положить карточки на первое, второе и третье места. В каждом из этих   504   способов на четвертое место можно положить одну из оставшихся   6   карточек. Отсюда вытекает, что существует

различных способа, чтобы выложить в ряд   4   карточки из набора, состоящего из   9   пронумерованных карточек. Таким образом, при выкладывании карточек можно получить   3024   различных четырехзначных числа.

      Ответ:   3024.

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

      Определение 1. Рассмотрим множество, содержащее   n   элементов, и все его , содержащие   k   элементов. Каждое из этих подмножеств называют размещением из   n   элементов по   k   элементов.

      Если обозначить символом  число размещений из   n   элементов по   k   элементов, то будет справедлива формула:

Комбинаторика (1)

      В соответствии с , формулу (1) можно также записать в виде:

      В задаче множеством из   n   элементов является исходный набор из   9   пронумерованных карточек, а упорядоченным подмножеством из   k   элементов –   4   карточки, выложенные в ряд.

      Таким образом, при решении задачи мы на частном примере подсчитали, чему равно число размещений из   9   элементов по   4   элемента, т.е. число

      В соответствии с формулой (1),

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

что и было получено в задаче.

      Замечание 1. Введенные в данном разделе размещения также называют размещениями без повторений.

      Замечание 2. Из формул для числа перестановок и числа размещений вытекает формула

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

смысл которой заключается в следующем.

      Утверждение. Размещение из   n   элементов по   n   элементов является перестановкой из   n   элементов.

Перестановка

Сейчас мы рассмотрим еще одну формулу комбинаторики. В данном разделе статьи мы поговорим о перестановках. Рассмотреть проблему предлагаем сразу же на примере. Возьмем бильярдные шары у нас их n-ое количество. Нам нужно подсчитать: сколько есть вариантов расставить их в ряд, то есть составить упорядоченный набор.

Начнем, если у нас нет шаров, то и вариантов расстановки у нас так же ноль. А если у нас шар один, то и расстановка тоже одна (математически это можно записать следующим образом: Р1 = 1). Два шара можно расставить двумя разными способами: 1,2 и 2,1. Следовательно, Р2 = 2. Три шара можно расставить уже шестью способами (Р3=6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. А если таких шаров не три, а десять или пятнадцать? Перечислять все возможные варианты очень долго, тогда нам на помощь приходит комбинаторика. Формула перестановки поможет нам найти ответ на интересующий нас вопрос. Pn = n *P (n-1). Если попытаться упростить формулу, то получаем: Pn = n* (n — 1) *…* 2 * 1. А это и есть произведение первых натуральных чисел. Такое число называется факториалом, а обозначается как n!

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

Рассмотрим задачу. Вожатый каждое утро выстраивает свой отряд в шеренгу (двадцать человек). В отряде есть три лучших друга – Костя, Саша и Леша. Какова вероятность того, что они будут стоять рядом? Чтобы найти ответ на вопрос, нужно вероятность «хорошего» исхода поделить на общее количество исходов. Общее число перестановок составляет 20! = 2,5 квинтиллиона. Как посчитать количество «хороших» исходов? Предположим, что Костя, Саши и Леша – это один сверхчеловек. Тогда мы имеем всего восемнадцать субъектов. Число перестановок в данном случае равняется 18 = 6,5 квадриллионов. При всем этом, Костя, Саша и Леша могут произвольно перемещаться между собой в своей неделимой тройке, а это еще 3! = 6 вариантов. Значит всего «хороших» расстановок у нас 18! * 3! Нам остается только найти искомую вероятность: (18! * 3!) / 20! Что равняется примерно 0,016. Если перевести в проценты, то это получается всего 1,6%.

Комбинации или сочетание элементов комбинаторики

Определение

Сочетание элементов (комбинации) из

элементов по
(обозначается
) называется то размещение из
элементов по
, которые отличаются хотя бы одним элементом.

Число комбинаций вычисляется по формуле:

(4)

Формулу (4) объясним на таком примере:

Пусть даны 4 элемента

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

Число таких размещений равняется

Таким образом, число всех размещений из

откуда получается формула (4).

Посмотрите пример:

Умножим числитель и знаменатель в формуле (4) на

В итоге получаем:

(5)

По определению принимают

При вычислении числа комбинаций иногда удобно пользоваться соотношением:

(6)

Действительно, если по формуле (5) записать

(7)

Последнее выражение совпадает с правой частью в формуле (5).

Отметим ещё, что числа

(8)

причём согласно с равенством (6) коэффициенты, равноотдалённые от окончания в формуле (8), равные между собой, то есть:

История

Пример звонка изменения (с шестью звонками), один из самых ранних нетривиальных результатов в теории графов .

Основные комбинаторные концепции и результаты перечисления появились во всем античном мире . В VI веке до нашей эры древний индийский врач Сушрута утверждает в « Сушрута-самхите», что можно составить 63 комбинации из 6 различных вкусов, взятых по одному, по два за раз и т. Д., Таким образом вычисляя все 2 6  — 1 возможности. Греческий историк Плутарх обсуждает спор между Хрисиппом (3 век до н.э.) и Гиппархом (2 век до н.э.) относительно довольно деликатной проблемы перечисления, которая, как позже было показано, связана с числами Шредера-Гиппарха . В Стомахионе , Архимед (третий век до н.э.) рассматривает мозаичную головоломку .

В средние века комбинаторика продолжала изучаться, в основном за пределами европейской цивилизации . Индийский математик Махавир (с. 850) , при условии формулы для числа перестановок и комбинаций , и эти формулы могут быть знакомы с индийскими математиками еще в 6 веке н.э.. Философ и астроном Рав Авраам ибн Эзра (с. 1140) установили симметрию биномиальных коэффициентов , в то время как замкнутая формула была получена позднее в талмудиста и математик Леви бен Герсон (более известный как Герсонид), в 1321 арифметической-треугольник в графическая диаграмма, показывающая отношения между биномиальными коэффициентами, была представлена ​​математиками в трактатах, датируемых еще 10 веком, и в конечном итоге стала известна как треугольник Паскаля . Позже, в средневековой Англии , кампанология предоставила примеры того, что сейчас известно как гамильтоновы циклы в некоторых графах Кэли на перестановках.

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

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

Комбинаторные конфигурации

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

Примерами таких моделей служат:

  • размещение;
  • перестановка;
  • сочетание;
  • композиция числа;
  • разбиение числа.

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

А разбиение – это неупорядоченная сумма.

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

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

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

Примеры решения задач с элементами комбинаторики

Пример 1

Задача

Студенты группы изучают 9 дисциплин по 3 пары ежедневно. Сколько существует способов, чтобы распределить пары на один день?

Решение

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

.

Ответ

Существует 504 размещений.

Пример 2

Задача

Автомобильный номер состоит из 5 цифр (из такого набора:

и двух букв. В соединении из букв для номеров автомобилей, какие зарегистрированы в Московской области, на первом месте стоит буква
, а на втором месте одна из букв А, Б. В, И. К, Н. Сколько автомобильных номеров можно составить в области?

Решение

Числовая часть номера – один из размещений из

по
с повторениями. И количество:

Из них необходимо исключить размещение 000-00, так как такой номер не используется, то есть, всех числовых соединений будет:

.

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

.

Ответ

Автомобильных номеров в одной области можно составить по числам – 99 999, а по буквам – 599994.

Пример 3

Задача

Сколько пятизначных телефонных номеров можно составить используя цифры 3, 4, 5, 6, 7 (без повторений)?

Решение

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

.

Ответ

Всего можно составить 120 пятизначных номеров.

Пример 4

Задача

Сколько есть способов, чтобы заполнить карточку спортлото, в которой из 49 чисел необходимо выбрать 6?

Решение

Две заполненные карточки считаются разными, если среди выбранных 6 чисел они отличаются хотя бы одним числом, то есть это будут комбинации, и их количество равняется:

.

Ответ

Количество комбинаций =

Пример 5

Задача

Сколько есть способов, чтобы в данном тайме тренер смог бы выставить на поле 5 баскетболистов, если в команде 10 игроков, причём одного из ведущих игроков тренер планирует задействовать в игре не заменяя на другого игрока весь тайм?

Решение

Так как один из ведущих игроков должен находится на поле в игре весь тайм, тогда менять придётся только 4 игрока из оставшихся 9, то есть у нас получается:

Ответ

Есть 126 способов.

Пример 6

Задача

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

Решение

Всего 8 фигур, причём

,
,
,
,
, тогда:

.

Ответ

На первой горизонтальной шахматной доске с перестановками фигур можно расставить 5 040 раз.

Пример 7

Задача

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

1. В слове “мама”;

2. в слове параллелограмм.

Записать соединения букв.

Решение

1. В слове “мама”

буквы, при этом две буквы “м”, и две буквы “а”. По формуле (9) всех перестановок будет:

.

А сами перестановки будут такими: “мама”, “маам”, амам”, “аамм”, “амма”.

2. В слове “параллелограмм” 12 букв, из них букв “а” – 3, “г” – 1, “е” – 1, “л” – 2, “м” – 1, “о” – 1, “п” – 1, “р” – 2. Всех перестановок будет:

.

Ответ

Всевозможных перестановок будет –

.

Пример 8

Задача

На складе нужно получить 5 однотипных деталей, каждая из которых может быть покрашена в один из трёх цветов: красный, чёрный, зелёный. Сколько имеется способов, чтобы выбрать 5 деталей трёх цветов?

Решение

.

Ответ

Для того, чтобы выбрать 5 деталей 3 цветов, мы нашли 21 способ.

2. Сочетание (или неупорядоченный выбор)

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

2.1 Число сочетаний без возвращения

Итак, вынутые шары не возвращаются назад в урну, а также не фиксируется порядок их номеров в процессе извлечения.

Другими словами, можно представить себе, что все n шаров вынимаются сразу за одно извлечение.

Следовательно, мы имеем дело с выбором произвольного подмножества размера n из множества размера m.

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

Из обсуждения модели известно, что количество последовательных наборов размера n равно (m)n.

Обозначим за x искомое число исходов (подмножеств размера n). Проведенные выше рассуждения показывают, что

n! ∙ x = (m)n

Отсюда получаем искомый ответ:

Если умножить числитель и знаменатель на (m-n)!, получим:

(*)

Выражение (*) называется биномиальным коэффициентом и играет важную роль в теории вероятностей.

Заметьте, что верно тождество

2.1.a. Перестановка из m шаров, неразличимых внутри групп

Допустим,что у нас есть m1 шаров цвета номер 1, m2 шаров цвета номер 2, … mr шаров цвета номер r. Цвета различаются, а шары одного цвета — нет.

Конечно, m1 + m2 +… + mr = m. Сколько существует отличающихся перестановок таких шаров?

Используя рассуждения из для каждой первоначальной перестановки без различения шаров одного цвета в силу основного правила существует

m1! ∙ m2! ∙ … ∙ mr!

новых способов размещения с учетом нумерации.

Рассуждения аналогичные проведенным для модели показывают, что искомое число ненумерованных перестановок равно частному:

Число называется мультиномиальным (или полиномиальным) коэффициентов. Когда r=2, коэффициент сводится к биномиальному.

2.2 Число сочетаний с возвращением

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

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

Литература

К.Л. Чжун, Ф. АитСахлиа. Элементарный курс теории вероятностей. Стохастические процессы и финансовая математика. Перевод с английского М.Б. Лагутина, М.: БИНОМ. Лаборатория знаний, 2007

Решение задачи о суеверном руководителе

Другой способ решения выглядит следующим образом. Исключив 8 из ряда, мы получим, что 0, 1, 2, 3, 4, 5, 6, 7, 9 — данные девять чисел являются допустимыми. После этого следует найти все двузначные номера, которые не содержали бы 8. Делается это просто: нужно взять любое число из допустимых и дописать к нему также любой число из допустимых. Таким образом мы легко получим все двузначные цифры, которые подходят под условие. В итоге получим, что каждый однозначный номер даст 9 разных двузначных. Итоговое число таких цифр будет 9*9 = 92 = 81.

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

Продолжая аналогию, можно заключить, что для получения всех трехзначных цифр без восьмерок, нужно к имеющимся двузначным числам приписать третий разряд, также из допустимых значений. Тогда получим, что число таких цифр будет 92*9 = 9*9*9 = 729. Таким образом мы выяснили, что наш горе руководитель легко сможет обеспечить 600 работников пропусками, номера которых не будут содержать 8. Попробуйте самостоятельное решить задачу для случая с пятизначными номерами.

А что будет, если руководителю не понравится еще и число 2? Получается, тогда количество допустимых чисел будет 8, а именно: 0, 1, 3, 4, 5, 6, 7, 9. Тогда прикинув количество комбинаций чисел без 2 и 8, можно заключить, что их число равно 8*8*8 = 512, а этого явно недостаточно, чтобы обеспечить 600 человек пропусками. Комбинаторика — это наука, помогающая отвечать на подобные вопросы более эффективно, чем это можно сделать методом перебора.

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

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

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

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

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

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

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

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

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

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

Литература

  • Андерсон, Джеймс.  Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М.: «Вильямс», 2006. — С. 960. — ISBN 0-13-086998-8.
  • Ерош И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c.
  • Липский В.  Комбинаторика для программиста. — М.: Мир, 1988. — 213 с.
  • Раизер Г. Дж.  Комбинаторная математика. — пер. с англ. — М., 1966.
  • Рейнгольд Э., Нивергельт Ю., Део Н.  Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980. — 476 с.
  • Риордан Дж.  Введение в комбинаторный анализ. — пер. с англ. — М., 1963.
  • Стенли Р.  Перечислительная комбинаторика = Enumerative Combinatorics. — М.: «Мир», 1990. — С. 440. — ISBN 5-03-001348-2.
  • Стенли Р.  Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции = Enumerative Combinatorics. Volume 2. — М.: «Мир», 2009. — С. 767. — ISBN 978-5-03-003476-8.

Правило умножения

К основным формулам комбинаторики относится и правило умножения. Начнем с теории. Допустим, нам необходимо выполнить несколько действий (а): первое действие выполняется с1 способами, второе – с2 способами, третье – с3 способами и так далее до последнего а-действия, выполняемого са способами. Тогда все эти действия (которых всего у нас а) могут быть выполнены N способами. Как высчитать неизвестную N? В этом нам поможет формула: N = с1 * с2 * с3 *…* са.

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

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

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

Очень часто приходится решать задачи, в которых надо посчитать количество возможных вариантов для той или иной ситуации. Например, сколько позиций может возникнуть на шахматной доске после первого хода обоих игроков? Сколько разных паролей длиною в десять символов можно записать, если ни один символ не использовать дважды? Сколько разнообразных комбинаций чисел может выпасть при игре в лотерею «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

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

Задача о лото

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

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

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

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

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

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

Перестановки из 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. Из трех математиков и десяти экономистов надо составить комиссию,
состоящую из двух математиков и шести экономистов. Сколькими способами это
можно сделать?

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

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

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

Перестановки с повторениями

До этого мы рассматривали случаи, когда все переставляемые объекты были различными. Однако порою некоторые из них не отличаются друг от друга. Пусть на полке надо расставить 3 книги, но две из них одинаковые. Сколько тогда существует перестановок? Общее число перестановок 3 книг составляет 3! = 6:

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

Здесь одинаковые книги отмечены как А и А1. Очевидно, что 1-ый и 2-ой варианты (А1АБ) и (АА1Б) на самом деле не отличаются друг от друга. В них отличается лишь порядок одинаковых книг А и А1. В первом случае за А1 следует А, а во втором, наоборот, за А следует А1. Тоже самое можно сказать про варианты 3 и 4, 5 и 6. Получается, что все возможные перестановки можно разбить на группы, в которых находятся «перестановки-дубликаты»:

А1АБ и АА1Б

А1БА и АБА1

БА1А и БАА1

В каждой группе находится ровно по два «дубликата». Почему именно по два? Это число равно количеству перестановок одинаковых книг. Так как одинаковых томов 2, а Р2 = 2, то в каждой группе по 2 «дубликата». Действительно, если бы мы «убрали» с полки все книги, кроме повторяющихся, то там осталось бы только 2 одинаковых тома, которые можно переставить двумя способами.

Для того чтобы найти количество «оригинальных» перестановок, надо их общее количество поделить на число дубликатов в каждой группе.

6:2 = 3

Пусть теперь надо расставить 4 книги, из которых 3 одинаковы. Обозначим тома как А, А1, А2 и Б. Всего можно записать 4! = 24 перестановки. Однако каждые 6 из них будут дублировать друг друга. То есть их можно разбить на группы, в каждой из которых будет 6 идентичных «дубликатов»:

1-ая группа: БАА1А2, БАА2А1, БА1АА2, БА1А2А, БА2АА1, БА2А1А

2-ая группа: АБА1А2, АБА2А1, А1БАА2, А1БА2А, А2БАА1, А2БА1А

3-ая группа: АА1БА2, АА2БА1, А1АБА2, А1А2БА, А2АБА1, А2А1БА

4-ая группа: АА1А2Б, АА2А1Б, А1АА2Б, А1А2АБ, А2АА1Б, А2А1АБ

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

Р43 = 4!/3! = 24/6 = 4

Для обозначения перестановок с повторениями используется запись

Рn(n1, n2, n3,… nk)

где n – общее количество объектов, а n1, n2, n3,… nk – количество одинаковых элементов. Например, в задаче с 4 книгами мы искали величину Р4(3, 1), потому что всего книг было 4, но они были разбиты на две группы, в одной из которых находилось 3 одинаковых тома (буквы А, А1, А2), а ещё одна книга (Б) составляла вторую группу. Мы заметили, что для вычисления числа перестановок с повторениями надо общее число перестановок делить на количество дублирующих перестановок. Формула в общем случае выглядит так:

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

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

Решение. Вася должен расставить 3 урока испанского и 4 урока английского, тогда n1 = 3, а n2 = 4. Общее количество уроков равно 3 + 4 = 7. Тогда

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

Ответ: 35

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

Пример. У мамы есть 3 яблока, 2 банана и 1 апельсин. Эти фрукты она распределяет между 6 детьми. Сколькими способами она может это сделать, если каждый должен получить по фрукту?

Решение. Всего есть три группы фруктов. В первой находится 3 яблока, поэтому n1 = 3. Во второй группе 2 банана, поэтому n2 = 2. В третьей группе только 1 апельсин, поэтому nk = 1. Общее число фруктов равно 6. Используем формулу:

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

Ответ: 60

В знаменателе формулы для перестановок с повторениями мы записываем число объектов в каждой группе одинаковых предметов. Так, если переставляются 3 яблока, 2 банана и 1 апельсин, то в знаменателе мы пишем 3!•2!•1!. Но что будет, если в каждой группе будет находиться ровно один уникальный объект? Тогда мы запишем в знаменателе произведение единиц:

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

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