# Question about an 8 sided die

I have a question about an 8 sided die problem. I will put up my work what I have if someone can tell me how to proceed I will appreciate it.

We roll an 8 sided die numbered 1 to 8 six times and record the result of the face value that pops up on top as $x_{1}, x_{2} , x_{3}, x_{4}, x_{5}, x_{6}$.

We must now find the total number of ways that $x_{1} \ge x_{2} \cdots x_{5} \ge x_{6}$.

My progress:

If we had $6$ numbers then there will be exactly one way to arrange it such that they are going from increasing to decreasing.

Like what I mean is if the numbers that showed up were 1 through 6 then there are 720 orientations of these numbers but only one orientation will put them in increasing order.

So I thought it would be $8^6/6!$ since for every 720 combinations one puts them in increasing order, but that does not even turn out to be an integer so I am not sure what I am doing wrong.

-
If you have $1,1,1,1,1,8$ then $120$ of the permutations satisfy the requirement rather than the one you assume. –  Henry Dec 11 '12 at 21:41
Not sure why the dice matters here. From what you've stated, it seems like you want to count the number of feasible orderings of 6 numbers drawn from 1 to 8 with repetition that can be arranged in increasing order. This is simply a combinatorial question. Do you then want to ask the further question, what is the probability that six successive drawings will give you a feasible sequence? –  Assad Ebrahim Dec 11 '12 at 22:07
My question is that if you roll the die 6 times you will get 6 numbers. in how many of the total possible 6 number combinations is the restraint that i gave true. –  Eric Chen Dec 11 '12 at 22:11

This is the number of ways to distribute six balls over eight bins numbered $1$ to $8$. (Each ball represents an occurrence of the bin's number in an ordered sequence.) This number is therefore ${6 + 7 \choose 6} = 1716$. See here.

-
Why is this true I don't quite understand. Sorry –  Eric Chen Dec 11 '12 at 21:30
Example: two balls in bin $1$, one in bin $5$ and three in bin $7$. This situation translates to the sequence $$7,7,7,5,1,1.$$ In this way all ordered sequences correspond exactly to the distribution of six balls over eight bins. –  WimC Dec 11 '12 at 21:38

The following is essentially the same as the solution of WimC. The language is a little different.

For no good reason, except that I like sequences not to decrease, let us list the results in non-decreasing order.

Consider for example the sequence $2,3,3,4,7,7$. We can describe this sequence in an alternate way. The first number is $1$ from the bottom. The next number is $1$ from the previous one. The next number is $0$ from the previous one. The next number is $1$ from the previous one. The next number is $3$ from the previous one. The next number is $0$ from the previous one. Finally, not necessary, but very useful for the later analysis, the biggest possible number, $8$, is $1$ from the previous one.

Call the sequence $(1,1,0,1,3,0,1)$ the encoding sequence of $2,3,3,4,7,7$.

The encoding sequence has length $7$. This $7$ comes from the fact that the sequence we are encoding has length $6$. A sequence of length $k$ will have encoding sequence of length $k+1$.

The sum of the elements of the encoding sequence is $7$. This $7$ comes from the fact that our numbers come from $1,2,\dots,8$. If it were an $n$-sided die, we would have $n-1$ for the sum of the elements of an encoding sequence.

We want to count the number of encoding sequences of length $k+1=7$ with sum $n-1=7$.

So we want to count the number of ways to distribute $n-1$ identical candies among $k+1$ babies.

This is a standard "Stars and Bars" problem (see Wikipedia if you have not met the problem). But we do the details.

We want in this case to distribute $7$ identical candies among $7$ babies. Sorry again about the fact these numbers happen to be equal. This is a pure accident. Explanation would be clearer if we had a $20$-sided die, and we were counting non-increasing (or non-decreasing) sequences of length $6$.

Back to the babies. Being nasty, I like to distribute candies as follows. I distribute $14$ candies to the babies, at least one to each baby. Then I take away one candy from each baby (easy to do).

For the distribution, line up the candies in a row, with a little gap between them. There are $13$ gaps. Choose $6$ of these gaps, because there are $7$ babies. Put a divider into each chosen gap. Give all the candies from the left end up to the first divider to the first baby, the candies between the first two dividers to the second baby, and so on.

The number of ways to distribute the $14$ candies, at least one to each baby, is the number of ways of placing the dividers. This is $\dbinom{13}{6}$.

-