[Math] Block walking and Pascal’s Triangle

combinatorics

This is quoted text from a math book:

The key to block walking is to imagine taking a walk on Pascal's Triangle. Starting at $0\choose0$, we proceed strictly downward along the lines drawn in the picture of Pascal's triangle above. At each junction, we can choose to go left or right; the element $n\choose k$ is attained after $n$ downward moves by $k$ right decisions and $n-k$ left decisions. The key questions is, in how many ways can we walk to the position $n\choose k$? Since we needs to choose $k$ right decisions out of $n$ total decisions, we can do it in $n\choose k$ ways!

I don't understand how you can reach the point $n \choose k$ in Pascal's Triangle in $n \choose k$ ways? Could someone please explain this to me. I understand that to reach the point you have to take $k$ right decisions and $n-k$ left decisions, but I don't know where to go on from there.

Best Answer

For example, to reach $\binom 3 2$ you need $2$ right (R) turns and $1$ left (L) turn. There are multiple paths that make these turns: RRL, RLR, LRR. This is the number of ways to pick $2$ places for Rs in a string of $3$ symbols.

Related Question