OFFSET
0,3
COMMENTS
This is a refinement of 1; 2,2; 3,18,6; 4,84,144,24; ... cf. A019575.
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].
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, so a(4) = 3.
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.
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
KEYWORD
nonn,tabf,easy
AUTHOR
EXTENSIONS
Better definition from Franklin T. Adams-Watters, May 30 2006
a(0)=1 prepended by Andrew Howroyd, Oct 18 2020
STATUS
approved
