|
| |
|
|
A205497
|
|
Triangle read by rows: Zig-zag 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 "P-Eulerian" polynomial of a naturally labeled zig-zag poset, which counts linear extensions according to number of descents. T(n, k) is the number of linear extensions of the n-element zig-zag poset with k descents.
Also T(n, k) is the number of up-down 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_{n-k, k} in row n-k 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_{m-3-j,j}}, j=0..m-3 (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_(r-1)(t) - U_(r-2)(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) unit-primitive 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 unit-primitive 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 unit-primitive matrix A_{2*j+3,1}.
(End)
Conjecture: The Eulerian zig-zag 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/(1-x) (A000012).
Conjecture: 5.2. G.f. for column 1 of M is 1/((1-x)^2*(1-x-x^2)) (A001924).
Conjecture: 5.3. G.f. for column 2 of M is (1 - x^2 - x^3 - x^4 + x^5)/((1-x)^3*(1-x-x^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)/((1-x)^4*(1-x-x^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)/((1-x)^5*(1-x-x^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 zig-zag 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 up-down 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)/(1-x)^7 = (Sum_{j=0..4} M_{4-j,j}*x^j)/(1-x)^7 = (1 + 14*x + 31*x^2 + 14*x^3 + x^4)/(1-x)^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..n-2)) end: # Peter Luschny, Jun 17 2024
|
|
|
MATHEMATICA
|
Gn[n_] := Module[{F}, If[n == 0, p*q*x/(1-q*x), If[n > 0, F = Gn[n-1]; Simplify[p/(p-q)*(ReplaceAll[F, {p -> q, q -> p}] - ReplaceAll[F, p -> q])]]]];
Zn[n_] := Expand[Simplify[ReplaceAll[Gn[n], {p -> 1, q -> 1}]*(1-x)^(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(dim-1)]
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
|
| |
|
|
