Line Up!

This is the same as finding the number of lattice paths from $(0,0)$ to $(28,6)$ that stay below and do not cross the line $x = y$ , (although they can touch this line). (By "lattice path" I mean a path that can only go up or to the right, one unit at a time.)

This is equivalent to finding the number of lattice paths from $(1,0)$ to $(29,6)$ that stay strictly below $x = y$ , (i.e., that do not touch this line), in which case the Ballot Theorem applies. With $a = 29, b = 6$ and $k = 1$ we have that the desired value is

$\dfrac{29 - 6}{29 + 6} \dbinom{29 + 6}{29} = \boxed{1066648}$ .

For the general formula where $m \leq n$ , the number of ways that the people can line up is: $\dfrac{n-m+1}{n+1}\dbinom{m+n}{m}$ Can you prove why?

As mentioned in other solutions, we are counting lattice paths from (0,0) to (28,6) stay within the region $x \geq y$ (why?). Instead, we can count the paths that do not stay within the region and subtract from the total. Call these bad paths.

It should be noticed that any bad path must intersect the line (but not necessarily cross) $y = x + 1$ . Suppose for a given bad path, it first hits the line at the point P. Reflect the part of this path from (0,0) to P across the line. We now have a lattice path from (-1,1) to (28,6), and in fact, the bad paths are in bijection to these lattice paths. I will spare the details, but you should convince yourself that it is true.

Now for the calculation, we simply have

$\dbinom{34}{6} - \dbinom{34}{5} = \boxed{1066648}.$