我确信每个人都熟悉著名的21个火柴比赛，每个人参加1,2或3场比赛，最后一个参加比赛的人输了。
让我们简化游戏，并假设只能进行1或2场比赛。我的问题是，可以玩几局？
我知道这很容易递归解决，但是，我试图提出一种组合解决方案。
[举例来说，我们将21场比赛减少到4场。可能的游戏数量为5。{'MCM'，'MMMM'，'CC'，'CMM'，'MMC'}。其中C代表删除2个匹配项，M代表删除单个匹配项。
Symbolic method允许我们推断此组合类的生成函数为
f(z) = 1/(1 - z - z^2 - z^3)
至此，我们可以通过幂级数展开获得答案，例如参见here。 z^21上的系数将给出“ 21个火柴”中可能的游戏数量（可能是233317）。
回想一下，假设球员只允许参加一场比赛。然后，将只有一种可能的情况。对于每个游戏长度（z的幂），只有一个游戏结果：
1/(1 - z) = 1*1 + 1*z + 1*z^2 + 1*z^3 + 1*z^4 + 1*z^5 + ...
如果允许玩家参加一两场比赛，我们有多种情况：
1/(1 - z - z^2) = 1*1 + 1*z + 2*z^2 + 3*z^3 + 5*z^4 + 8*z^5 + ...
系数恢复Fibonacci sequence，并且仅使用数字compositions和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 + ...
可以在this OEIS sequence中找到，并亲切地称为“ Tribonacci数字”。
虽然可以将任务留给其他人，但是可以使用笔，纸和233317的一般化来得出Pascal triangle的答案。
顺便说一句，我强烈推荐Philippe Flajolet和Robert Sedgewick所著的“ Analytic Combinatorics”一书，介绍了符号方法及其以后的内容。