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
Examples
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;
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.
Crossrefs
Programs
-
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
-
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 *) -
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
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
Extensions
Crossreferences corrected by Emeric Deutsch, May 09 2010
Comments