

A205497


Triangle read by rows: Zigzag Eulerian number triangle T(n, k).


21



1, 1, 1, 1, 1, 1, 3, 1, 1, 7, 7, 1, 1, 14, 31, 14, 1, 1, 26, 109, 109, 26, 1, 1, 46, 334, 623, 334, 46, 1, 1, 79, 937, 2951, 2951, 937, 79, 1, 1, 133, 2475, 12331, 20641, 12331, 2475, 133, 1, 1, 221, 6267, 47191, 123216, 123216, 47191, 6267, 221, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,7


COMMENTS

Coefficients of the "PEulerian" polynomial of a naturally labeled zigzag poset, which counts linear extensions according to number of descents. T(n, k) is the number of linear extensions of the nelement zigzag poset with k descents.
Also T(n, k) is the number of updown permutations of length n with k "big returns". A big return is a pair (i, i+1) for which i appears more than one place to the right of i+1 in the permutation. This interpretation implies row sums are given by A000111. (End)
(Previous name:) Omitting the first two ones, a rectangular array M read by antidiagonals in which entry M_{nk, k} in row nk and column k, 0 <= k <= n, gives the coefficient of x^k in the numerator of the conjectured generating function for row n + 3 of the tabular form of A050446.
In the following, let M_{n, k} denote the entry in row n and column k of M, n, k in {0, 1, ...}.
Conjecture: 1. M_{n, k) = M_{k, n), for all n and k; that is, M is symmetric about the central terms {1, 3, 31, 623,...}. (This has been verified for the first 100 antidiagonals of M.)
Conjecture: 2. For m in {3, 4,...}, row m of array A050446 has generating function of the form H_m(x)/(1  x)^m, in which the numerator H_m(x) is a polynomial of degree m  3 in x with coefficients given by the entries of the (m  3)th antidiagonal of M containing the sequence of entries {M_{m3j,j}}, j=0..m3 (see the example below). It is known that H_1(x) = H_2(x) = 1.
Conjecture: 3. Define the Chebyshev polynomials of the second kind by U_0(t) = 1, U_1(t) = 2*t and U_r(t) = 2*t*U_(r1)(t)  U_(r2)(t) (r > 1). Assuming Conjecture 1, lim_{n > infinity} M_{n+1, k}/M_{n, k} = U_k(cos(Pi/(2*k+3))) = spectral radius of the (k+1) X (k+1) unitprimitive matrix (see [Jeffery]) A_{2*k+3, k} = [0,...,0,1; 0,...,0,1,1; ...; 0,1,...,1; 1,...,1], with identical limits for the columns of the transpose M^T of M.
Conjecture: 4. Let S(u, v) denote the entry in row u and column v of triangle S = A187660, 0 <= v <= u. Define the polynomials P_u(x) = Sum[S(u, v)*x^v]. Assuming Conjecture 1, then (i) the generating function for row (or column) n of M is of the form
G_n(x)/((P_1(x))^(n+1) * (P_2(x))^n * ... * (P_n(x))^2 * P_(n+1)(x)),
in which (ii) the numerator G_n(x) is a polynomial of degree A005586(n), and (iii) the denominator is a polynomial of degree A000292(n+1).
Remarks: The coefficients in the numerators G_n(x) appear to have no pattern. The polynomial P_j(x), j in {1,...,n+1}, of Conjecture 4 is also obtained from the characteristic polynomial of the unitprimitive matrix A_{2*j+3,j} of Conjecture 3 by taking the exponents of the latter in reverse order; and P_j(x) is otherwise identical to the characteristic polynomial of the unitprimitive matrix A_{2*j+3,1}.
(End)
Conjecture: The Eulerian zigzag polynomials have only negative and simple real roots and form a Sturm sequence, that is, p(n+1, x) has n real roots separated by the roots of p(n, x). This property was proved by Frobenius for the classical Eulerian polynomials.  Peter Luschny, Jun 04 2024


LINKS



FORMULA

