A049009 Number of functions from a set to itself such that the sizes of the preimages of the individual elements in the range form the n-th partition in Abramowitz and Stegun order.

1, 1, 2, 2, 3, 18, 6, 4, 48, 36, 144, 24, 5, 100, 200, 600, 900, 1200, 120, 6, 180, 450, 300, 1800, 7200, 1800, 7200, 16200, 10800, 720, 7, 294, 882, 1470, 4410, 22050, 14700, 22050, 29400, 176400, 88200, 88200, 264600, 105840, 5040, 8, 448, 1568, 3136, 1960

Offset

0,3

Comments

a(n,k) is a refinement of 1; 2,2; 3,18,6; 4,84,144,24; ... cf. A019575.

a(n,k)/A036040(n,k) and a(n,k)/A048996(n,k) are also integer sequences.

Apparently a(n,k)/A036040(n,k) = A178888(n,k). - R. J. Mathar, Apr 17 2011

Let f,g be functions from [n] into [n]. Let S_n be the symmetric group on n letters. Then f and g form the same partition iff S_nfS_n = S_ngS_n. - Geoffrey Critzer, Jan 13 2022

References

O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups, Springer, 2009, page38.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..2713 (rows 0..20)

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

Formula

a(n,k) = A036038(n,k) * A035206(n,k).

Example

Table begins:
  1;
  1;
  2,  2;
  3, 18,  6;
  4, 48, 36, 144, 24;
  ...
For n = 4, partition [3], we can map all three of {1,2,3} to any one of them, for 3 possible values. For n=5, partition [2,1], there are 3 choices for which element is alone in a preimage, 3 choices for which element to map that to and then 2 choices for which element to map the pair to, so a(5) = 3*3*2 = 18.

Mathematica

f[list_] := Multinomial @@ Join[{nn - Length[list]}, Table[Count[list, i], {i, 1, nn}]]*Multinomial @@ list; Table[nn = n; Map[f, IntegerPartitions[nn]], {n, 0, 10}] // Grid (* Geoffrey Critzer, Jan 13 2022 *)

Prog

(PARI)
C(sig)={my(S=Set(sig)); (binomial(vecsum(sig), #sig)) * (#sig)! * vecsum(sig)! / (prod(k=1, #S, (#select(t->t==S[k], sig))!) * prod(k=1, #sig, sig[k]!))}
Row(n)={apply(C, [Vecrev(p) | p<-partitions(n)])}
{ for(n=0, 7, print(Row(n))) } \\ Andrew Howroyd, Oct 18 2020

Crossrefs

Cf. A019575, A035206, A035796, A036038, A036040, A048996.

Row sizes A000041, sums A000312.

Sequence in context: A089751 A137909 A035796 * A101817 A058159 A058157

Adjacent sequences: A049006 A049007 A049008 * A049010 A049011 A049012

Keyword

nonn,tabf,easy

Author

Alford Arnold

Extensions

Better definition from Franklin T. Adams-Watters, May 30 2006

a(0)=1 prepended by Andrew Howroyd, Oct 18 2020

Status

approved