cp's OEIS Frontend

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.

%I A049009 #31 Jan 18 2022 06:00:16
%S A049009 1,1,2,2,3,18,6,4,48,36,144,24,5,100,200,600,900,1200,120,6,180,450,
%T A049009 300,1800,7200,1800,7200,16200,10800,720,7,294,882,1470,4410,22050,
%U A049009 14700,22050,29400,176400,88200,88200,264600,105840,5040,8,448,1568,3136,1960
%N 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.
%C A049009 a(n,k) is a refinement of 1; 2,2; 3,18,6; 4,84,144,24; ... cf. A019575.
%C A049009 a(n,k)/A036040(n,k) and a(n,k)/A048996(n,k) are also integer sequences.
%C A049009 Apparently a(n,k)/A036040(n,k) = A178888(n,k). - _R. J. Mathar_, Apr 17 2011
%C A049009 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
%D A049009 O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups, Springer, 2009, page38.
%H A049009 Andrew Howroyd, <a href="/A049009/b049009.txt">Table of n, a(n) for n = 0..2713</a> (rows 0..20)
%H A049009 M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
%F A049009 a(n,k) = A036038(n,k) * A035206(n,k).
%e A049009 Table begins:
%e A049009   1;
%e A049009   1;
%e A049009   2,  2;
%e A049009   3, 18,  6;
%e A049009   4, 48, 36, 144, 24;
%e A049009   ...
%e A049009 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.
%t A049009 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 *)
%o A049009 (PARI)
%o A049009 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]!))}
%o A049009 Row(n)={apply(C, [Vecrev(p) | p<-partitions(n)])}
%o A049009 { for(n=0, 7, print(Row(n))) } \\ _Andrew Howroyd_, Oct 18 2020
%Y A049009 Cf. A019575, A035206, A035796, A036038, A036040, A048996.
%Y A049009 Row sizes A000041, sums A000312.
%K A049009 nonn,tabf,easy
%O A049009 0,3
%A A049009 _Alford Arnold_
%E A049009 Better definition from _Franklin T. Adams-Watters_, May 30 2006
%E A049009 a(0)=1 prepended by _Andrew Howroyd_, Oct 18 2020