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

1, 1, 2, 9, 44, 270, 2139, 18837, 186808, 2070828, 25861140, 350000640, 5145279611, 81492295079, 1381583542234, 25097285838765, 484602684624080, 9894705390149400, 213418984780492164, 4842425874827849868, 115231446547162291200, 2874808892527026177240

Offset: 0

Author

Geoffrey Critzer, Sep 30 2011

Keywords

• nonn

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..444

Crossrefs

Cf. A120774.

Row sums of A285849.

Programs

Maple

b:= proc(n, i, p) option remember; `if`(n=0 or i=1,
      (p+n)!/n!, add(b(n-i*j, i-1, p+j)*(i-1)!^j*combinat
      [multinomial](n, n-i*j, i$j)/j!^2, j=0..n/i))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..25);  # Alois P. Heinz, Apr 27 2017

Mathematica

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