A177252 Triangle read by rows: T(n,k) is the number of permutations of [n] having k adjacent 4-cycles (0 <= k <= floor(n/4)), i.e., having k cycles of the form (i, i+1, i+2, i+3).

1, 1, 2, 6, 23, 1, 118, 2, 714, 6, 5016, 24, 40201, 118, 1, 362163, 714, 3, 3623772, 5016, 12, 39876540, 40200, 60, 478639079, 362163, 357, 1, 6223394516, 3623772, 2508, 4, 87138394540, 39876540, 20100, 20, 1307195547720, 478639080, 181080, 120

Offset

0,3

Comments

Row n contains 1 + floor(n/4) entries.

Sum of entries in row n = n! (A000142).

Links

Seiichi Manyama, Rows n = 0..200, flattened

R. A. Brualdi and E. Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.

Formula

T(n,k) = Sum_{j=0..floor(n/4)} (-1)^(k+j)*binomial(j,k)*(n-3*j)!/j!.

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

Sum_{k>=0} k*T(n,k) = (n-3)! (n >= 4).

G.f. of column k: (1/k!) * Sum_{j>=k} j! * x^(j+3*k) / (1+x^4)^(j+1). - Seiichi Manyama, Feb 24 2024

Example

T(9,2)=3 because we have (1234)(5678)(9), (1234)(5)(6789), and (1)(2345)(6789).
Triangle starts:
     1;
     1;
     2;
     6;
    23,  1;
   118,  2;
   714,  6;
  5016, 24;

Maple

T := proc (n, k) options operator, arrow: sum((-1)^(k+j)*binomial(j, k)*factorial(n-3*j)/factorial(j), j = 0 .. floor((1/4)*n)) end proc: for n from 0 to 15 do seq(T(n, k), k = 0 .. floor((1/4)*n)) end do; % yields sequence in triangular form

Mathematica

T[n_, k_]:= T[n, k]= Sum[(-1)^(k+j)*Binomial[j, k]*(n-3 j)!/j!, {j, 0, n/4}];
Table[T[n, k], {n, 0, 15}, {k, 0, n/4}] // Flatten (* Jean-François Alcover, Nov 17 2017 *)

Prog

(Magma)
A177252:= func< n, k | (&+[(-1)^j*Factorial(n-3*k-3*j)/(Factorial(k) *Factorial(j)): j in [0..Floor((n-4*k)/4)]]) >;
[A177252(n, k): k in [0..Floor(n/4)], n in [0..20]]; // G. C. Greubel, Apr 28 2024
(SageMath)
def A177252(n, k): return sum((-1)^j*factorial(n-3*k-3*j)/(factorial(k) *factorial(j)) for j in range(1+(n-4*k)//4))
flatten([[A177252(n, k) for k in range(1+n//4)] for n in range(21)]) # G. C. Greubel, Apr 28 2024

Crossrefs

Columns k=0-3 give A177253, A369098, A370652, A370653.

Cf. A000166, A008290, A177248, A177249, A177250, A177251.

Cf. A000142 (row sums).

Sequence in context: A264319 A264173 A220183 * A168270 A222761 A298817

Adjacent sequences: A177249 A177250 A177251 * A177253 A177254 A177255

Keyword

nonn,tabf

Author

Emeric Deutsch, May 07 2010

Status

approved