A184184 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, 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, 1566, 1824, 1068, 420, 125, 30, 6, 1, 12840, 14664, 8400, 3220, 930, 216, 42, 7, 1, 117696, 132360, 74580, 28080, 7950, 1806, 343, 56, 8, 1, 1193760, 1326120, 737640, 273960, 76440, 17094, 3192, 512, 72, 9, 1
Offset: 0
Examples
T(3,2) = 2 because we have (1)(23) and (12)(3). T(4,2) = 6 because we have (1)(234), (1)(24)(3), (12)(34), (123)(4), (14)(2)(3), and (13)(2)(4). Triangle starts: 1; 0, 1; 0, 1, 1; 1, 2, 2, 1; 6, 8, 6, 3, 1; 34, 42, 27, 12, 4, 1;
Links
- FindStat - Combinatorial Statistic Finder, The number of adjacent cycles of a permutation
Programs
-
Maple
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
Formula
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).
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).
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.
Comments