Author |
Topic: EVERY DIE FACE (Read 1435 times) |
|
jonderry
Newbie
Posts: 18
|
 |
EVERY DIE FACE
« on: Sep 18th, 2004, 5:59pm » |
 Quote  Modify
|
Does anyone know how to get this in closed form? I can't figure it out so far, even searching the web.
|
|
 IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
|
Re: EVERY DIE FACE
« Reply #1 on: Sep 20th, 2004, 5:12am » |
Quote Modify
|
on Sep 18th, 2004, 5:59pm, jonderry wrote:| Does anyone know how to get this in closed form? I can't figure it out so far, even searching the web. |
|
You roll a k-sided die n times. What is the probability that each of the k faces appeared at least once?
The number of ways of throwing a k-sided die n times, so that all k sides turn up at least once,
is equal to
the number of ways of distributing n balls among k bins, so that every bin contains at least one ball.
This number is given by S(n,k).
Hence probability = S(n,k) / kn
|
| « Last Edit: Sep 20th, 2004, 5:18am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: EVERY DIE FACE
« Reply #2 on: Sep 20th, 2004, 5:42am » |
Quote Modify
|
I was really surprised that this problem was not on the site 
It's just a reformulation of a classical Occupancy Problem. Don't miss the "Approximation with a Poisson distribution" at the link!
|
|
IP Logged |
|
|
|
jonderry
Newbie
Posts: 18
|
|
Re: EVERY DIE FACE
« Reply #3 on: Sep 24th, 2004, 7:48pm » |
Quote Modify
|
I don't see how this works.
Suppose n = 3 and k = 2.
Then, S(3,2) = 3.
However, the odds of getting "heads" and "tails"
is clearly 6/8, not 3/8.
Perhaps you need to multiply by k!?
If so, it seems like there is indeed no closed formula for for this problem, unless there is a closed form for S(n, k) that is escaping me.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: EVERY DIE FACE
« Reply #4 on: Sep 25th, 2004, 1:25am » |
Quote Modify
|
Jonderry,
You are right. The formula THUD&BLUNDER sent, should be multiplied by k!. The folrmula may be also derived using the famous inclusion-exclusion principle.
I am pretty sure no closed form exists for it.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: EVERY DIE FACE
« Reply #5 on: Sep 25th, 2004, 3:44am » |
Quote Modify
|
on Sep 25th, 2004, 1:25am, Barukh wrote:
I am pretty sure no closed form exists for it. |
|
S(n,k) can be expressed in terms of a finite sum, which I would consider to be closed-form - unlike an infinite sum, for example.
|
| « Last Edit: Sep 25th, 2004, 5:42am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print