Dtyjlui

A dice is rolled $20$ times, with the possible results $left{1,2,3,4,5,6right}$.

Let $X$ be the number of results, out of the possible 6, which were chosen only once during the 20 rolls.

Calculate $Pleft{Xright}$

I find it hard to identify the kind of variable it is. It isn't bio nominal nor hyper geometric.

I understand I have to choose 4 rolls out of the 20, and the combination between them is $4!$, giving me -

$$ frac{binom{20}{4} times binom{6}{4} times 4!}{6^{20}} $$

For the chosen "results", the chosen "rolls' and the inner combination between them. But how about the other "rolls"? Something is missing here.

Observe that since there are $20$ rolls, $P(X=6)=0$. So we need only check the probabilities that $X=1,2,3,4,5$. These can be done on a case by case basis.

For $X=5$, the probability is
$$frac{binom{6}{5}cdotbinom{20}{5}cdot 5!}{6^{20}}$$
since we must choose the the $5$ results which will occur only once, and choose which rolls they occur on in $binom{20}{5}$ ways, accounting for their orderings.

For $X=4$, the probability is
$$frac{binom{6}{4}cdotbinom{20}{4}cdot 4!cdot (2^{16}-30)}{6^{20}}$$
since we must choose the $4$ results which will occur only once, choose which rolls they occur on, order these $4$ results (in $4!$ ways), and then fill in the remaining $16$ rolls with the other two results. We must be a bit careful here, since we need each of the other results to occur at least twice, or not at all. Denote the remaining results by $x$ and $y$. Since there are $16$ rolls to fill in with $x'$s and $y$'s, there are $2^{16}$ possible outcomes. $15$ of them consist of $15 x'$s and one $y$, and another $15$ consist of $15 y$'s and one $x$. Discarding these $30$ undesirable outcomes leaves $2^{16}-30$.

The argument is similar for the other cases, but the last bit corresponding to the results that don't appear exactly once gets a bit more complicated. For $X=3$, we have have $17$ rolls that must be filled with, say, $x,y,z$ such that neither $x,y,$ nor $z$ appears exactly once. There are $17cdot 2^{16}$ ways for $x,y,$ or $z$ to appear once (place it in one of $17$ positions then fill the other $16$ rolls with the other two results). And there are $binom{17}{2}$ ways for two of them to appear only once. Since these are double-counted above, there are $3(17cdot 2^{16}-binom{17}{2})$ undesirable cases to discard.

I'll leave the cases $X=1,2$ up to you to compute. For now I'll just denote by $C_{4},C_{5}$ the number of ways to arrange the remaining results without any of them appearing exactly once. Therefore

$$P(X=3)=frac{binom{6}{3}cdotbinom{20}{3}cdot 3!cdot [3(17cdot 2^{16}-binom{17}{2})]}{6^{20}}$$

$$P(X=2)=frac{binom{6}{2}cdotbinom{20}{2}cdot 2!cdot (4^{18}-C_{4})}{6^{20}}$$
$$P(X=1)=frac{binom{6}{1}cdotbinom{20}{1}cdot (5^{16}-C_{5})}{6^{20}}$$

For completeness, observe that (clearly) $P(X<1)=P(X>6)=0$.

It isn't bio nominal nor hyper geometric.

Why would it be anything with a nice name?

I understand I have to choose 4 rolls out of the 20

I have no idea where this came from, but it is wrong.

To actually answer your question, we'll first find a (reverse) cumulative density function for $P$, then calculate the actual values from that.

So, what's the probability that $X$ is at least $k$ (for $1 leq k leq 5$? That means that there are at least $k$ elements of ${1,2,3,4,5,6}$ (with $left(array{6\k}right)$ choices) that don't come up, and $k$ of our rolls take the appropriate values, one at a time ($left(array{20\k}right)k!$ possibilities), while the other $20-k$ take values the remaining $6 - k$ possible values ($(6-k)^{20-k}$ possibilities).

Our numbers $N(X=k)$ of possibilities for $X$ to take a value no smaller than each $k$ is therefore given by:

begin{array}{c|c|c}X&N(Xgeq k)&N(Xgeq k)mbox{ simplified}\hline
\0&6^{20}&6^{20}
\1&left(array{6\1}right)1!left(array{20\1}right)(6-1)^{20-1}&24(5)^{20}
\2&left(array{6\2}right)2!left(array{20\2}right)(6-2)^{20-2}&1425(4)^{19}
\3&left(array{6\3}right)3!left(array{20\3}right)(6-3)^{20-3}&15200(3)^{19}
\4&left(array{6\4}right)4!left(array{20\4}right)(6-4)^{20-4}&218025(2)^{19}
\5&left(array{6\5}right)5!left(array{20\5}right)(6-5)^{20-5}&11162880
\6&0&0end{array}

The actual counts for each value of $X$ are then given by the differences between these: $N(X = k) = N(X geq k) - N(X geq k+1)$:

begin{array}{c|c|c}X&N(X= k)&N(X=k)mbox{ evaluated}\hline
\0&6^{20}-24(5)^{20}&1367340080687976
\1&24(5)^{20}-1425(4)^{19}&1897117341979800
\2&1425(4)^{19}-15200(3)^{19}&374034643096800
\3&15200(3)^{19}-218025(2)^{19}&17552066407200
\4&218025(2)^{19}-11162880&114296728320
\5&11162880&11162880
\6&0&0end{array}

And our probabilities are, therefore, given by dividing these by $6^{20}$:

