A392624 Parallelized coupon collector's problem: With n fair n-sided dice, a(n) = numerator(E(n)) where E(n) is the expected number of turns for n coordinating mice to have every face present.

1, 2, 27, 34, 310625, 986503, 16843633744903, 11394650921238434, 791434475057775645459711, 29361311928729307123950290459, 6116280052904149513141628731879369558959377, 3025374273219190570589666480219921811379, 699070991746814045478243555870571795054947212184515374999963830883

Offset

1,2

Comments

Each face with k>0 occurrences on a turn has 1 saved and the other k-1 rerolled on the next turn.

Mice holding saved values, do not reroll, so the number of mice rolling at each turn decreases until all n values have been saved.

This differs from the usual coupon collector's problem in that we are allow multiple rerolls in one turn; this changes the problem's growth from ~n*log(n) to ~n*zeta(2).

Links

Table of n, a(n) for n=1..13.

Mathematics StackExchange, Sequential allocation of n balls into n urns (2013)

Mathematics StackExchange, Number of trials rolling six 6-sided dice to get 6 unique values (2019)

Mathematics StackExchange, n balls into n urns until there is no empty urn (2021)

Formula

Heuristically, the expected number of turns a(n)/A392625(n) = E(n) ~ zeta(2)*n + log(n)/2 + c, with c slightly larger than 3/4.

Example

Expectations for n=1..8: 1, 2, 27/8, 34/7, 310625/48672, 986503/124400, 16843633744903/1774217134800, 11394650921238434/1029491058898575
Derivation for n=4: (Without loss of generality, state k has faces [1..k] seen, [k+1..n] unseen.)
State k=3 has chance 3/4 to return to itself, and 1/4 for rerolled die to be 4 (completing the set).
State k=2 has chance 4/16 for both rerolls to be existing faces ([1,1],[1,2],[2,1],[2,2]), 10/16 for one new ([_,3],[_,4],[3,_],[4,_],[3,3],[4,4]), and 2/16 for both new ([3,4],[4,3]).
State k=1 has chance 1/64 to return to itself, 21/64 for one new, 36/64 for two new, 6/64 for three new.
  t_3 = 1 + t_3*3/4
  t_2 = 1 + (t_2*2 + t_3*5)/8
  t_1 = 1 + (t_1 + 21*t_2 + 36*t_3)/64
Solving the linear equation, t_1 = 34/7.

Prog

(Python)
from fractions import Fraction as frac
from math import factorial as fact, comb
from sympy import Matrix
rsubset=lambda r, n, k: k>=r and sum((-1)**(k-r-i)*comb(k-r, i)*(i+r)**(n-r) for i in range(k-r+1))//fact(k-r)
P=lambda n, m, l: frac(fact(n-m), n**(n-m)*fact(n-l))*rsubset(m, n, l)
micedice=lambda n: int(n==1) or sum(Matrix([[(m==l)-P(n, m, l) for m in range(1, n)] for l in range(1, n)]).inv()[::n-1])
print([micedice(n) for n in range(1, 14)])

Crossrefs

Cf. A392625 (denominators).

Sequence in context: A041883 A226670 A277542 * A273844 A294678 A206585

Adjacent sequences: A392621 A392622 A392623 * A392625 A392626 A392627

Keyword

nonn,frac,changed

Author

Natalia L. Skirrow, Jan 17 2026

Status

approved