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, 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. (Expected value provided by M. Shackleford.)

Links

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

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

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.

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

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 * A380980 A380981 A380982

Keyword

nonn,tabl

Author

Manfred Boergens, Feb 10 2025

Status

approved