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

Author

Alford Arnold

Keywords

• nonn
• tabf
• easy

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

Examples

			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.
		

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].

Crossrefs

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

Row sizes A000041, sums A000312.

Programs

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 *)

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

Formula

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

Extensions

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

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