Throwing an N-sided die M times, probability of a unique number

Clash Royale CLAN TAG#URR8PPP

up vote
2
down vote

favorite

What is the probability of at least one number being rolled exactly once when throwing an N-sided die M times?

I have simulated this and it seems to be a strange function in M which starts at 1, drops, increases and drops off.

When N = 6:

M Probability

1 1.000

2 0.833

3 0.972

4 0.926

probability

share|cite|improve this question

asked Jul 24 at 15:28

user2290362

1174

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $fracNcdot (N-1)^M-1N^M$.
  – Dzoooks
  Jul 24 at 15:36
  

  
  
  
  

add a comment | 

up vote
2
down vote

favorite

What is the probability of at least one number being rolled exactly once when throwing an N-sided die M times?

I have simulated this and it seems to be a strange function in M which starts at 1, drops, increases and drops off.

When N = 6:

M Probability

1 1.000

2 0.833

3 0.972

4 0.926

probability

share|cite|improve this question

asked Jul 24 at 15:28

user2290362

1174

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $fracNcdot (N-1)^M-1N^M$.
  – Dzoooks
  Jul 24 at 15:36
  

  
  
  
  

add a comment | 

up vote
2
down vote

favorite

up vote
2
down vote

favorite

What is the probability of at least one number being rolled exactly once when throwing an N-sided die M times?

I have simulated this and it seems to be a strange function in M which starts at 1, drops, increases and drops off.

When N = 6:

M Probability

1 1.000

2 0.833

3 0.972

4 0.926

probability

share|cite|improve this question

asked Jul 24 at 15:28

user2290362

1174

What is the probability of at least one number being rolled exactly once when throwing an N-sided die M times?

I have simulated this and it seems to be a strange function in M which starts at 1, drops, increases and drops off.

When N = 6:

M Probability

1 1.000

2 0.833

3 0.972

4 0.926

probability

share|cite|improve this question

asked Jul 24 at 15:28

user2290362

1174

share|cite|improve this question

share|cite|improve this question

asked Jul 24 at 15:28

user2290362

1174

asked Jul 24 at 15:28

user2290362

1174

asked Jul 24 at 15:28

user2290362

1174

1174

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $fracNcdot (N-1)^M-1N^M$.
  – Dzoooks
  Jul 24 at 15:36
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $fracNcdot (N-1)^M-1N^M$.
  – Dzoooks
  Jul 24 at 15:36
  

  
  
  
  

$fracNcdot (N-1)^M-1N^M$.
– Dzoooks
Jul 24 at 15:36

$fracNcdot (N-1)^M-1N^M$.
– Dzoooks
Jul 24 at 15:36

add a comment | 

2 Answers
2

active

oldest

votes

up vote
5
down vote



accepted

You can do this using inclusion–exclusion.

The probability for $k$ particular numbers to be rolled exactly once in $M$ rolls is

begineqnarray*
p_M,k
&=&
fracM!(M-k)!left(frac1Nright)^kleft(1-frac kNright)^M-k
\
&=&
N^-MfracM!(M-k)!(N-k)^M-k;.
endeqnarray*

Then by inclusion–exclusion, the probability for at least one number to be rolled exactly once is

begineqnarray*
p_M
&=&
sum_k=1^min(N,M)(-1)^k-1binom Nkp_M,k
\
&=&
sum_k=1^min(N,M)(-1)^k-1binom NkN^-MfracM!(M-k)!(N-k)^M-k
\
&=&N^-MM!
sum_k=1^min(N,M)(-1)^k-1binom Nkfrac(N-k)^M-k(M-k)!;.
endeqnarray*

For $N=6$, we get

