A285231 -id:A285231 - cp's OEIS frontend

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

Wouter Meeussen, Dec 26 2012

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

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

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

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.

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

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 *)

More terms from Alois P. Heinz, Apr 15 2017

A159324 n! times the average number of comparisons required by an insertion sort of n (distinct) elements.

Original entry on oeis.org

0, 0, 2, 16, 118, 926, 7956, 75132, 777456, 8771184, 107307360, 1416252960, 20068629120, 304002322560, 4903642679040, 83928856838400, 1519397749094400, 29010025797580800, 582647327132774400, 12280347845905305600, 271030782903552000000, 6251213902855219200000

Offset: 0

Harmen Wassenaar (towr(AT)ai.rug.nl), Apr 10 2009

nonn

			For n=3, insertion sorting 123, 213, 213, 231, 312, 321 takes 3+3+3+2+3+2 = 4*3+2*2 = 16 comparisons.

Alois P. Heinz, Table of n, a(n) for n = 0..448
Wikipedia, Insertion sort
Index entries for sequences related to sorting

Row sums of triangle A159323.

Cf. A000254, A001008, A002805, A138772, A212395, A285231.

a:= proc(n) option remember;
      `if`(n<2, 0, a(n-1)*n + (n-1)! * (n-1)*(n+2)/2)
    end:
seq(a(n), n=0..30); # Alois P. Heinz, May 14 2012
# second Maple program:
a:= proc(n) option remember; `if`(n<3, [0$2, 2][n+1],
      ((2*n^3-n^2-5*n+2)*a(n-1)-(n+2)*(n-1)^3*a(n-2))/((n-2)*(n+1)))
    end:
seq(a(n), n=0..30); # Alois P. Heinz, Dec 16 2016

a[n_] := n! ((n+1)(n+2)/4 - HarmonicNumber[n] - 1/2); Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Apr 12 2017, after Gary Detlefs *)

a(n) = a(n-1)*(n) + n! *(n+1)/2 - (n-1)!.
a(n) = Sum_k A159323(n,k) = Sum_k A129178(n,k) * (n(n-1)/2 - k).
a(n) = n!/4 *(n^2+3*n-4*H(n)), where H(n) = Sum_{k=1..n} 1/k. - Gary Detlefs, Sep 02 2010
a(n) = A138772(n+1) - A000254(n). - Gary Detlefs, May 13 2012
a(n) = ((2*n^3-n^2-5*n+2)*a(n-1)-(n+2)*(n-1)^3*a(n-2))/((n-2)*(n+1)) for n>2. - Alois P. Heinz, Dec 16 2016
a(n) = 2 * A285231(n+1). - Alois P. Heinz, Apr 15 2017

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions