VOOZH about

URL: https://oeis.org/A380977

⇱ A380977 - OEIS


login
A380977
Triangle read by rows: T(n,m) (1<=m<=n) = number of surjections f:[n]->[m] with f(n) != f(j), j<n.
1
1, 0, 2, 0, 2, 6, 0, 2, 18, 24, 0, 2, 42, 144, 120, 0, 2, 90, 600, 1200, 720, 0, 2, 186, 2160, 7800, 10800, 5040, 0, 2, 378, 7224, 42000, 100800, 105840, 40320, 0, 2, 762, 23184, 204120, 756000, 1340640, 1128960, 362880, 0, 2, 1530, 72600, 932400, 5004720, 13335840, 18627840, 13063680, 3628800
OFFSET
1,3
COMMENTS
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).
REFERENCES
William Feller, Introduction to Probability Theory and Its Applications, 2nd ed., 1957.
FORMULA
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)
EXAMPLE
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
MATHEMATICA
Table[m! StirlingS2[n - 1, m - 1], {n, 10}, {m, n}]//Flatten
CROSSREFS
Row sums give A005649(n-1) for n>=1.
Sequence in context: A115951 A264954 A212085 * A265882 A324253 A208385
KEYWORD
nonn,tabl
AUTHOR
Manfred Boergens, Feb 10 2025
STATUS
approved