cp's OEIS Frontend

Compositions into distinct parts are equivalent to (1,1)-avoiding compositions. - Gus Wiseman, Jun 25 2020

All terms are odd. - Alois P. Heinz, Apr 09 2021

a(n^2) is odd. - Gregory L. Simay, Jun 23 2019

Also the number of compositions of n avoiding the patterns (1,2,1) and (2,1,2). - Gus Wiseman, Jul 07 2020

A composition of n is a finite sequence of positive integers summing to n.

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

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

Note that an exponentiation ^(-1) is missing in Example 4.4. The notation in Theorem 4.3 is complete.

Theorem: The reverse of a composition avoids 23-1 iff its leaders of maximal weakly increasing runs are weakly decreasing. For example, the composition y = (3,2,1,2,2,1,2,5,1,1,1) has maximal weakly increasing runs ((3),(2),(1,2,2),(1,2,5),(1,1,1)), with leaders (3,2,1,1,1), which are weakly decreasing, so the reverse of y is counted under a(21). - Gus Wiseman, Aug 19 2024

Also the number of integer compositions of n whose reverse avoids 12-1 and 23-1.

Theorem: The reverse of a composition avoids 12-1 and 23-1 iff its leaders of maximal weakly increasing runs, obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each, are strictly decreasing. For example, the composition y = (4,5,3,2,2,3,1,3,5) has reverse (5,3,1,3,2,2,3,5,4), which avoids 12-1 and 23-1, while the maximal weakly increasing runs of y are ((4,5),(3),(2,2,3),(1,3,5)), with leaders (4,3,2,1), which are strictly decreasing, as required. - Gus Wiseman, Aug 20 2024

These patterns comprise the basis of the class of patterns generated by this composition.

We define a (normal) 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).

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.

Also compositions matching the pattern (1,1). - Gus Wiseman, Jun 23 2020

Such a permutation is characterized by being neither a twin (x,x) nor wiggly (A025047, A345192). A sequence is wiggly if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,3,2,2,2,2,1) has no wiggly permutations, even though it has the anti-run permutations (2,3,2,3,2,1,2), (2,3,2,1,2,3,2), and (2,1,2,3,2,3,2).

We define a (normal) pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670. 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).

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.