login
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).
10
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
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. A000142 (row sums).
Sequence in context: A264319 A264173 A220183 * A168270 A222761 A298817
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, May 07 2010
STATUS
approved