cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A205497 Triangle read by rows: Zig-zag Eulerian number triangle T(n, k).

Original entry on oeis.org

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
Offset: 0

Views

Author

L. Edson Jeffery, Jan 27 2012

Keywords

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

Examples

			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.

Links

Crossrefs

Cf. A000012, A000292, A001924, A050446, A050447, A187660, row sums are A000111.
Cf. A350354, A373388, A373389.

Programs

  • 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 *)
  • 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

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).

Extensions

Two 1's prepended and new name by Kyle Petersen Jun 02 2024
Edited by Peter Luschny, Jun 02 2024

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.