Number of valid ways to roll M dice with N sides

[Hiero]

Homework Statement

Suppose we have M dice each with N sides. The dice are ordered, so that rolling (1, 2, ...) is not the same as (2, 1, ...)

A valid configuration is one for which each number rolled is at least as large as the previous. (For instance, take M=N=2. (1,1) is valid, (1,2) is valid, (2,2) is valid, but (2,1) is not valid.)

How many configurations are valid?

Homework Equations

The answer is (M+N-1) choose (M)

The Attempt at a Solution

I can only see a kind of recursive approach, something like:

1 + M + Σn [from n=1 to M] + ΣΣ(...) + ΣΣΣ(...) + ...
(it’s a finite sum)

I haven’t explained it but it works for N = 3 (where only those first three terms exist) but obviously this is not the approach for general N.

Whenever the answer involves the choose function there’s usually an elegant way of viewing things, but I just can’t see the elegant approach.

 

[RPinPA]

Yes, a recursive approach makes sense. In order to have a valid roll of M dice, first you need a valid roll of M-1 dice, then the next die has to be at least as high as the last one.

Can you show what you've done for N = 3 and why you can't generalize it?

 

[r0bHadz]

You need to break it down into cases, and then break those into sub cases

case 1: the first die value is 1

case 2: the first die value is 2
...
case n: the first die value is n

find out how many sub cases are in case 1, then go on to generalize.

There may be a more elegant approach though.

 

[Hiero]

Can you show what you've done for N = 3 and why you can't generalize it?

It’s not that I can’t generalize it, it’s that I can’t simplify the generalized form.

You need to break it down into cases, and then break those into sub cases

case 1: the first die value is 1

case 2: the first die value is 2
...
case n: the first die value is n

find out how many sub cases are in case 1, then go on to generalize.

That was indeed my approach, but we should go in the reverse order. Warning... it’s about to get ugly... but y’all asked for it!

If the first die is N, then all die must be N and so this gives 1 way.

If the first die is N-1, then we have M-1 spots that we could put an N (then the rest must be N as said above) or we could have none be N, so this gives M ways.

If the first die is N-2; one way is for all dice to be N-2; or we could put N-1 in the n^th spot (n ∈ {2,3,...M}) which would reduce the problem to the previous case except with M’ = M+1-n, and each of these (from previous reasoning) gives M’ ways; or we could have no (N-1)’s and put an N is any of the M-1 spots.
So for this case we get 1 + ΣM’ + (M-1) but we can see M’ ∈ {1,2,...,M-1} so (if we add the 1+(M-1) = M on to the end of the sum) we get a final answer (for this particular case) of:
_{k=1 to M}∑k ways (which can be written as M(M+1)/2 ways)

I’ll be honest, I haven’t properly reasoned it out beyond this (it’s getting messy) but if we follow the pattern then it seems the number of ways for when the first die is 1 would be ΣΣ(...)ΣΣ1 where there are N-1 nested sums all starting from 1 and going up to some variable which is the variable of the next sum, with the left most upper bound being M.

If the pattern is correct and continues then our final answer would be:
1 + Σ1 + ΣΣ1 + ΣΣΣ1 + ... + ΣΣ(...)ΣΣ1
Where there are N terms and the nested sums are as described above.

This gives the same answer as the choose function for N = {1,2,3} (I should check N = 4 but I’m lazy) but there’s no way that I know of to simplify a general number of ‘interlocked’ summations. (And even if we could, we would still need to show that the N terms add up to the choose function...)

So this method of brute force counting doesn’t seem fruitful. There has to be another way

 

[RPinPA]

I'm going to change notation here slightly and use lower case $m$ and $n$ for number of dice and number of faces, respectively. Let's define $N(m,k)$ as the number of ways to roll a valid roll such that the last die is $k$, and n $R(m,n)$ as the number of valid rolls with $m$ $n$-sided dice. Clearly $R(m,n) = \sum_{k=1}^n N(m,k)$.

(I think this is what you're doing but the notation is confusing me a little).

Suppose $m = 1$. Then $N(1,k) = 1$ because there's only one way to roll a single die with a value of $k$. And clearly $R(1,n) = n$.

Now, let's think about the recursion. In order to have a valid roll of $m$ dice, as I said we need to have a valid roll of $m-1$ dice followed by a roll which is at least as large as the last roll. So that gives us the recursion $R(m,n) = \sum_{k=1}^n N(m-1,k) (n-k+1)$

OK and $N(m,k) = R(m-1,k)$ because a valid roll that ends in a $k$ consists of $m-1$ rolls that end in anything $\leq k$, followed by a $k$.

I'm thinking out loud here, so I apologize if the flow is a little erratic. I don't think that recursion above helps actually. Instead I'll use the result I just stated to write a different recursion:
$R(m,n) = \sum_{k=1}^n N(m,k) = \sum_{k=1}^n R(m-1,k)$. Is that really valid? Yes, I think so. I've gone over the logic a couple of times and it seems sound.

So where does that lead us? Well, let's see (disclaimer again: I have no idea if this is a profitable path, I'm just seeing what happens).
$R(1,n) = n$
$R(2,n) = \sum_{k=1}^n R(1,k) = \sum_{k=1}^n k = n(n+1)/2 = \binom {n+1} 2$
$R(3,n) = \sum_{k=1}^n \binom {k+1} 2 = \sum_{k=2}^{n+1} \binom k 2$

