|
|
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)<p(i+1).
|
|
18
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Row sums are the factorials (A000142).
T(n,1) = T(n,n) = A000111(n) (Euler or up-down numbers).
Sum(k*T(n,k), k=1..n) = (n+1)!/2 = A001710(n+1).
Koutras has defined generalized Eulerian numbers associated with a sequence of polynomials - the ordinary Eulerian numbers A008292 being associated with the sequence of monomials x^n. The present array is the triangle of Eulerian numbers associated with the sequence of zigzag polynomials Z(n,x) defined in A147309.
See A109449, A147315 and A185424 for the respective analogs of the Pascal triangle, the Stirling numbers of the second kind and the Bernoulli numbers, associated with the sequence of zigzag polynomials. (End)
In general, for fixed k>=1, T(n,k) ~ (4-Pi)^(k-1) * 2^(n+2) * n^(k-1) * n! / ((k-1)! * Pi^(n + k)).
Equivalently, for fixed k>=1, T(n,k) ~ (4-Pi)^(k-1) * 2^(n + 5/2) * n^(n + k - 1/2) / ((k-1)! * Pi^(n + k - 1/2) * exp(n)). (End)
|
|
LINKS
|
|
|
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).
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)
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)
|
|
EXAMPLE
|
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;
...
|
|
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)):
|
|
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]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|