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

These compositions avoid the strict consecutive patterns (1,2,3) and (3,2,1), the weak version being A344604.

These compositions avoid the weak consecutive pattern (1,2,3), the strict version being A128761.

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670. A sequence is alternating (cf. A025047) including pairs (x,x) if there are no adjacent triples (..., x, y, z, ...) where x <= y <= z or x >= y >= z. These sequences avoid the weak consecutive patterns (1,2,3) and (3,2,1).

An alternating pattern of length > 2 is necessarily an anti-run (A005649).

The version without pairs (x,x) is identical to this sequence except a(2) = 2 instead of 3.

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)

The number of compatible bipartitions of a set of cardinality n for which at least one subset is not underlined. E.g., for n=2 there are 5 such bipartitions: {1 2}, {1}{2}, {2}{1}, {1}{2}, {2}{1}. A005649 is the number of bipartitions of a set of cardinality n. A000670 is the number of bipartitions of a set of cardinality n with none of the subsets underlined. - Kyle Petersen, Mar 31 2005

a(n) is the cardinality of the image set summed over "all surjections". All surjections means: onto functions f:{1, 2, ..., n} -> {1, 2, ..., k} for every k, 1 <= k <= n. a(n) = Sum_{k=1..n} A019538(n, k)*k. - Geoffrey Critzer, Nov 12 2012

From Gus Wiseman, Jan 15 2022: (Start)

For n > 1, also the number of finite sequences of length n + 1 covering an initial interval of positive integers with at least two adjacent equal parts, or non-anti-run patterns, ranked by the intersection of A348612 and A333217. The complement is counted by A005649. For example, the a(3) = 31 patterns, grouped by sum, are:

(1111) (1222) (1122) (1112) (1233) (1223)

(2122) (1221) (1121) (1332) (1322)

(2212) (2112) (1211) (2133) (2213)

(2221) (2211) (2111) (2331) (2231)

(1123) (3312) (3122)

(1132) (3321) (3221)

(2113)

(2311)

(3112)

(3211)

Also the number of ordered set partitions of {1,...,n + 1} with two successive vertices together in some block.

(End)

From Gus Wiseman, Jun 24 2020: (Start)

Equivalently, a(n) is number of (1,1)-matching sequences of length n that cover an initial interval of positive integers. For example, the a(2) = 1 and a(3) = 7 sequences are:

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

(1,1,2)

(1,2,1)

(1,2,2)

(2,1,1)

(2,1,2)

(2,2,1)

Missing from this list are:

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

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

(2,1,3)

(2,3,1)

(3,1,2)

(3,2,1)

(End)

From Robert A. Proctor, Jul 18 2017: (Start)

a(n) is the number of words of length n on {1,2,...,r} with positive multiplicities as 1 <= r <= n avoiding the pattern 123. [This is easy to see from the next comment.]

a(n) is the number of 123-avoiding ordered set partitions of {1,2,...,n}. [This is Cor. 2.3 of the Chen-Dai-Zhou reference.] (End)

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.

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 S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).