Author |
Topic: k-sided die rolled n times (Read 1030 times) |
|
jarls
Newbie
Posts: 32
|
 |
k-sided die rolled n times
« on: May 1st, 2009, 1:20am » |
 Quote  Modify
|
is the probability of all sides showing up at least once for a k-sided die which is rolled n times
k!/k^n?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: k-sided die rolled n times
« Reply #1 on: May 1st, 2009, 2:59am » |
Quote Modify
|
No, because the probability of all sides showing at least once goes to 1 as n increases, whereas k!/k^n goes to 0.
I'll need a few moments to figure out what the correct formula is, because I know I tend to get it wrong; even though by now I should remember it.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: k-sided die rolled n times
« Reply #2 on: May 1st, 2009, 5:59am » |
Quote Modify
|
One approach is to reverse the probability and use inclusion/exclusion.
P(all sides rolled)
= 1 - P(at least one side not rolled)
= 1 - [kC1 (k-1]n - kC2 (k-2]n + kC3 (k-3]n - ... ] / kn
= Sum over i from 0 to k of (-1)i kCi [(k-i)/k]n
But that's where I get stuck, as I don't know if there's a way to find a closed-form representation of that sum.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
jarls
Newbie
Posts: 32
|
|
Re: k-sided die rolled n times
« Reply #4 on: May 1st, 2009, 8:27pm » |
Quote Modify
|
This is a riddle found in the 'relatively hard' section.
Why did you move it to the 'easy' section of the forum?
|
|
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: k-sided die rolled n times
« Reply #5 on: May 2nd, 2009, 1:34am » |
Quote Modify
|
Hi, Towr,
Jaris is referring to every die face in Williams hard section.
Hi, Jaris,
I suppose Towr moved it because he had an easy answer to the question as it was formulated in this thread.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: k-sided die rolled n times
« Reply #6 on: May 2nd, 2009, 9:36am » |
Quote Modify
|
on May 1st, 2009, 8:27pm, jarls wrote:| This is a riddle found in the 'relatively hard' section. |
|
Ah sorry, I didn't know that.
Quote:| Why did you move it to the 'easy' section of the forum? |
|
The rating between the riddle site and the forum has diverged a bit over time. I didn't feel it was appropriate for the hard section; although if I had known it was classified as such on the riddle site I'd have left it.
As for why then easy rather than medium, that's because I thought I remembered it having an easier answer. There are a number of variations on the theme of what is equivalent to a "putting N balls in K bins", which vary in how easy they are to solve.
If my memory had served me better I'd have gone with medium in retrospect.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print