login
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.
17

%I #39 Jun 02 2021 05:16:21

%S 1,3,1,12,5,1,60,27,8,1,360,168,59,12,1,2520,1200,463,119,17,1,20160,

%T 9720,3978,1177,221,23,1,181440,88200,37566,12217,2724,382,30,1,

%U 1814400,887040,388728,135302,34009,5780,622,38,1,19958400,9797760,4385592,1606446,441383,86029,11378,964,47,1

%N 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.

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

%C For fixed k>=1, A185105(n,k) ~ n!*n/2^k. - _Vaclav Kotesovec_, Apr 25 2017

%H Alois P. Heinz, <a href="/A185105/b185105.txt">Rows n = 1..141, flattened</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>

%e The six permutations of n=3 in ordered cycle form are:

%e { {1}, {2}, {3} }

%e { {1}, {2, 3}, {} }

%e { {1, 2}, {3}, {} }

%e { {1, 2, 3}, {}, {}}

%e { {1, 3, 2}, {}, {}}

%e { {1, 3}, {2}, {} }

%e .

%e 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.

%e Triangle begins:

%e 1;

%e 3, 1;

%e 12, 5, 1;

%e 60, 27, 8, 1;

%e 360, 168, 59, 12, 1;

%e 2520, 1200, 463, 119, 17, 1;

%e 20160, 9720, 3978, 1177, 221, 23, 1;

%e 181440, 88200, 37566, 12217, 2724, 382, 30, 1;

%e ...

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

%p add((p-> p+coeff(p, x, 0)*j*x^i)(b(n-j, i+1))*

%p binomial(n-1, j-1)*(j-1)!, j=1..n)))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 1)):

%p seq(T(n), n=1..12); # _Alois P. Heinz_, Apr 15 2017

%t Table[it = Join[RotateRight /@ ToCycles[#], Table[{}, {k}]] & /@ Permutations[Range[n]]; Tr[Length[Part[#, k]]& /@ it], {n, 7}, {k, n}]

%t (* Second program: *)

%t 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 T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, 1]];

%t Array[T, 12] // Flatten (* _Jean-François Alcover_, May 30 2018, after _Alois P. Heinz_ *)

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

%Y T(2n,n) gives A285239.

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

%K nonn,tabl

%O 1,2

%A _Wouter Meeussen_, Dec 26 2012

%E More terms from _Alois P. Heinz_, Apr 15 2017