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

1, 1, 2, 5, 1, 22, 2, 114, 6, 697, 22, 1, 4923, 114, 3, 39612, 696, 12, 357899, 4923, 57, 1, 3588836, 39612, 348, 4, 39556420, 357900, 2460, 20, 475392841, 3588836, 19806, 116, 1, 6187284605, 39556420, 178950, 820, 5, 86701097310, 475392840, 1794420, 6600, 30

Offset

0,3

Comments

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

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

Links

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

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

Formula

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

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

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

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

Example

T(7,2)=3 because we have (123)(456)(7), (123)(4)(567), and (1)(234)(567).
Triangle starts:
    1;
    1;
    2;
    5,  1;
   22,  2;
  114,  6;
  697, 22,  1;

Maple

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

Mathematica

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

Prog

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

Crossrefs

Columns k=0..3 give A177251, A370525, A370528, A370530.

Cf. A000142, A000166, A008290, A177248, A177249, A177252, A177253.

Sequence in context: A343535 A047921 A242783 * A102786 A222637 A190950

Adjacent sequences: A177247 A177248 A177249 * A177251 A177252 A177253

Keyword

nonn,tabf

Author

Emeric Deutsch, May 07 2010

Extensions

Crossreferences corrected by Emeric Deutsch, May 09 2010

Status

approved