This is an interesting problem that I have no easy solution for, but an inkling that there may be one!
Consider an $n$ player game. If we disallow draws, we know that the number of permutations of $n$ players in that $n$ player game will be $n!$.
That's the easy problem. But now let us permit and consider the possibility of draws. What then?
I model this tentatively in my own mind as a roll of $n$ $n$-sided dice. For for a four player game 4 dice with 4 sides each (d4 in gamers' parlance). Now that would appear to present $n^n$ permutations. And that seems a good starting point, albeit overestimating the number of rankings considerably because ...
... from a ranking perspective a load of these are invalid or identical depending on how we choose to classify it. But let's consider that to limit the results to valid rankings:
- A 1 must appear
- All numbers must be contiguous (adjacent)
- All numbers must be ascending (order is relevant)
We might address the first issue by pinning one outcome to 1, and so only rolling 3 4-sided dice for the remaining 3 players (or $n-1$ $n$-sided dice for the remaining $n-1$ players). Which presents 1/4 as may permutations or a total of $n^{n-1}$ permutations generally.
Now from the results we want to exclude all those that have gaps, are not contiguous. On that I am stuck. How to enumerate those if possible.
To clarify, this is an illegal ranking we wish not to count (4 player game):
1334
only because it is double counting:
1223
And we also want to enforce ascending order so that these are excluded:
3314
4331
again, only because they double count:
1223
(which is a winner, a tie for second place and someone in 3rd place).
which is the same ranking. I figure the best way to avoid this kind of double counting is to demand this ascending contiguity of ranks.
How many illegal results then are there in the sample space of $n^{n-1}$ rolls of the $n$-sided die? Or is there a better way to model it?
This is OEIS A000670, which starts $$1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, 1622632573, 28091567595, 526858348381, 10641342970443, 230283190977853, 5315654681981355, 130370767029135901, 3385534663256845323, 92801587319328411133, 2677687796244384203115$$ with a number of formulas and references given. One of them is $$a(n) = \sum_{k=1}^n k! StirlingS2(n, k)$$