0
$\begingroup$

In William Feller's probability book (the first of the two part series), the following example is given (page 36)

The number of shortest polygonal paths (with horizontal and vertical segments) joining two diagonally opposite vertices of a chessboard equals $\binom{16}{8} = 12,870$.

No further explanation was given, and I wanted to justify this, but I came to a different conclusion. My thoughts are as follows: starting from the lower left square, any valid path to the upper right square can be described by a string describing $7$ right moves (say R) and $7$ up moves (say U). There is a bijection between these strings and valid paths. The amount of such strings is equal to the amount of unordered collections of $7$ out of $14$ digits, since any such string can be described completely by the positions of the U's (or, same thing, the R's) in the string. This gives me the result $\binom{14}{7} = 3,432$. Is my approach correct?

$\endgroup$
1
$\begingroup$

Since you are going from corner to corner and therefore from vertex to vertex, the number of steps in each direction is $8$ rather than $7$ and you get the advertised answer by your method.

$\endgroup$
  • $\begingroup$ I interpreted it as the paths being the squares themselves, not on their edges; thank you for your answer. $\endgroup$ – Steven Wagter May 29 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.