Horse race combinations when ties are allowed How many ways are there for N=4 horses to finish if ties are allowed?
Note that order does matter!
One of my friends solved this problem in the following way and he told answer for N=5 will be 541.
He also showed his solution process for N=4 like the following and asked me to find out the answer for N=5 as he solved but I can not do it. Please someone help me. My friend's solution process is here for N=4:
Solution by cases:
1.No ties:
The number of permutations is P(4,4) = 4! = 24
2.Two horses tie:
There are C(4,2) = 6 ways to choose the two horses that tie
  There are P(3,3) = 6 ways for the “groups” to finish
  A “group” is either a single horse or the two tying horses
  By the product rule, there are 6*6 = 36 possibilities for this case
3.Two groups of two horses tie
There are C(4,2) = 6 ways to choose the two winning horses
  The other two horses tie for second place
4.Three horses tie with each other:
There are C(4,3) = 4 ways to choose the two horses  that tie
   There are P(2,2) = 2 ways for the “groups” to finish
   By the product rule, there are 4*2 = 8 possibilities for this case
5.All four horses tie:
There is only one combination for this
  By the sum rule, the total is 24+36+6+8+1 = 75 
My question is that what the solution approach for N=5 is? 
 A: The answers for 0, 1, 2, 3, or 4 horses are 1, 1, 3, 13, and 75.
Now suppose there are five horses. If just one horse is in first place, there are $\tbinom51$ ways to choose that horse, and $75$ ways to order the remaining four horses. If there are two horses in first place, there are $\tbinom52$ ways to choose them, and $13$ ways to order the rest. And so on. Thus the answer is $$\binom51\cdot75+\binom52\cdot13+\binom53\cdot3+\binom54\cdot1+\binom55\cdot1=541$$
The answer for six horses can be computed similarly, using all the previous answers. This creates a sequence known as the Fubini numbers, or ordered Bell numbers.
A: I'd sort the cases according to the number $g$ of "groups" finishing at equal times and encode the possible sizes of the $g$ groups as $g$-tuples:
$$\eqalign{g=1:\quad&(5)\cr
g=2:\quad&(4,1), \ (3,2)\cr
g=3:\quad&(3,1,1), \ (2,2,1)\cr
g=4:\quad&(2,1,1,1)\cr
g=5:\quad&(1,1,1,1,1)\cr}$$
What we see here is just a list of the partitions of $5$. For each $g$-tuple we have to compute in how many ways the individual horses can be distributed into groups of the respective sizes, and then we have to multiply by $g!$ to take care of the order in  which the groups appear in the final race sheet. 
Take as an example the code $(3,2)$: Here we can choose the two horses that tie in ${5\choose 2}$ ways. Similarly the code $(2,2,1)$: Here we can choose the single horse in $5$ ways and can pair off the four remaining horses in three ways. Etcetera.
In this way we obtain the following total number of outcomes for $5$ horses:
$$1+\left({5\choose1}+{5\choose2}\right)\cdot 2!+\left({5\choose3}+5 \cdot3\right)\cdot 3!+{5\choose2}\cdot4!+5!=541\ .$$