begin{array}{c|c|c|c}X&P(X= k)&P(X=k)mbox{ evaluated}&mbox{approx.}\hline
\0&1-24left(frac{5}{6}right)^{20}&frac{56972503361999}{152339935002624}&0.37398
\1&24left(frac{5}{6}right)^{20}-1425left(frac{2}{3}right)^{19}&frac{79046555915825}{152339935002624}&0.51888
\2&1425left(frac{2}{3}right)^{19}-15200left(frac{1}{2}right)^{19}&frac{3896194198925}{38084983750656}&0.10230
\3&15200left(frac{1}{2}right)^{19}-218025left(frac{1}{3}right)^{19}&frac{20314891675}{4231664861184}&0.0048007
\4&218025left(frac{1}{3}right)^{19}-frac{11162880}{6^20}&frac{5511995}{176319369216}&0.000031261
\5&frac{11162880}{6^{20}}&frac{1615}{528958107648}&0.0000000030532end{array}

It is not difficult to provide a complete answer to thise question.
With a die having $N$ sides and being rolled $M$ times we get the
marked combinatorial class

$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{rm #1{small #2}}}
textsc{SEQ}_{=N}(textsc{SET}_{=0}(mathcal{Z})
+mathcal{U} times textsc{SET}_{=1}(mathcal{Z})
+textsc{SET}_{ge 2}(mathcal{Z})).$$

We thus get the mixed generating function

$$G(z, u) = (exp(z)-z + uz)^N =
(exp(z)+(u-1)z)^N.$$

We then get for the probability

$$mathrm{P}[X=k] = frac{1}{N^M} sum_{q=0}^N M! [z^M]
[u^k] (exp(z) + (u-1) z )^N
\ = frac{M!}{N^M} [z^M]
sum_{q=0}^N {Nchoose q} [u^k] (u-1)^q z^q exp((N-q)z)
\ = frac{M!}{N^M}
sum_{q=0}^N {Nchoose q} {qchoose k} (-1)^{q-k}
[z^{M-q}] exp((N-q)z)
\ = frac{M!}{N^M}
sum_{q=0}^{min(N,M)} {Nchoose q} {qchoose k} (-1)^{q-k}
frac{(N-q)^{M-q}}{(M-q)!}.$$

Now

$${Nchoose q} {qchoose k} =
frac{N!}{(N-q)! times k! times (q-k)!}
= {Nchoose k} {N-kchoose N-q}$$

so we finally get for the probability

$$bbox[5px,border:2px solid #00A000]{
mathrm{P}[X=k]
= frac{M!}{N^M} {Nchoose k}
sum_{q=0}^{min(N,M)} {N-kchoose N-q} (-1)^{q-k}
frac{(N-q)^{M-q}}{(M-q)!}.}$$

This yields e.g. for a four-sided die and seven rolls the PGF

$${frac {799}{4096}}+{frac {1701,u}{4096}}
+{frac {693,{u}^{2}}{2048}}+{frac {105,{u}^{3}}{2048}}.$$

A regular die with six sides and ten rolls produces

$${frac {409703}{5038848}}+{frac {1356025,u}{5038848}}
+{frac {12275,{u}^{2}}{34992}}+{frac {8075,{u}^{3}}{34992}}
\ +{frac {2275,{u}^{4}}{34992}}+{frac {35,{u}^{5}}{11664}}.$$

In particular, six sides and twenty rolls will produce

$${frac {72562042521379}{152339935002624}}
+{frac {2404256592175,u}{5642219814912}}
+{frac {3535287814775,{u}^{2}}{38084983750656}}
\ +{frac {2213124275,{u}^{3}}{470184984576}}
+{frac {16529525,{u}^{4}}{528958107648}}
+{frac {1615,{u}^{5}}{528958107648}}.$$

As a sanity check we get for five values appearing once where the
sixth must fill the remaining slots the probability:

$${6choose 5} {20choose 5} 5! times frac{1}{6^{20}}
= frac{1615}{528958107648}$$

and the check goes through.

We can also compute the expectation, either by differentiating the PGF
or alternatively by

$$frac{1}{N^M} M! [z^M]
left. frac{partial}{partial u} G(z, u) right|_{u=1}
\ = frac{1}{N^M} M! [z^M]
left. N (exp(z)-z+uz)^{N-1} z right|_{u=1}
\ = frac{1}{N^{M-1}} M! [z^{M-1}] exp((N-1)z)
= frac{1}{N^{M-1}} M! frac{1}{(M-1)!} (N-1)^{M-1}.$$

This is

$$bbox[5px,border:2px solid #00A000]{
mathrm{E}[X] = M times left(1-frac{1}{N}right)^{M-1}.}$$

This also follows by linearity of expectation. We get for the probability
of a particular face appearing once

$${Mchoose 1} times frac{1}{N} left(1-frac{1}{N}right)^{M-1}.$$

Sum over $N$ to get the expectation.

The above results were verified with the following Maple routines.

with(combinat);



ENUMPGFX :=

proc(N, M)

    option remember;

    local res, part, psize, mset, adm;



    res := 0;



    part := firstpart(M);



    while type(part, `list`) do

        psize := nops(part);

        mset := convert(part, `multiset`);



        adm :=

        nops(select(ent -> ent = 1, part));



        res := res + u^adm * binomial(N, psize) *

        M!/mul(p!, p in part) *

        psize!/mul(p[2]!, p in mset);



        part := nextpart(part);

    od;



    res/N^M;

end;



PGF := (N, M) ->

M!/N^M*add(u^k*binomial(N,k)*

           add(binomial(N-k, N-q)*(-1)^(q-k)*

               (N-q)^(M-q)/(M-q)!, q=0..min(N,M)),

           k=0..N);



ENUMEX := (N, M) -> subs(u=1, diff(ENUMPGFX(N, M), u));

PGFEX := (N, M) -> subs(u=1, diff(PGF(N, M), u));



EX := (N, M) -> M*(1-1/N)^(M-1);