OFFSET
0,7
COMMENTS
From Kyle Petersen, Jun 02 2024: (Start)
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)
From L. Edson Jeffery, Jan 27 2012: (Start)
(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
Jane Ivy Coons and Seth Sullivant, The h*-polynomial of the order polytope of the zig-zag poset, arXiv:1901.07443 [math.CO], 2019.
L. E. Jeffery, Unit-primitive matrices
Hyeong-Kwan Ju, On the sequence generated by a certain type of matrices, Honam Math. J. 39, No. 4, 665-675 (2017).
Daeseok Lee and H.-K. Ju, An Extension of Hibi's palindromic theorem, arXiv preprint arXiv:1503.05658 [math.CO], 2015.
Peter Luschny, Illustrating the polynomials.
T. Kyle Petersen and Yan Zhuang, Zig-zag Eulerian polynomials, arXiv:2403.07181 [math.CO], 2024.
R. P. Stanley, Examples of Magic Labelings, Unpublished Notes, 1973 [Cached copy, with permission] See p. 31.
Guoce Xin and Yueming Zhong, Proving some conjectures on Kekulé numbers for certain benzenoids by using Chebyshev polynomials, arXiv:2201.02376 [math.CO], 2022.
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
From Kyle Petersen, Jun 02 2024: (Start)
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:
seq( coeffs(Zn(n)), n=0..15); # Kyle Petersen, Jun 02 2024
# 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)]];
Table[Rest@CoefficientList[Zn[n], x], {n, 0, 15}] // Flatten (* Jean-François Alcover, Jun 04 2024, after Kyle Petersen *)
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::]
print(A205497(9)) # Peter Luschny, Jun 14 2024
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
L. Edson Jeffery, Jan 27 2012
EXTENSIONS
Two 1's prepended and new name by Kyle Petersen Jun 02 2024
Edited by Peter Luschny, Jun 02 2024
STATUS
approved