Hard Probability Puzzle

#171

There was a race going on between 8 persons. In how many ways, counting the ties, they can reach the destination i.e. finishing line ?
For example : Two persons, A and B, can reach the destination in 3 ways.
A wins, B wins or a Tie.

  Difficulty Level - 5/5

  Update Your Answers : Click Here

  Solution : 

  545835.
It's the same as putting 8 labelled balls into k labelled boxes so that no box is empty, and summing for k = 1... 8.
For each k(places) you can find the total by starting with k^8 (choose a box for each ball), then eliminating the cases where a box is empty using inclusion exclusion.
k=1: 1
k=2: 2^8 - 2
k=3, 3^8 - 3*2^8 + 3
k=4, 4^8 - 4*3^8 + 6*2^8 - 4
k=5, 5^8 - 5*4^8 + 10*3^8 - 10*2^8 + 5
k=6, 6^8 - 6*5^8 + 15*4^8 - 20*3^8 + 15*2^8 - 6
k=7, 7^8 - 7*6^8 + 21*5^8 - 35*4^8 + 35*3^8 - 21*2^8 + 7 = 7! * C(8,2)
k=8, 8!
It adds to 545835.
{ k=1 means everybody is tied; k=4 means there are 4 different places (1st place through 4th place), so many people are tied etc.}