A185105 Number T(n,k) of entries in the k-th cycles of all permutations of {1,2,..,n}; each cycle is written with the smallest element first and cycles are arranged in increasing order of their first elements.

1, 3, 1, 12, 5, 1, 60, 27, 8, 1, 360, 168, 59, 12, 1, 2520, 1200, 463, 119, 17, 1, 20160, 9720, 3978, 1177, 221, 23, 1, 181440, 88200, 37566, 12217, 2724, 382, 30, 1, 1814400, 887040, 388728, 135302, 34009, 5780, 622, 38, 1, 19958400, 9797760, 4385592, 1606446, 441383, 86029, 11378, 964, 47, 1

Offset

1,2

Comments

Row sums are n!*n = A001563(n) (see example).

For fixed k>=1, A185105(n,k) ~ n!*n/2^k. - Vaclav Kotesovec, Apr 25 2017

Links

Alois P. Heinz, Rows n = 1..141, flattened

Wikipedia, Permutation

Example

The six permutations of n=3 in ordered cycle form are:
{ {1}, {2}, {3}    }
{ {1}, {2, 3}, {}  }
{ {1, 2}, {3}, {}  }
{ {1, 2, 3}, {}, {}}
{ {1, 3, 2}, {}, {}}
{ {1, 3}, {2}, {}  }
.
The lengths of the cycles in position k=1 sum to 12, those of the cycles in position k=2 sum to 5 and those of the cycles in position k=3 sum to 1.
Triangle begins:
       1;
       3,     1;
      12,     5,     1;
      60,    27,     8,     1;
     360,   168,    59,    12,    1;
    2520,  1200,   463,   119,   17,   1;
   20160,  9720,  3978,  1177,  221,  23,  1;
  181440, 88200, 37566, 12217, 2724, 382, 30, 1;
  ...

Maple

b:= proc(n, i) option remember; expand(`if`(n=0, 1,
      add((p-> p+coeff(p, x, 0)*j*x^i)(b(n-j, i+1))*
       binomial(n-1, j-1)*(j-1)!, j=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 1)):
seq(T(n), n=1..12);  # Alois P. Heinz, Apr 15 2017

Mathematica

Table[it = Join[RotateRight /@ ToCycles[#], Table[{}, {k}]] & /@ Permutations[Range[n]]; Tr[Length[Part[#, k]]& /@ it], {n, 7}, {k, n}]
(* Second program: *)
b[n_, i_] := b[n, i] = Expand[If[n==0, 1, Sum[Function[p, p + Coefficient[ p, x, 0]*j*x^i][b[n-j, i+1]]*Binomial[n-1, j-1]*(j-1)!, {j, 1, n}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, 1]];
Array[T, 12] // Flatten (* Jean-François Alcover, May 30 2018, after Alois P. Heinz *)

Crossrefs

Columns k=1-10 give: A001710(n+1), A138772, A159324(n-1)/2 or A285231, A285232, A285233, A285234, A285235, A285236, A285237, A285238.

T(2n,n) gives A285239.

Cf. A000142, A001563, A270236, A284816, A285439.

Sequence in context: A162995 A177020 A226167 * A122844 A113369 A249253

Adjacent sequences: A185102 A185103 A185104 * A185106 A185107 A185108

Keyword

nonn,tabl

Author

Wouter Meeussen, Dec 26 2012

Extensions

More terms from Alois P. Heinz, Apr 15 2017

Status

approved