Символ c метод позволяет нам сделать вывод, что производящая функция для этого комбинаторного класса равна
f(z) = 1/(1 - z - z^2 - z^3)
. На этом этапе мы можем получить ответ посредством расширения степенного ряда. например, см. здесь . Коэффициент на z^21 даст количество возможных игр в «21 спичках» (это может быть 233317).
Оглядываясь назад, предположим, что игрокам было разрешено принять только один матч. Тогда будет только один возможный сценарий. Для каждой длины игры (мощность z) результат игры один:
1/(1 - z) = 1*1 + 1*z + 1*z^2 + 1*z^3 + 1*z^4 + 1*z^5 + ...
Если игрокам разрешено принять один или два матча, у нас есть несколько сценариев ios:
1/(1 - z - z^2) = 1*1 + 1*z + 2*z^2 + 3*z^3 + 5*z^4 + 8*z^5 + ...
Коэффициенты восстанавливают последовательность Фибоначчи и могут интерпретироваться как число целых композиций из n с использованием только чисел 1 и 2.
Разрешение на взятие одного, двух или трех совпадений приводит к следующему расширению,
1/(1 - z - z^2 - z^3) = 1*1 + 1*z + 2*z^2 + 4*z^3 + 7*z^4 + 13*z^5 + ...
, которое можно найти в этой последовательности OEIS , сердечно названной "числами Трибоначи" ".
Можно получить ответ 233317, используя перо, бумагу и смещенное обобщение Pascal треугольника , хотя я бы оставил эту задачу кому-то другому.
Кроме того, я настоятельно рекомендую книгу Филиппа Фололе и Роберта Седжвика "Analyti c Combinatorics" для ознакомления с методом символики c и не только.