begineqnarray*
p_1
&=&
6^-1cdot6=1;,\
p_2
&=&
6^-2cdot2!left(6cdotfrac(6-1)^2-1(2-1)!-binom62right)
\
&=⅚,
\
p_3
&=&
6^-3cdot3!left(6cdotfrac(6-1)^3-1(3-1)!-binom62cdotfrac(6-2)^3-2(3-2)!+binom63right)
\
&=&
frac3536;,
\
p_4
&=&
6^-4cdot4!left(6cdotfrac(6-1)^4-1(4-1)!-binom62cdotfrac(6-2)^4-2(4-2)!+binom63cdotfrac(6-3)^4-3(4-3)!-binom64right)
\
&=&
frac7581;,
endeqnarray*

and so on.

share|cite|improve this answer

edited Jul 24 at 16:10

answered Jul 24 at 16:00

joriki

164k10180328

add a comment | 

up vote
1
down vote

We get for the complementary probability of no unique number from
first principles that it is

$$frac1N^M M! [z^M] (exp(z)-z)^N
\= frac1N^M M! [z^M]
sum_q=0^N Nchoose q (-1)^q z^q exp((N-q)z)
\= frac1N^M M!
sum_q=0^min(M,N) Nchoose q (-1)^q [z^M-q] exp((N-q)z)
\= frac1N^M M!
sum_q=0^min(M,N)
Nchoose q (-1)^q frac(N-q)^M-q(M-q)!.$$

This gives for the desired probability the value

$$1- frac1N^M M!
sum_q=0^min(M,N)
Nchoose q (-1)^q frac(N-q)^M-q(M-q)!
\ = fracM!N^M sum_q=1^min(M,N)
Nchoose q (-1)^q+1 frac(N-q)^M-q(M-q)!.$$

Here we have used the labeled combinatorial class

$$deftextsc#1dosc#1csod
defdosc#1#2csodrm #1small #2
textscSEQ_=N(textscSET_ne 1(mathcalZ))
quad textwith EGFquad (exp(z)-z)^N.$$

This matches the answer that was first to appear.

share|cite|improve this answer

edited Jul 25 at 19:19

answered Jul 25 at 17:39

Marko Riedel

36.4k333107

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861467%2fthrowing-an-n-sided-die-m-times-probability-of-a-unique-number%23new-answer', 'question_page');

);

Post as a guest

Name Email

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
5
down vote



accepted

You can do this using inclusion–exclusion.

The probability for $k$ particular numbers to be rolled exactly once in $M$ rolls is

begineqnarray*
p_M,k
&=&
fracM!(M-k)!left(frac1Nright)^kleft(1-frac kNright)^M-k
\
&=&
N^-MfracM!(M-k)!(N-k)^M-k;.
endeqnarray*

Then by inclusion–exclusion, the probability for at least one number to be rolled exactly once is

begineqnarray*
p_M
&=&
sum_k=1^min(N,M)(-1)^k-1binom Nkp_M,k
\
&=&
sum_k=1^min(N,M)(-1)^k-1binom NkN^-MfracM!(M-k)!(N-k)^M-k
\
&=&N^-MM!
sum_k=1^min(N,M)(-1)^k-1binom Nkfrac(N-k)^M-k(M-k)!;.
endeqnarray*

For $N=6$, we get

begineqnarray*
p_1
&=&
6^-1cdot6=1;,\
p_2
&=&
6^-2cdot2!left(6cdotfrac(6-1)^2-1(2-1)!-binom62right)
\
&=⅚,
\
p_3
&=&
6^-3cdot3!left(6cdotfrac(6-1)^3-1(3-1)!-binom62cdotfrac(6-2)^3-2(3-2)!+binom63right)
\
&=&
frac3536;,
\
p_4
&=&
6^-4cdot4!left(6cdotfrac(6-1)^4-1(4-1)!-binom62cdotfrac(6-2)^4-2(4-2)!+binom63cdotfrac(6-3)^4-3(4-3)!-binom64right)
\
&=&
frac7581;,
endeqnarray*

and so on.

share|cite|improve this answer

edited Jul 24 at 16:10

answered Jul 24 at 16:00

