Suppose there are 10 individuals competing in a race. If all 10 finish the race, how many distinguishable final rankings are possible (including ties)?
Follow up: What would be the answer if we allow for the possibility that some or all of the competitors do not finish the race?
With no ties we have 3,628,800 permutations (10!).
With one tie (between two racers only) we have 16,329,600 positions. That is (ways of choosing a pair) * (ways of arranging the remaining racers) * (number of positions the tie can be in). That is 9*45*40320.
With one three-way tie we have 8*120*5040 that is 4,838,400.
With one four-way tie we have 7*210*720 that is 1,058,400.
And so it continues.
With two two person ties we have (ways of choosing a pair) * (ways of choosing a pair from the remaining racers) * (number of positions the first pair can be in) * (number of positions the second pair can be in) *(ways of arranging the remaining racers). That is 45*28*8*7*720. That's 50,803,200.
I could continue this but it's obvious that this isn't the method that the problem is looking for (far too much legwork).
Originally posted by XanthosNZThe problem (and especially the follow-up) will be way too much legwork unless you can come up with a suitable recurrence relation to facilitate the calculations. I'll give hints later on if nobody comes up with the solution.
With no ties we have 3,628,800 permutations (10!).
With one tie (between two racers only) we have 16,329,600 positions. That is (ways of choosing a pair) * (ways of arranging the remaining racers) * (number of positions the tie can be in). That is 9*45*40320.
With one three-way tie we have 8*120*5040 that is 4,838,400.
With one four-way tie we ha ...[text shortened]... 's obvious that this isn't the method that the problem is looking for (far too much legwork).