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

Author

Emeric Deutsch, Feb 16 2011 (based on communication from Vladeta Jovovic)

Keywords

• nonn
• tabl

Comments

Sum of entries in row n is n!.

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

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

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

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

Crossrefs

Cf. A007489, A013999, A184185.

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.