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,3

Links

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

Example

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.

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

Crossrefs

Cf. A120774.

Row sums of A285849.

Sequence in context: A000166 A093464 A308338 * A347571 A331559 A184932

Adjacent sequences: A196298 A196299 A196300 * A196302 A196303 A196304

Keyword

nonn

Author

Geoffrey Critzer, Sep 30 2011

Status

approved