cp's OEIS Frontend

Triangle T(n,k), 0 <= k <= n, read by rows given by [0,1,0,2,0,3,0,4,0,5,0,6,0,7,0,...] DELTA [1,1,2,2,3,3,4,4,5,5,6,6,...] where DELTA is the operator defined in A084938; another version of A019538.

See also A019538: version with n > 0 and k > 0. - Philippe Deléham, Nov 03 2008

From Peter Bala, Jul 21 2014: (Start)

T(n,k) gives the number of (k-1)-dimensional faces in the interior of the first barycentric subdivision of the standard (n-1)-dimensional simplex. For example, the barycentric subdivision of the 1-simplex is o--o--o, with 1 interior vertex and 2 interior edges, giving T(2,1) = 1 and T(2,2) = 2.

This triangle is used when calculating the face vectors of the barycentric subdivision of a simplicial complex. Let S be an n-dimensional simplicial complex and write f_k for the number of k-dimensional faces of S, with the usual convention that f_(-1) = 1, so that F := (f_(-1), f_0, f_1,...,f_n) is the f-vector of S. If M(n) denotes the square matrix formed from the first n+1 rows and n+1 columns of the present triangle, then the vector F*M(n) is the f-vector of the first barycentric subdivision of the simplicial complex S (Brenti and Welker, Lemma 2.1). For example, the rows of Pascal's triangle A007318 (but with row and column indexing starting at -1) are the f-vectors for the standard n-simplexes. It follows that A007318*A131689, which equals A028246, is the array of f-vectors of the first barycentric subdivision of standard n-simplexes. (End)

This triangle T(n, k) appears in the o.g.f. G(n, x) = Sum_{m>=0} S(n, m)*x^m with S(n, m) = Sum_{j=0..m} j^n for n >= 1 as G(n, x) = Sum_{k=1..n} (x^k/(1 - x)^(k+2))*T(n, k). See also the Eulerian triangle A008292 with a Mar 31 2017 comment for a rewritten form. For the e.g.f. see A028246 with a Mar 13 2017 comment. - Wolfdieter Lang, Mar 31 2017

T(n,k) = the number of alignments of length k of n strings each of length 1. See Slowinski. An example is given below. Cf. A122193 (alignments of strings of length 2) and A299041 (alignments of strings of length 3). - Peter Bala, Feb 04 2018

The row polynomials R(n,x) are the Fubini polynomials. - Emanuele Munarini, Dec 05 2020

From Gus Wiseman, Feb 18 2022: (Start)

Also the number of patterns of length n with k distinct parts (or with maximum part k), where we define a pattern to be a finite sequence covering an initial interval of positive integers. For example, row n = 3 counts the following patterns:

(1,1,1) (1,2,2) (1,2,3)

(2,1,2) (1,3,2)

(2,2,1) (2,1,3)

(1,1,2) (2,3,1)

(1,2,1) (3,1,2)

(2,1,1) (3,2,1)

(End)

Regard A048994 as a lower-triangular matrix and divide each term A048994(n,k) by n!, then this is the matrix inverse. Because Sum_{k=0..n} (A048994(n,k) * x^n / n!) = A007318(x,n), Sum_{k=0..n} (A131689(n,k) * A007318(x,k)) = x^n. - Natalia L. Skirrow, Mar 23 2023

T(n,k) is the number of ordered partitions of [n] into k blocks. - Alois P. Heinz, Feb 21 2025

Original name was: Ascending wiggly sums: number of sums adding to n in which terms alternately increase and decrease.

A composition is up/down if it is alternately strictly increasing and strictly decreasing, starting with an increase. For example, the partition (3,2,2,2,1) has no up/down permutations, even though it does have the anti-run permutation (2,3,2,1,2). - Gus Wiseman, Jan 15 2022

Original name was: Descending wiggly sums: number of sums adding to n in which terms alternately decrease and increase.

A composition is down/up if it is alternately strictly decreasing and strictly increasing, starting with a decrease. For example, the partition (3,2,2,2,1) has no down/up permutations, even though it does have the anti-run permutation (2,1,2,3,2). - Gus Wiseman, Jan 28 2022

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217.

A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no alternating permutations, even though it does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2). An alternating pattern is necessarily an anti-run (A005649).

The version with twins (A344605) is identical to this sequence except with a(2) = 3 instead of 2.

From Gus Wiseman, Jan 16 2022: (Start)

Conjecture: Also the number of weakly up/down patterns of length n, where a sequence is weakly up/down if it is alternately weakly increasing and weakly decreasing, starting with an increase. For example, the a(0) = 1 through a(3) = 6 weakly up/down patterns are:

() (1) (1,1) (1,1,1)

(2,1) (1,1,2)

(2,1,1)

(2,1,2)

(2,1,3)

(3,1,2)

(End)

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217.

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217.

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

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

A composition is up/down if it is alternately strictly increasing and strictly decreasing, starting with an increase. For example, the partition (3,2,2,2,1) has no up/down permutations, even though it does have the anti-run permutation (2,3,2,1,2).

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

A composition is down/up if it is alternately strictly increasing and strictly decreasing, starting with a decrease. For example, the partition (3,2,2,2,1) has no down/up permutations, even though it does have the anti-run permutation (2,1,2,3,2).