4
$\begingroup$

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:

  1. A 1 must appear
  2. All numbers must be contiguous (adjacent)
  3. 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?

$\endgroup$
  • $\begingroup$ Are things such as 4-way ties legal? $\endgroup$ – Joseph Eck May 21 '18 at 4:09
  • $\begingroup$ Yes. More to the point if ties are allowed, then a tie between all players is fine (if unlikely). Attaching probabilities to all the possible outcomes is another matter of course and some will indeed be very very rare for most games - like an all player tie). $\endgroup$ – Bernd Wechner May 21 '18 at 6:47
3
$\begingroup$

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)$$

$\endgroup$

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.