Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

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

2 Чтобы произвести подобные вычисления, в математике используют перечислительную комбинаторику.

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

4 <h2>Что такое перечислительная комбинаторика</h2>

5 Это ветвь комбинаторики, которой человечество пользуется уже очень давно. Она помогает ответить на один из базовых вопросов: "Сколько возможно вариантов?".

6 Перечислительная комбинаторика помогает узнать, сколько существует вариантов - то есть разных структур заданного размера. Например, можно выяснить, сколько существует вариантов:

7 <ul><li>Расстановки 100 книг на полке</li>

8 <li>Размещения 40 гостей в зале</li>

9 <li>Последовательности 10 уроков в курсе по математике</li>

10 </ul>В перечислительной комбинаторике есть несколько вариантов подсчета - среди них нет единственного верного способа. Правильным способом подсчета будет тот, который подходит под конкретную задачу. Поэтому можно использовать разные подходы, которые мы рассмотрим далее.

11 <h2>Два способа подсчета</h2>

12 Возьмем такой пример:

13 Нужно узнать, сколько существует способов записать (n - 1) в виде упорядоченной суммы 1 и 2

14 Разберем условие задачи на основные составляющие и определим, как ее решить:

15 <ul><li>Есть множество объектов - это упорядоченные суммы 1 и 2</li>

16 <li>Это множество объектов параметризуется целым числом n - всего n - 1</li>

17 <li>Нужно найти функцию f:N → N, при которой f(n) будет верным для всех n</li>

18 </ul>Для ответа на вопрос мы собрали первые несколько значений f(n) в таблице:

19 С помощью этих данных разберем два способа подсчета в перечислительной комбинаторике:

20 <ul><li>Рекуррентные отношения</li>

21 <li>Замкнутая формула</li>

22 </ul>Рассмотрим их подробнее.

23 <h3>Рекуррентные отношения</h3>

24 Для начала найдемрекуррентное соотношениедля ответа - это уравнение, в котором следующий член вычисляется как функция предыдущих членов.

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

26 Один из самых наглядных примеров рекуррентных соотношений - это ряд Фибоначчи:

27 F(n) = F(n - 1) + F(n - 2)

28 Вернемся к примеру выше. Возьмем упорядоченные суммы и разделим их на два случая:

29 <ol><li>Суммы, у которых последний член - 1</li>

30 <li>Суммы, у которых последний член - 2</li>

31 </ol>Далее найдем различные суммы в обоих случаях:

32 <ol><li>Есть f(n) различных сумм. Они равны n - 1 с единицей, добавленной в конце каждой суммы</li>

33 <li>Есть f(n - 1) различных сумм</li>

34 </ol>В итоге мы находим:

35 f(n + 1) = f(n) + f(n - 1)

36 Вместе с начальными значениями f(0) = 0 и f(1) = 1 последовательность однозначно определена - то есть имеет единственное решение.

37 Теперь у нас есть такое уравнение:

38 (f(n + 1) = f(n) + f(n - 1))

39 Это значит, что у нас есть более простой способ вычислить f(n) с помощью примерно n сложений.

40 Нам больше не нужно записывать все вычисления из таблицы выше. Теперь необходимо только f(n) - числа из последнего столбца. Чтобы вычислить последующие строки, нужно помнить только две предыдущие.

41 Рекуррентное соотношение дает алгоритм. Он помогает найти такую функцию f : N → N, при которой f(n) будет правильным ответом для всех n.

42 Продолжим подсчеты с помощью еще одного способа - замкнутой формулы.

43 <h3>Замкнутая формула</h3>

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

45 Рассмотрим следующие функции, каждая из которых - ответ на комбинаторную задачу подсчета:

46 f1(n) = n^n - 2 f2(n) = n! * Σ[k=0 to n] ((-1)^k) / k! f3(n) ≈ ближайшее целое число к (n! / e) f4(n) = (1 / √5) * ( (9 * τ^n)_1 - (τ^n)_2 )

47 Разберем каждую функцию подробнее.

48 <ul><li>Функция типа f1 - вполне удовлетворительный ответ, потому что у членов сумм есть комбинаторный смысл - они соответствуют определенным частичным графам. Но есть одна сложность - немногие задачи допускают такие решения. Часто нам нужны суммы в ответе, например, как в f2</li>

49 <li>f2 - это не замкнутая формула. Но это удовлетворительный ответ, потому что проще вычислить f2, чем перечислять все объекты, которые она учитывает</li>

50 <li>Формулы f3 и f4 - не комбинаторные, так как в них участвуют нерациональные члены. При этом такие формулы все равно могут быть содержательными, и у них менее загроможденный вид - например: f2 = f3</li>

51 </ul><h2>Выводы</h2>

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

53 <ul><li>На подсчеты вариантов могут накладываться определенные ограничения - например, различимость, повторения одинаковых элементов</li>

54 <li>Решать такие задачи можно двумя способами: с помощью рекуррентных отношений и замкнутой формулы. Единственно верного способа нет, поэтому нужно выбирать способ под конкретную задачу</li>

55 </ul>