Conjecture: 5.1. G.f. for column 0 of M is 1/(1x) (A000012).
Conjecture: 5.2. G.f. for column 1 of M is 1/((1x)^2*(1xx^2)) (A001924).
Conjecture: 5.3. G.f. for column 2 of M is (1  x^2  x^3  x^4 + x^5)/((1x)^3*(1xx^2)^2*(1  2*x  x^2 + x^3)) (A205492).
Conjecture: 5.4. G.f. for column 3 of M is (1 + x  6*x^2  15*x^3 + 21*x^4 + 35*x^5  13*x^6  51*x^7 + 3*x^8 + 21*x^9 + 5*x^10 + x^11  5*x^12  x^13  x^14)/((1x)^4*(1xx^2)^3*(1  2*x  x^2 + x^3)^2*(1  2*x  3*x^2 + x^3 + x^4)) (A205493).
Conjecture: 5.5. G.f. for column 4 of M is (1 + 4*x  31*x^2  67*x^3 + 348*x^4 + 418*x^5  1893*x^6  1084*x^7 + 4326*x^8 + 4295*x^9  7680*x^10  9172*x^11 + 9104*x^12 + 11627*x^13  5483*x^14  10773*x^15 + 1108*x^16 + 7255*x^17 + 315*x^18  3085*x^19  228*x^20 + 669*x^21 + 102*x^22  23*x^23  45*x^24  16*x^25 + 11*x^26 + 2*x^27  x^28)/((1x)^5*(1xx^2)^4*(1  2*x  x^2 + x^3)^3*(1  2*x  3*x^2 + x^3 + x^4)^2*(1  3*x  3*x^2 + 4*x^3 + x^4  x^5)) (A205494).


EXAMPLE

Triangle T(n, k) begins:
1;
1;
1;
1, 1;
1, 3, 1;
1, 7, 7, 1;
1, 14, 31, 14, 1;
1, 26, 109, 109, 26, 1;
1, 46, 334, 623, 334, 46, 1;
1, 79, 937, 2951, 2951, 937, 79, 1;
...
For n=4, the naturally labeled zigzag poset 1<3>2<4 has five linear extensions: 1234, 1243, 2134, 2143, 2413, and their descent numbers are (respectively) 0, 1, 1, 2, 1. Thus T(4,0) = 1, T(4,1) = 3, and T(4,2) = 1. Also with n=4, there are five updown permutations: 1324, 1423, 2314, 2413, 3412, and their big return numbers are (respectively) 0, 1, 1, 2, 1. (End)
Without the first two ones the data can be seen as an array M read by antidiagonals. Christopher H. Gribble kindly calculated the first 100 antidiagonals which starts as:
1, 1, 1, 1, 1, 1, ...
1, 3, 7, 14, 26, 46, ...
1, 7, 31, 109, 334, 937, ...
1, 14, 109, 623, 2951, 12331, ...
1, 26, 334, 2951, 20641, 123216, ...
1, 46, 937, 12331, 123216, 1019051, ...
...
The antidiagonals of M written as the rows of a triangle, yielding then, by the conjectures and the definition of H_m(x), row m = 7 of table A050446 has generating function H_7(x)/(1x)^7 = (Sum_{j=0..4} M_{4j,j}*x^j)/(1x)^7 = (1 + 14*x + 31*x^2 + 14*x^3 + x^4)/(1x)^7.


MAPLE

Gn := proc(n) local F;
if n = 0 then p*q*x/(1  q*x);
elif n > 0 then
F := Gn(n  1);
simplify(p/(p  q)*(subs({p = q, q = p}, F)  subs(p = q, F)));
fi;
end:
Zn := proc(n) expand(simplify(subs({p = 1, q = 1}, Gn(n))*(1  x)^(n + 1))) end:
# Alternative:
A205497row := proc(n) local k, j; ifelse(n < 2, 1,
seq(add((1)^j * binomial(n + 1, j) * A050446(n, k  j), j = 0..k), k = 0..n2)) end: # Peter Luschny, Jun 17 2024


MATHEMATICA

Gn[n_] := Module[{F}, If[n == 0, p*q*x/(1q*x), If[n > 0, F = Gn[n1]; Simplify[p/(pq)*(ReplaceAll[F, {p > q, q > p}]  ReplaceAll[F, p > q])]]]];
Zn[n_] := Expand[Simplify[ReplaceAll[Gn[n], {p > 1, q > 1}]*(1x)^(n+1)]];


PROG

(Python)
from functools import cache
from math import comb as binomial
@cache
def S(n, k):
return (S(n, k  1) + sum(S(2 * j, k  1) * S(n  1  2 * j, k)
for j in range(1 + (n  1) // 2)) if k > 0 else 1)
def A205497(dim): # returns [row(0), ..., row(dim1)]
if dim < 4: return [[1]] * dim
Y = [[0 for _ in range(n  2)] for n in range(dim + 1)]
for n in range(dim + 1):
for k in range(n  2):
for j in range(k + 1):
Y[n][k] += (1)**j * binomial(n, j) * S(n  1, k  j)
Y[1] = Y[2] = [1]
return Y[1::]


CROSSREFS



KEYWORD

nonn,tabf


AUTHOR



EXTENSIONS



STATUS

approved



