Counting up-down walks to a target

EasyCombinatorics~3m

A sequence starts at $x_0 = 0$ , and each step changes the value by exactly $\pm 1$ : $|x_i - x_{i-1}| = 1$ for $i = 1, \dots, 10$ . How many such sequences of $10$ steps end at $x_{10} = 4$ ?

Show hints (2)+

Let $u$ steps be $+1$ and $d$ steps be $-1$ . Set up $u+d=10$ and $u-d=4$ .
Once $u=7$ , $d=3$ are fixed, the sequence is just a choice of which steps are down: $\binom{10}{3}$ .

Answer

Reveal answer →

120

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Practise free Unlock solutions

Asked at: Jane Street, SIG

Counting up-down walks to a target

Answer

Related questions