我有一个游戏，一名球员 X 想将球传给球员 Y，但他可以与多个球员一起比赛，而其他球员可以将球传给 Y。
我想知道球从 X 到 Y 可以走多少条不同的路径？
例如，如果他与 3 名球员一起比赛，则有 5 条不同的路径，4 名球员有 16 条路径，如果他与 20 名球员一起比赛，则有 330665665962404000 条路径，40 名球员 55447192200369381342665835466328897344361743780 球可以走。最大数量 他可以玩的球员是500人。
我在考虑使用加泰罗尼亚数字？你认为是解决这个问题的正确方法吗？你能给我一些建议吗？
乍一看，我会说，可能路径的数量可以通过以下方式计算（我假设“路径”是玩家序列，没有玩家出现超过一次）。
如果您与n+2玩家一起玩，即玩家 X、玩家 Y 和n路径中可能出现的其他玩家。
然后路径可以包含0, 1, 2, 3, ...n-1或n玩家 X（开始）和玩家 Y（结束）之间的“中间”玩家。
如果您从玩家总数中选择k( ) 个玩家，您可以通过多种方式进行操作。1 <= k <= nn(n choose k)
对于中间玩家的每个子集，都有k!可能的玩家安排。
所以这会产生sum(i=0 to n: (n choose i) * i!)。
为了“更好”的阅读：
---- n / n \ ---- n n! ---- n 1
\ | | \ -------- \ ------
/ | | * i! = / (n-i)! = n! / i!
---- i=0 \ i / ---- i=0 ---- i=0
但我认为这些不是加泰罗尼亚语数字。
这确实是组合学中的问题，而不是算法中的问题。
将玩家 X 到玩家 Y 的不同路径的数量标记为 F(n)，其中 n 是包括 Y 但不包括 X 的玩家数量。现在，有多少不同的路径？球员 X 可以直接将球传给 Y（1 个选项），也可以将球传给其他球员之一（n-1 个选项）。如果 X 传给了另一个玩家，我们可以假装那个玩家是新的 X，场上有 n-1 个玩家（因为“旧”X 不再在游戏中）。这就是为什么 F(n) = 1 + (n-1)F(n-1) 和 F(1) = 1
我很确定你可以从这个得到 phimuemue 的答案。问题是您更喜欢递归解决方案还是求和解决方案。
我对这种搜索有点菜鸟，但快速浏览数字表明你可以修剪、剪掉、过滤掉的越多，你就能越快地做到这一点。你引用的数字很大。
首先想到的是“限制搜索深度是否可行？” 如果您可以将搜索深度限制为 4（任意数字），那么您最坏情况的可能性数量会...
499 * 498 * 497 * 496 = 61,258,725,024 (assuming no one gets the ball twice)
这仍然很大，但详尽的搜索会比您的原始数字集快得多（尽管对于游戏来说仍然太慢）。
我相信在这方面有更多经验的其他人会有更好的建议。不过，我希望这会有所帮助。
如果 X 需要传给 Y，并且中间可能有 P1、P2、...、Pn 球员，而你关心传球的顺序，那么确实
对于 2 个额外的玩家，您有路径：XY、X-P1-Y、X-P2-Y、X-P1-P2-Y、X-P2-P1-Y
这给出了总共 5 条不同的路径，同样对于 3 个额外的玩家，你有 16 条不同的路径
首先尝试将问题简化为已知的问题，为此我将消除 XY，它们对于上述所有内容都是共同的，转化为问题：k 从 0 到 n 的 k 排列之和是多少，其中 n 是数字的P。
这可以给出为
f(n):=sum(n!/(n-i)!,i,0,n);
我可以确认您对 19 和 39（您的符号中的 20 和 40）的发现。
对于 f(499) 我得到
6633351524650661171514504385285373341733228850724648887634920376333901210587244906195903313708894273811624288449277006968181762616943058027258258920058014768423359811679381900054568501151839849768338994244697593758840394106353734267539926205845992860165295957099385939316593862710470512043836452624452665801937754479602741031832540175306674471495745716725509714798824661807396000105338256698426305553340786519843729411660457896089840381658295930455362209587765698327585913037665131195504013431486823990271059962837959407778393078276213331859189770016153265512805722812864376997337140529242894215031131618375899072989922780132488077015246576266246551484603286735418485007674249207286921801779414240854077425752351919182464902664206622037834736215298295580945851569079682952183639701057397376328170754187008425429164206646365285647875545882646729176997107332605851460212415526607757545366695048460341802079614840254694664267117469603856584752270653889630424848913719533359942725361985274851471687885265903663806182184272555073708882789845441094009797907518245726494471433964169680271980763830020431957658400573531564215436064984091520
使用wxMaxima获得的结果
编辑：从问题的评论中得到更多澄清后，我的回答绝对没用:)他肯定想要可能的路线数量，而不是最好的路线！
我的第一个想法是为什么你想知道这些数字？您当然永远不会遍历 500 人可用的所有路径（这将花费太长时间），而且它太大而无法以任何有意义的方式显示在 ui 上。
我假设您将尝试找到球可以采用的最佳路线，在这种情况下，我会考虑研究不关心路线中节点数量的算法。
我会尝试查看A 星算法和Dijkstra 算法。