This post is in reference to CodeForces

Dreamoon and WiFi.

We must move to a given position in the given number of moves; each move is either to the left or right. *How many distinct paths are there?*

E.g. We must move one to the right in 9 moves. One path is shown here:

So, to move over one spot in 9 moves requires 5 right (RRRRR) and 4 left (LLLL). The question simplifies down to the following:

*How many different strings can be made by rearranging RRRRRLLLL?*

This simplifies even further to this: How many different ways can we assign 5 R’s to 9 spots? Since once the R’s are given, the L’s positions are known — the places remaining. And we can go from the other way: How many ways can we assign 4 L’s to 9 spots? It’s the same thing, again because assigning L’s *is * assigning R’s.

The solution is found using the binomial coefficient function .

The factorial form is .

*Related*