Часто нам нужно посчитать количество объектов, комбинаций или вариантов чего-либо. Например, мы хотим понять, как рассадить гостей на конференции. Для этого мы будем перебирать различные варианты рассадки, чтобы выбрать лучший.
Чтобы произвести подобные вычисления, в математике используют перечислительную комбинаторику.
В этом уроке мы разберем, что такое перечислительная комбинаторика, и как с ее помощью можно посчитать количество комбинаций из нескольких элементов.
Что такое перечислительная комбинаторика
Это ветвь комбинаторики, которой человечество пользуется уже очень давно. Она помогает ответить на один из базовых вопросов: «Сколько возможно вариантов?».
Перечислительная комбинаторика помогает узнать, сколько существует вариантов — то есть разных структур заданного размера. Например, можно выяснить, сколько существует вариантов:
-
Расстановки 100 книг на полке
-
Размещения 40 гостей в зале
-
Последовательности 10 уроков в курсе по математике
В перечислительной комбинаторике есть несколько вариантов подсчета — среди них нет единственного верного способа. Правильным способом подсчета будет тот, который подходит под конкретную задачу. Поэтому можно использовать разные подходы, которые мы рассмотрим далее.
Два способа подсчета
Возьмем такой пример:
Нужно узнать, сколько существует способов записать в виде упорядоченной суммы и
Разберем условие задачи на основные составляющие и определим, как ее решить:
-
Есть множество объектов — это упорядоченные суммы и
-
Это множество объектов параметризуется целым числом — всего
-
Нужно найти функцию , при которой будет верным для всех
Для ответа на вопрос мы собрали первые несколько значений в таблице:
Значение |
Значение |
Варианты подсчета |
Количество вариантов — |
|
--- |
Вариантов нет |
|
|
|
• |
|
|
|
• |
|
|
|
•
|
|
|
|
•
|
|
|
|
•
|
|
С помощью этих данных разберем два способа подсчета в перечислительной комбинаторике:
-
Рекуррентные отношения
-
Замкнутая формула
Рассмотрим их подробнее.
Рекуррентные отношения
Для начала найдем рекуррентное соотношение для ответа — это уравнение, в котором следующий член вычисляется как функция предыдущих членов.
Как видите, это рекурсия — такое уравнение может продолжаться бесконечно, постоянно по кругу обращаясь к результатам предыдущих вычислений.
Один из самых наглядных примеров рекуррентных соотношений — это ряд Фибоначчи:
Вернемся к примеру выше. Возьмем упорядоченные суммы и разделим их на два случая:
-
Суммы, у которых последний член —
-
Суммы, у которых последний член —
Далее найдем различные суммы в обоих случаях:
-
Есть различных сумм. Они равны с единицей, добавленной в конце каждой суммы
-
Есть различных сумм
В итоге мы находим:
Вместе с начальными значениями и последовательность однозначно определена — то есть имеет единственное решение.
Теперь у нас есть такое уравнение:
Это значит, что у нас есть более простой способ вычислить с помощью примерно сложений.
Нам больше не нужно записывать все вычисления из таблицы выше. Теперь необходимо только — числа из последнего столбца. Чтобы вычислить последующие строки, нужно помнить только две предыдущие.
Рекуррентное соотношение дает алгоритм. Он помогает найти такую функцию , при которой будет правильным ответом для всех .
Продолжим подсчеты с помощью еще одного способа — замкнутой формулы.
Замкнутая формула
Это математическое выражение, которое можно получить с помощью комбинации чисел или функций и ссылки на операции. Решения, которые дают удовлетворительный ответ, называются решениями в замкнутой формуле.
Рассмотрим следующие функции, каждая из которых — ответ на комбинаторную задачу подсчета:
-
-
-
ближайшее целое число к
-
Разберем каждую функцию подробнее.
-
Функция типа — вполне удовлетворительный ответ, потому что у членов сумм есть комбинаторный смысл — они соответствуют определенным частичным графам. Но есть одна сложность — немногие задачи допускают такие решения. Часто нам нужны суммы в ответе, например, как в
-
— это не замкнутая формула. Но это удовлетворительный ответ, потому что проще вычислить , чем перечислять все объекты, которые она учитывает
-
Формулы и — не комбинаторные, так как в них участвуют нерациональные члены. При этом такие формулы все равно могут быть содержательными, и у них менее загроможденный вид — например:
Выводы
В этом уроке мы познакомились с перечислительной комбинаторикой и узнали, как она помогает подсчитать количество способов построения и перебора элементов. В работе с ней есть несколько особенностей:
-
На подсчеты вариантов могут накладываться определенные ограничения — например, различимость, повторения одинаковых элементов
-
Решать такие задачи можно двумя способами: с помощью рекуррентных отношений и замкнутой формулы. Единственно верного способа нет, поэтому нужно выбирать способ под конкретную задачу
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
