令 x_0 = 0 并令 x_1, x_2, ..., x_10 遵循规则 |x_i - x_{i-1}| = 1 换 1 <= i <= 10. If x_10 = 4, how many possible sequences are there?

Question

在每个节点，我们必须向上或向下 1。几个可能的序列是

0,1,2,3,2,3,2,3,2,3,4 或 0,-1,-2,1,2,3,4,5,4,3,4

我在QuantGuide上看到这个问题

我遇到了这个问题，不知道如何解决。我此时的想法是，在每个节点你有两种可能的选择，向上 1 或向下 1。如果没有最终约束，答案将只是 2^10，但最终约束 x_10 = 4 让我困惑离开。我通过在 Python 中通过查找以 4 终止的无约束序列的百分比找到了解决方案，但我觉得必须有一个更简洁的解决方案。

问题的答案是 120 个可能的序列，这有帮助。

Answer 1

评论的粗暴实现

为了用代码解决这个问题，你可能可以通过一种方式来暴力破解：当你离目标太远，并且给定尝试中的剩余 k 步根本无法让你返回时，你可以放弃该尝试早（而不是检查 2^k 次，是的，结果不是 4）。

start=0
stop=4
size=11 # includes the starting element
results=0

def check(candidate):
  global stop,results
  if len(candidate) == size:  # just safety, the two "if"-s could be an "and"
    if candidate[-1] == stop: # found a solution, happy
      print(candidate)
      results+=1
    return
  if abs(candidate[-1] - stop) > size - len(candidate): # the "shortcut"
    return
  check(candidate + [candidate[-1] + 1])
  check(candidate + [candidate[-1] - 1])

check([start])
print(results)

它产生

120

作为结果（也打印实际序列）。

当然，数学部分也表明，从评论中重复：

重复排列：对于 0->4 的情况，你有 7 个上升和 3 个下降，10!/(7!*3!)=120。