cp's OEIS Frontend

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

A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts.

Alternatively, a multiset is separable if its greatest multiplicity is greater than the sum of its remaining multiplicities plus one. Hence a(n) is the number of compositions of n whose greatest part is at most one more than the sum of its other parts. For example, the a(1) = 1 through a(5) = 13 compositions are:

(1) (11) (12) (22) (23)

(21) (112) (32)

(111) (121) (113)

(211) (122)

(1111) (131)

(212)

(221)

(311)

(1112)

(1121)

(1211)

(2111)

(11111)

A multiset whose multiplicities are the prime indices of n (such as row n of A305936) is not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

An anti-run is a sequence with no adjacent equal parts.

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

A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts.

Alternatively, a multiset is separable if its greatest multiplicity is greater than the sum of its remaining multiplicities plus one.

Also the number of compositions of n whose greatest part is greater than the sum of its remaining parts plus one. For example, the a(2) = 1 through a(7) = 8 compositions are:

(2) (3) (4) (5) (6) (7)

(1,3) (1,4) (1,5) (1,6)

(3,1) (4,1) (2,4) (2,5)

(4,2) (5,2)

(5,1) (6,1)

(1,1,4) (1,1,5)

(1,4,1) (1,5,1)

(4,1,1) (5,1,1)

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). Alternating permutations of multisets are a generalization of alternating or up-down permutations of {1..n}.

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). Alternating permutations of multisets are a generalization of alternating or up-down permutations of {1..n}.

The multisets that have an alternating permutation are those which have no part with multiplicity greater than floor(n/2) except for odd n when either the smallest or largest part can have multiplicity ceiling(n/2). - Andrew Howroyd, Jan 13 2024

Also the number of (1,2,1)-matching patterns of length n.

Also the number of (2,1,2)-matching patterns of length 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).

a(n) is the number of ways to arrange the blocks of the partitions of {1,2,...,n} in an undirected cycle of length 3 or more, see A000629. - Geoffrey Critzer, Nov 23 2012

From Gus Wiseman, Jun 24 2020: (Start)

Also the number of (1,2)-matching length-n sequences covering an initial interval of positive integers. For example, the a(2) = 1 and a(3) = 9 sequences are:

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

(1,2,1)

(1,2,2)

(1,2,3)

(1,3,2)

(2,1,2)

(2,1,3)

(2,3,1)

(3,1,2)

Missing from this list are:

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

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

(2,2,1)

(3,2,1)

(End)

These are compositions with some part appearing more than once, or non-strict compositions.

A composition of n is a finite sequence of positive integers summing to n. 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).