joriki

164k10180328

add a comment | 

up vote
5
down vote



accepted

You can do this using inclusion–exclusion.

The probability for $k$ particular numbers to be rolled exactly once in $M$ rolls is

begineqnarray*
p_M,k
&=&
fracM!(M-k)!left(frac1Nright)^kleft(1-frac kNright)^M-k
\
&=&
N^-MfracM!(M-k)!(N-k)^M-k;.
endeqnarray*

Then by inclusion–exclusion, the probability for at least one number to be rolled exactly once is

begineqnarray*
p_M
&=&
sum_k=1^min(N,M)(-1)^k-1binom Nkp_M,k
\
&=&
sum_k=1^min(N,M)(-1)^k-1binom NkN^-MfracM!(M-k)!(N-k)^M-k
\
&=&N^-MM!
sum_k=1^min(N,M)(-1)^k-1binom Nkfrac(N-k)^M-k(M-k)!;.
endeqnarray*

For $N=6$, we get

begineqnarray*
p_1
&=&
6^-1cdot6=1;,\
p_2
&=&
6^-2cdot2!left(6cdotfrac(6-1)^2-1(2-1)!-binom62right)
\
&=⅚,
\
p_3
&=&
6^-3cdot3!left(6cdotfrac(6-1)^3-1(3-1)!-binom62cdotfrac(6-2)^3-2(3-2)!+binom63right)
\
&=&
frac3536;,
\
p_4
&=&
6^-4cdot4!left(6cdotfrac(6-1)^4-1(4-1)!-binom62cdotfrac(6-2)^4-2(4-2)!+binom63cdotfrac(6-3)^4-3(4-3)!-binom64right)
\
&=&
frac7581;,
endeqnarray*

and so on.

share|cite|improve this answer

edited Jul 24 at 16:10

answered Jul 24 at 16:00

joriki

164k10180328

add a comment | 

up vote
5
down vote



accepted

up vote
5
down vote



accepted

You can do this using inclusion–exclusion.

The probability for $k$ particular numbers to be rolled exactly once in $M$ rolls is

begineqnarray*
p_M,k
&=&
fracM!(M-k)!left(frac1Nright)^kleft(1-frac kNright)^M-k
\
&=&
N^-MfracM!(M-k)!(N-k)^M-k;.
endeqnarray*

Then by inclusion–exclusion, the probability for at least one number to be rolled exactly once is

begineqnarray*
p_M
&=&
sum_k=1^min(N,M)(-1)^k-1binom Nkp_M,k
\
&=&
sum_k=1^min(N,M)(-1)^k-1binom NkN^-MfracM!(M-k)!(N-k)^M-k
\
&=&N^-MM!
sum_k=1^min(N,M)(-1)^k-1binom Nkfrac(N-k)^M-k(M-k)!;.
endeqnarray*

For $N=6$, we get

begineqnarray*
p_1
&=&
6^-1cdot6=1;,\
p_2
&=&
6^-2cdot2!left(6cdotfrac(6-1)^2-1(2-1)!-binom62right)
\
&=⅚,
\
p_3
&=&
6^-3cdot3!left(6cdotfrac(6-1)^3-1(3-1)!-binom62cdotfrac(6-2)^3-2(3-2)!+binom63right)
\
&=&
frac3536;,
\
p_4
&=&
6^-4cdot4!left(6cdotfrac(6-1)^4-1(4-1)!-binom62cdotfrac(6-2)^4-2(4-2)!+binom63cdotfrac(6-3)^4-3(4-3)!-binom64right)
\
&=&
frac7581;,
endeqnarray*

and so on.

share|cite|improve this answer

edited Jul 24 at 16:10

answered Jul 24 at 16:00

joriki

164k10180328

You can do this using inclusion–exclusion.

The probability for $k$ particular numbers to be rolled exactly once in $M$ rolls is

