Dice Rolling

Arrangements, combinations and permutations, probability, ...
Post Reply
drwhat
Posts: 42
Joined: Tue Sep 06, 2011 4:56 am

Dice Rolling

Post by drwhat »

Sadly mathhelpform seems to have gone down. I usually post such questions there, but thought I might try here.

A friend and I like to pose various problems to each other. The most recent one I got was: What are the odds of rolling a dice n times without repeating a number. (i'm pretty sure this isn't a euler problem, I apologize if it is.) For example if n=6 131315 is valid roll. but 133151 is not.

I've figured out most of the problem, but i'm stuck on one part and randomly surfing google, wikipedia and wolfram hasn't turned up any answers.
If I get single set of numbers : 111223333445. the number of combos of this is: 12!/(3!2!4!2!)

What I can't figure out is how to elminate the permutations where 2 numbers follow each other. I'm fairly certain i need to use some form of inclusion/exclusion but not sure how to proceed. For a simpler case: 11122245: I believe the answer should be:

8!/(3!3!) - All the ways 1 repeats - All the ways 2 repeats + All the ways 1 repeats and 2 repeats. But i'm stumped at how to generate the 3 answers.

Any help would be appreciated, or even a suggestion on where to get an answer
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Dice Rolling

Post by thundre »

On each roll you can roll any number except the result of the previous roll? If I understand the question correctly, you're making the solution much too complicated.

p(1) = 1
p(n) = p(n-1) * [frac]5,6[/frac]

And from there you can get a closed-form solution.
Image
drwhat
Posts: 42
Joined: Tue Sep 06, 2011 4:56 am

Re: Dice Rolling

Post by drwhat »

Heh of course your right. Very simple. Thank you for the insight, I've already solved my problem and sent one back.

Though now that I've been thinking about this a bit, i'm wondering if there is an easy solution to the following:

Say you have the letter sequence MISSISSIPPI.

1.How many ways can you rearrange these letters: Turns out its 11!/(4!4!2!).

2.How many ways can you rearrange these letters so that no two adjacent letter are the same letter. (THe actual word mississippi would be invalid).

It took me a bit to puzzle out the answer to 1, and it seems like there should be an logical way to figure it out the answer to 2, but it just keeps eluding me.
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Dice Rolling

Post by thundre »

drwhat wrote:2.How many ways can you rearrange these letters so that no two adjacent letter are the same letter. (THe actual word mississippi would be invalid).
I don't have an immediate solution to that, but it would be relatively straightforward using dynamic programming.

The states would be the inventory of each letter (5x5x3x2) and the last letter used (5 because you need a null case for complete freedom at the beginning). That's a total of 750 states, 11 iterations. Some states are unreachable or dead ends. Each state occurs on at most one iteration.
Image
Post Reply