login
The number of ways to linearly order the cycles in each permutation of {1,2,...,n} where two cycles are considered identical if they have the same length.
3

%I #16 Apr 28 2017 09:16:00

%S 1,1,2,9,44,270,2139,18837,186808,2070828,25861140,350000640,

%T 5145279611,81492295079,1381583542234,25097285838765,484602684624080,

%U 9894705390149400,213418984780492164,4842425874827849868,115231446547162291200,2874808892527026177240

%N The number of ways to linearly order the cycles in each permutation of {1,2,...,n} where two cycles are considered identical if they have the same length.

%H Alois P. Heinz, <a href="/A196301/b196301.txt">Table of n, a(n) for n = 0..444</a>

%e a(4) = 44 because in the conjugacy classes of S(4): (4), (3)(1), (2)(2), (2)(1)(1), (1)(1)(1)(1) there are (respectively) 6 permutations times 1 arrangement, 8 permutations times 2 arrangements, 3 permutations times 1 arrangement, 6 permutations times 3 arrangements, and 1 permutation times 1 arrangement. So 6*1+8*2+3*1+6*3+1*1 = 44.

%p b:= proc(n, i, p) option remember; `if`(n=0 or i=1,

%p (p+n)!/n!, add(b(n-i*j, i-1, p+j)*(i-1)!^j*combinat

%p [multinomial](n, n-i*j, i$j)/j!^2, j=0..n/i))

%p end:

%p a:= n-> b(n$2, 0):

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Apr 27 2017

%t Needs["Combinatorica`"]; f[{x_, y_}]:= x^y y!; Table[Total[Table[n!, {PartitionsP[n]}]/Apply[Times, Map[f, Map[Tally, Partitions[n]], {2}], 2] * Apply[Multinomial, Map[Last, Map[Tally, Partitions[n]], {2}], 2]], {n, 0, 20}]

%Y Cf. A120774.

%Y Row sums of A285849.

%K nonn

%O 0,3

%A _Geoffrey Critzer_, Sep 30 2011