begineqnarray*
p_M,k
&=&
fracM!(M-k)!left(frac1Nright)^kleft(1-frac kNright)^M-k
\
&=&
N^-MfracM!(M-k)!(N-k)^M-k;.
endeqnarray*

Then by inclusion–exclusion, the probability for at least one number to be rolled exactly once is

begineqnarray*
p_M
&=&
sum_k=1^min(N,M)(-1)^k-1binom Nkp_M,k
\
&=&
sum_k=1^min(N,M)(-1)^k-1binom NkN^-MfracM!(M-k)!(N-k)^M-k
\
&=&N^-MM!
sum_k=1^min(N,M)(-1)^k-1binom Nkfrac(N-k)^M-k(M-k)!;.
endeqnarray*

For $N=6$, we get

begineqnarray*
p_1
&=&
6^-1cdot6=1;,\
p_2
&=&
6^-2cdot2!left(6cdotfrac(6-1)^2-1(2-1)!-binom62right)
\
&=⅚,
\
p_3
&=&
6^-3cdot3!left(6cdotfrac(6-1)^3-1(3-1)!-binom62cdotfrac(6-2)^3-2(3-2)!+binom63right)
\
&=&
frac3536;,
\
p_4
&=&
6^-4cdot4!left(6cdotfrac(6-1)^4-1(4-1)!-binom62cdotfrac(6-2)^4-2(4-2)!+binom63cdotfrac(6-3)^4-3(4-3)!-binom64right)
\
&=&
frac7581;,
endeqnarray*

and so on.

share|cite|improve this answer

edited Jul 24 at 16:10

answered Jul 24 at 16:00

joriki

164k10180328

share|cite|improve this answer

share|cite|improve this answer

edited Jul 24 at 16:10

edited Jul 24 at 16:10

edited Jul 24 at 16:10

answered Jul 24 at 16:00

joriki

164k10180328

answered Jul 24 at 16:00

joriki

164k10180328

answered Jul 24 at 16:00

joriki

164k10180328

164k10180328

add a comment | 

add a comment | 

up vote
1
down vote

We get for the complementary probability of no unique number from
first principles that it is

$$frac1N^M M! [z^M] (exp(z)-z)^N
\= frac1N^M M! [z^M]
sum_q=0^N Nchoose q (-1)^q z^q exp((N-q)z)
\= frac1N^M M!
sum_q=0^min(M,N) Nchoose q (-1)^q [z^M-q] exp((N-q)z)
\= frac1N^M M!
sum_q=0^min(M,N)
Nchoose q (-1)^q frac(N-q)^M-q(M-q)!.$$

This gives for the desired probability the value

$$1- frac1N^M M!
sum_q=0^min(M,N)
Nchoose q (-1)^q frac(N-q)^M-q(M-q)!
\ = fracM!N^M sum_q=1^min(M,N)
Nchoose q (-1)^q+1 frac(N-q)^M-q(M-q)!.$$

Here we have used the labeled combinatorial class

$$deftextsc#1dosc#1csod
defdosc#1#2csodrm #1small #2
textscSEQ_=N(textscSET_ne 1(mathcalZ))
quad textwith EGFquad (exp(z)-z)^N.$$

This matches the answer that was first to appear.

share|cite|improve this answer

edited Jul 25 at 19:19

answered Jul 25 at 17:39

Marko Riedel

36.4k333107

add a comment | 

up vote
1
down vote

We get for the complementary probability of no unique number from
first principles that it is

$$frac1N^M M! [z^M] (exp(z)-z)^N
\= frac1N^M M! [z^M]
sum_q=0^N Nchoose q (-1)^q z^q exp((N-q)z)
\= frac1N^M M!
sum_q=0^min(M,N) Nchoose q (-1)^q [z^M-q] exp((N-q)z)
\= frac1N^M M!
sum_q=0^min(M,N)
Nchoose q (-1)^q frac(N-q)^M-q(M-q)!.$$

