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,8

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

Links

Table of n, a(n) for n=0..65.

FindStat - Combinatorial Statistic Finder, The number of adjacent cycles of a permutation

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.

Example

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;

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

Crossrefs

Cf. A007489, A013999, A184185.

Sequence in context: A077873 A123305 A118024 * A074297 A339604 A020824

Adjacent sequences: A184181 A184182 A184183 * A184185 A184186 A184187

Keyword

nonn,tabl

Author

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

Status

approved