1,3

Number of n-tuples containing all elements of [m] with a unique last element.

Consider an urn with m balls of pairwise different colors. T(n,m) is motivated by the probability p(n,m) for exactly n draws with replacement needed to obtain all colors; p(n,m)=T(n,m)/m^n. - With m fixed and n running, p(n,m) is a probability distribution. The expected number of draws needed to obtain all colors is Sum_{j=1..m} m/j.

In the Laplace link, an asymptotic formula is given for i(n,k), the number of draws required to have probability 1/k that all balls have been drawn. However, Laplace did not consider the distribution of the draw-count.

Feller's Introduction, section 'Waiting times in sampling' (p. 211 in 2nd edition, 224 in 3rd) seems to be the first to discuss the expectation, then gives the variance as a problem (p. 224 in 2nd, p. 239 in 3rd).

William Feller, Introduction to Probability Theory and Its Applications, 2nd ed., 1957.

Pierre-Simon Laplace, Théorie analytique des probabilités, 1812.

Michael Shackleford, Problem 74. Free gift in the cereal box problem #2, Mathproblems.info.

Wikipedia, Coupon collector's problem.

T(n,m) = m!*S2(n-1,m-1) = m!*A048993(n-1,m-1).

T(n,m) = m*A131689(n-1,m-1).

T(n,3) = A068293(n-1), n>1.

From Natalia L. Skirrow, Aug 29 2025: (Start)

E.g.f.: (1/(1-(e^x-1)*y) + (x-log(y*(e^x-1)-1))/(1+y)) * y/(1+y)

E.g.f. for T(n+1,k+1): 1/(1-y*(e^x-1))^2.

In general, the e.g.f. of sequence T(n,k) = S2(n,k)*(o)_k is 1/(1-y(e^x-1))^o, where (o)_k = (o+k-1)!/(o-1)! is the Pochhammer symbol. (End)

The triangle T(n,m) begins:

n\m 1 2 3 4 5 6 7 8 9 10 ...

1: 1

2: 0 2

3: 0 2 6

4: 0 2 18 24

5: 0 2 42 144 120

6: 0 2 90 600 1200 720

7: 0 2 186 2160 7800 10800 5040

8: 0 2 378 7224 42000 100800 105840 40320

9: 0 2 762 23184 204120 756000 1340640 1128960 362880

10: 0 2 1530 72600 932400 5004720 13335840 18627840 13063680 3628800

...

T(4,3)=18 is the number of 4-sequences of draws from [3] completing the covering of [3] with the last draw; these sequences are (without brackets and commas):

1123 1213 1223 2113 2123 2213 1132 1312 1332

3112 3132 3312 2231 2321 2331 3221 3231 3321

Table[m! StirlingS2[n - 1, m - 1], {n, 10}, {m, n}]//Flatten

Cf. A048993, A068293, A131689.

Row sums give A005649(n-1) for n>=1.

Sequence in context: A115951 A264954 A212085 * A265882 A324253 A208385

Adjacent sequences: A380974 A380975 A380976 * A380978 A380979 A380980

nonn,tabl

Manfred Boergens, Feb 10 2025

approved