A145876
Triangle read by rows: T(n,k) is the number of permutations of [n] having k-1 alternating descents (1<=k<=n). The index i is an alternating descent of a permutation p if either i is odd and p(i)>p(i+1), or i is even and p(i)
1, 1, 1, 2, 2, 2, 5, 7, 7, 5, 16, 26, 36, 26, 16, 61, 117, 182, 182, 117, 61, 272, 594, 1056, 1196, 1056, 594, 272, 1385, 3407, 6669, 8699, 8699, 6669, 3407, 1385, 7936, 21682, 46348, 67054, 76840, 67054, 46348, 21682, 7936, 50521, 151853, 350240, 556952, 704834, 704834, 556952, 350240, 151853, 50521
Offset: 1
Examples
T(4,3) = 7 because we have 1243, 4123, 1342, 3124, 2134, 2341 and 4321. For example, for p=1342 the alternating descent is {2,3}; indeed, 2 is even and p(2)=3 < p(3)=4, while 3 is odd and p(3)=4 > p(4)=2.
Triangle starts:
1;
1, 1;
2, 2, 2;
5, 7, 7, 5;
16, 26, 36, 26, 16;
61, 117, 182, 182, 117, 61;
272, 594, 1056, 1196, 1056, 594, 272;
1385, 3407, 6669, 8699, 8699, 6669, 3407, 1385;
...
Links
- Alois P. Heinz, Table of n, a(n) for n = 1..141, flattened
- D. Chebikin, Variations on descents and inversions in permutations, The Electronic J. of Combinatorics, 15 (2008), #R132.
- M. V. Koutras, Eulerian numbers associated with sequences of polynomials, The Fibonacci Quarterly, 32 (1994), 44-57.
- Shi-Mei Ma, Qi Fang, Toufik Mansour, and Yeong-Nan Yeh, Alternating Eulerian polynomials and left peak polynomials, arXiv:2104.09374 [math.CO], 2021.
- S.-M. Ma and Y.-M. Yeh, Enumeration of permutations by number of alternating descents, Discr. Math., 339 (2016), 1362-1367.
Crossrefs
Programs
-
Maple
F:=t*(1-tan(u*(t-1))-sec(u*(t-1)))/(tan(u*(t-1))+sec(u*(t-1))-t): Fser:= simplify(series(F,u=0,12)): for n from 0 to 10 do P[n]:=sort(expand(factorial(n)*coeff(Fser,u,n))) end do: for n to 10 do seq(coeff(P[n],t,j),j=1..n) end do; # yields sequence in triangular form # second Maple program: b:= proc(u, o) option remember; expand(`if`(u+o=0, 1, add(b(o+j-1, u-j)*x, j=1..u)+ add(b(o-j, u-1+j), j=1..o))) end: T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 0)): seq(T(n), n=1..12); # Alois P. Heinz, Nov 18 2013, Apr 15 2018 -
Mathematica
b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Expand[ Sum[b[u+j-1, o-j, !t]*If[t, 1, x], {j, 1, o}] + Sum[b[u-j, o+j-1, !t]*If[t, x, 1], {j, 1, u}]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, n-1}]][b[0, n, True]]; Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Feb 19 2015, after Alois P. Heinz *)
Formula
E.g.f.: F(t,u) = t*(1-tan(u*(t-1))-sec(u*(t-1)))/(tan(u*(t-1))+sec(u*(t-1))-t).
From Peter Bala, Jun 11 2011: (Start)
T(n,k) = Sum_{j = 0..k} (-1)^(k-j)*binomial(n+1,k-j)*Z(n,j), where Z(n,x) are the zigzag polynomials defined in A147309.
Let M denote the triangular array A109449. The first column of the array (I-x*M)^-1 is a sequence of rational functions in x whose numerator polynomials are the row polynomials of the present array.
(End)
From Vladimir Shevelev, Jul 01 2011: (Start)
a(2^(2*n-1)-2^(n-1)+1) == 1 (mod 2^n).
If n is odd prime, then a(2*n^2-n+1) == 1 (mod 2*n) and a((n^2-n+2)/2) == (-1)^((n-1)/2).
(End)
Comments