login
Triangle read by rows: T(n,k) is the number of permutations of [n] having k adjacent cycles (0 <= k <= n). An adjacent cycle is a cycle of the form (i, i+1, i+2, ...) (including 1-element cycles).
1

%I #20 Nov 03 2019 19:41:26

%S 1,0,1,0,1,1,1,2,2,1,6,8,6,3,1,34,42,27,12,4,1,216,258,156,64,20,5,1,

%T 1566,1824,1068,420,125,30,6,1,12840,14664,8400,3220,930,216,42,7,1,

%U 117696,132360,74580,28080,7950,1806,343,56,8,1,1193760,1326120,737640,273960,76440,17094,3192,512,72,9,1

%N Triangle read by rows: T(n,k) is the number of permutations of [n] having k adjacent cycles (0 <= k <= n). An adjacent cycle is a cycle of the form (i, i+1, i+2, ...) (including 1-element cycles).

%C Sum of entries in row n is n!.

%C T(n,0) = A184185(n).

%C T(n,1) = A013999(n-1).

%C Sum_{k>=0} k*T(n,k) = 1! + 2! + ... + n! = A007489(n).

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/St000153/">The number of adjacent cycles of a permutation</a>

%F G.f. of column k is (1/k!)*z^k*(1-z)*Sum_{i>=0} (k+i)!*(z-z^2)^i (private communication from _Vladeta Jovovic_, May 26 2009).

%F T(n,k) = (1/k!)*Sum_{i=ceiling((n-k-1)/2)..n-k} (-1)^(n-k-i)*(k+i)!*binomial(i+1, n-k-i).

%F The bivariate g.f. is G(t,z) = ((1-z)/(1-tz))*F((z-z^2)/(1-tz)), where F(z) = Sum_{j>=0} j!*z^j.

%e T(3,2) = 2 because we have (1)(23) and (12)(3).

%e T(4,2) = 6 because we have (1)(234), (1)(24)(3), (12)(34), (123)(4), (14)(2)(3), and (13)(2)(4).

%e Triangle starts:

%e 1;

%e 0, 1;

%e 0, 1, 1;

%e 1, 2, 2, 1;

%e 6, 8, 6, 3, 1;

%e 34, 42, 27, 12, 4, 1;

%p T := proc (n, k) options operator, arrow: add((-1)^(n-k-i)*factorial(k+i)*binomial(i+1, n-k-i), i = ceil((1/2)*n-(1/2)*k-1/2) .. n-k)/factorial(k) end proc: for n from 0 to 10 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form

%Y Cf. A007489, A013999, A184185.

%K nonn,tabl

%O 0,8

%A _Emeric Deutsch_, Feb 16 2011 (based on communication from _Vladeta Jovovic_)