Dreamoon and WiFi

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:
rrrll

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 (tabular{000}{00}{R+L R}).

The factorial form is {(R+L)!}/{R! * L!}.

{9!}/{5! * 4!} = 126

Leave a Reply