This gives for the desired probability the value

$$1- frac1N^M M!
sum_q=0^min(M,N)
Nchoose q (-1)^q frac(N-q)^M-q(M-q)!
\ = fracM!N^M sum_q=1^min(M,N)
Nchoose q (-1)^q+1 frac(N-q)^M-q(M-q)!.$$

Here we have used the labeled combinatorial class

$$deftextsc#1dosc#1csod
defdosc#1#2csodrm #1small #2
textscSEQ_=N(textscSET_ne 1(mathcalZ))
quad textwith EGFquad (exp(z)-z)^N.$$

This matches the answer that was first to appear.

share|cite|improve this answer

edited Jul 25 at 19:19

answered Jul 25 at 17:39

Marko Riedel

36.4k333107

add a comment | 

up vote
1
down vote

up vote
1
down vote

We get for the complementary probability of no unique number from
first principles that it is

$$frac1N^M M! [z^M] (exp(z)-z)^N
\= frac1N^M M! [z^M]
sum_q=0^N Nchoose q (-1)^q z^q exp((N-q)z)
\= frac1N^M M!
sum_q=0^min(M,N) Nchoose q (-1)^q [z^M-q] exp((N-q)z)
\= frac1N^M M!
sum_q=0^min(M,N)
Nchoose q (-1)^q frac(N-q)^M-q(M-q)!.$$

This gives for the desired probability the value

$$1- frac1N^M M!
sum_q=0^min(M,N)
Nchoose q (-1)^q frac(N-q)^M-q(M-q)!
\ = fracM!N^M sum_q=1^min(M,N)
Nchoose q (-1)^q+1 frac(N-q)^M-q(M-q)!.$$

Here we have used the labeled combinatorial class

$$deftextsc#1dosc#1csod
defdosc#1#2csodrm #1small #2
textscSEQ_=N(textscSET_ne 1(mathcalZ))
quad textwith EGFquad (exp(z)-z)^N.$$

This matches the answer that was first to appear.

share|cite|improve this answer

edited Jul 25 at 19:19

answered Jul 25 at 17:39

Marko Riedel

36.4k333107

We get for the complementary probability of no unique number from
first principles that it is

$$frac1N^M M! [z^M] (exp(z)-z)^N
\= frac1N^M M! [z^M]
sum_q=0^N Nchoose q (-1)^q z^q exp((N-q)z)
\= frac1N^M M!
sum_q=0^min(M,N) Nchoose q (-1)^q [z^M-q] exp((N-q)z)
\= frac1N^M M!
sum_q=0^min(M,N)
Nchoose q (-1)^q frac(N-q)^M-q(M-q)!.$$

This gives for the desired probability the value

$$1- frac1N^M M!
sum_q=0^min(M,N)
Nchoose q (-1)^q frac(N-q)^M-q(M-q)!
\ = fracM!N^M sum_q=1^min(M,N)
Nchoose q (-1)^q+1 frac(N-q)^M-q(M-q)!.$$

Here we have used the labeled combinatorial class

$$deftextsc#1dosc#1csod
defdosc#1#2csodrm #1small #2
textscSEQ_=N(textscSET_ne 1(mathcalZ))
quad textwith EGFquad (exp(z)-z)^N.$$

This matches the answer that was first to appear.

share|cite|improve this answer

edited Jul 25 at 19:19

answered Jul 25 at 17:39

Marko Riedel

36.4k333107

share|cite|improve this answer

share|cite|improve this answer

edited Jul 25 at 19:19

edited Jul 25 at 19:19

edited Jul 25 at 19:19

answered Jul 25 at 17:39

Marko Riedel

36.4k333107

answered Jul 25 at 17:39

Marko Riedel

36.4k333107

answered Jul 25 at 17:39

Marko Riedel

36.4k333107

36.4k333107

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861467%2fthrowing-an-n-sided-die-m-times-probability-of-a-unique-number%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email