Hmm. I think I'm on the verge of a counting argument here but I don't know what it is. How would you argue that last thing is equivalent to $\binom {n+2} {3}$, if it is? And then what's the general counting argument? I need to think about this some more, but at least I got your summations down to a single sum :-)

Wolfram Alpha says that last sum does indeed yield $\binom {n+2}{3}$: https://www.wolframalpha.com/input/?i=sum(k=2,n+1)+C(k,2)

 

[Hiero]

@RPinPA

Appreciate you tackling this problem. Your counting approach is distinctly different from my counting approach (I don’t build up from one die, I just count the cases based on what the first die shows).

I am pleased to say I have realized the elegant perspective. It is the classic “stars and bars” perspective from combinatorics. We take M stars representing the M dice and N-1 bars, which gives N ‘sections’ representing the N faces of the dice. There is a one to one correspondence between the orderings of the stars and bars and the valid solutions to the problem.

For instance, if N = M = 2, we get the correspondence:
**| = (1,1)
*|* = (1,2)
|** = (2,2)
Which gives the three valid solutions.

In general there are (M + N - 1) choose (M) ways to order the stars and bars, which was the solution to the problem.

I am pretty damn sure I wouldn’t realize this correspondence if it wasn’t for the fact that I knew the form of the answer... but there it is!

 

[RPinPA]

I am pleased to say I have realized the elegant perspective. It is the classic “stars and bars” perspective from combinatorics.

That crossed my mind but I couldn't make the connection. I still can't. Congratulations on seeing this elegant approach, but can you explain the encoding? Why is *|* read as (1, 2) for instance?

 

[Hiero]

That crossed my mind but I couldn't make the connection. I still can't. Congratulations on seeing this elegant approach, but can you explain the encoding? Why is *|* read as (1, 2) for instance?

All the stars in the first section (left of all the bars) represent dice that rolled a 1, all the stars in the second section (left of all but one bar) are a dice with a 2, etc. The stars read from left to right give the ordered states of the dice. This only works because all the 1s must be left of all the 2s, etc.

Any valid ordering can be converted to this scheme.
If we roll all 1s it looks like ***(...)***|||(...)|||
If we roll all Ns it looks like |||(...)|||***(...)***,
If we roll a 2 then all Ns it’s |*||(...)|||***(...)***

It looks kinda messy with the ellipsis, maybe it will be more clear if I show N = 3, M = 2;
**|| = (1,1)
|**| = (2,2)
||** = (3,3)
*|*| = (1,2)
|*|* = (2,3)
*||* = (1,3)
Which are the 4choose2 = 6 valid rolls.

Sorry for the poor explanations. I certainly haven’t proved the one to one correspondence, I’ve merely seen it.

 

[RPinPA]

Sweet! A really pretty combinatorial argument.

The proof is not that hard.

First, every valid roll results in a stars-and-bars representation with exactly M stars and N-1 bars. I'll prove that algorithmically.
Suppose we have a valid roll $(r_1, r_2, ..., r_M)$. Define $r_0 = 1$ and $r_{M+1} = N$. Then $\sum_{k=1}^{M+1} (r_k - r_{k-1}) = N-1$ because the sum is $(r_1 - r_0) + (r_2 - r_1) + ... + (r_{M+1} - r_M)$ which telescopes to $r_{M+1} - r_0 = N-1$.

Algorithm: For $k=1 \text{ to } M+1$
i. Output $(r_k - r_{k-1})$ bars.
ii. If $k \leq M$ output one star.

Step i, by the argument above, results in N-1 bars. Step ii, which executes M times, results in M stars. Thus we have some arrangement of M stars and N-1 bars for any valid roll.

Next, any such arrangement results in a valid roll. Let $(s_1, s_2, ... s_{M + N-1})$ be a string containing M stars and N-1 bars in any order.
Algorithm:
Let $p=1$
For $k=1 \text{ to } M+N-1$
i. If $s_k$ = '|' set $p = p + 1$.
ii. else output the value of $p$

Step i executes exactly $N-1$ times, once for each bar. Therefore $p$ is incremented $N-1$ times, resulting in a final value of $N$.
Step ii will execute exactly $M$ times, resulting in M numbers being output. No number will be less than the previous number since $p$ never decreases. And no number will be higher than $N$ since that is the maximum value of $p$. Thus the output is a sequence of numbers which is a valid roll.