cp's OEIS Frontend

Apart from initial term, same as A000079 (powers of 2).

Number of compositions (ordered partitions) of n. - Toby Bartels, Aug 27 2003

Number of ways of putting n unlabeled items into (any number of) labeled boxes where every box contains at least one item. Also "unimodal permutations of n items", i.e., those which rise then fall. (E.g., for three items: ABC, ACB, BCA and CBA are unimodal.) - Henry Bottomley, Jan 17 2001

Number of permutations in S_n avoiding the patterns 213 and 312. - Tuwani Albert Tshifhumulo, Apr 20 2001. More generally (see Simion and Schmidt), the number of permutations in S_n avoiding (i) the 123 and 132 patterns; (ii) the 123 and 213 patterns; (iii) the 132 and 213 patterns; (iv) the 132 and 231 patterns; (v) the 132 and 312 patterns; (vi) the 213 and 231 patterns; (vii) the 213 and 312 patterns; (viii) the 231 and 312 patterns; (ix) the 231 and 321 patterns; (x) the 312 and 321 patterns.

a(n+2) is the number of distinct Boolean functions of n variables under action of symmetric group.

Number of unlabeled (1+2)-free posets. - Detlef Pauly, May 25 2003

Image of the central binomial coefficients A000984 under the Riordan array ((1-x), x*(1-x)). - Paul Barry, Mar 18 2005

Binomial transform of (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...); inverse binomial transform of A007051. - Philippe Deléham, Jul 04 2005

Also, number of rationals in [0, 1) whose binary expansions terminate after n bits. - Brad Chalfan, May 29 2006

Equals row sums of triangle A144157. - Gary W. Adamson, Sep 12 2008

Prepend A089067 with a 1, getting (1, 1, 3, 5, 13, 23, 51, ...) as polcoeff A(x); then (1, 1, 2, 4, 8, 16, ...) = A(x)/A(x^2). - Gary W. Adamson, Feb 18 2010

An elephant sequence, see A175655. For the central square four A[5] vectors, with decimal values 2, 8, 32 and 128, lead to this sequence. For the corner squares these vectors lead to the companion sequence A094373. - Johannes W. Meijer, Aug 15 2010

From Paul Curtz, Jul 20 2011: (Start)

Array T(m,n) = 2*T(m,n-1) + T(m-1,n):

1, 1, 2, 4, 8, 16, ... = a(n)

1, 3, 8, 20, 48, 112, ... = A001792,

1, 5, 18, 56, 160, 432, ... = A001793,

1, 7, 32, 120, 400, 1232, ... = A001794,

1, 9, 50, 220, 840, 2912, ... = A006974, followed with A006975, A006976, gives nonzero coefficients of Chebyshev polynomials of first kind A039991 =

1,

1, 0,

2, 0, -1,

4, 0, -3, 0,

8, 0, -8, 0, 1.

T(m,n) third vertical: 2*n^2, n positive (A001105).

Fourth vertical appears in Janet table even rows, last vertical (A168342 array, A138509, rank 3, 13, = A166911)). (End)

A131577(n) and differences are:

0, 1, 2, 4, 8, 16,

1, 1, 2, 4, 8, 16, = a(n),

0, 1, 2, 4, 8, 16,

1, 1, 2, 4, 8, 16.

Number of 2-color necklaces of length 2n equal to their complemented reversal. For length 2n+1, the number is 0. - David W. Wilson, Jan 01 2012

Edges and also central terms of triangle A198069: a(0) = A198069(0,0) and for n > 0: a(n) = A198069(n,0) = A198069(n,2^n) = A198069(n,2^(n-1)). - Reinhard Zumkeller, May 26 2013

These could be called the composition numbers (see the second comment) since the equivalent sequence for partitions is A000041, the partition numbers. - Omar E. Pol, Aug 28 2013

Number of self conjugate integer partitions with exactly n parts for n>=1. - David Christopher, Aug 18 2014

The sequence is the INVERT transform of (1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...). - Gary W. Adamson, Jul 16 2015

Number of threshold graphs on n nodes [Hougardy]. - Falk Hüffner, Dec 03 2015

Number of ternary words of length n in which binary subwords appear in the form 10...0. - Milan Janjic, Jan 25 2017

a(n) is the number of words of length n over an alphabet of two letters, of which one letter appears an even number of times (the empty word of length 0 is included). See the analogous odd number case in A131577, and the Balakrishnan reference in A006516 (the 4-letter odd case), pp. 68-69, problems 2.66, 2.67 and 2.68. - Wolfdieter Lang, Jul 17 2017

Number of D-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are D-equivalent iff the positions of pattern D are identical in these paths. - Sergey Kirgizov, Apr 08 2018

Number of color patterns (set partitions) for an oriented row of length n using two or fewer colors (subsets). Two color patterns are equivalent if we permute the colors. For a(4)=8, the 4 achiral patterns are AAAA, AABB, ABAB, and ABBA; the 4 chiral patterns are the 2 pairs AAAB-ABBB and AABA-ABAA. - Robert A. Russell, Oct 30 2018

The determinant of the symmetric n X n matrix M defined by M(i,j) = (-1)^max(i,j) for 1 <= i,j <= n is equal to a(n) * (-1)^(n*(n+1)/2). - Bernard Schott, Dec 29 2018

For n>=1, a(n) is the number of permutations of length n whose cyclic representations can be written in such a way that when the cycle parentheses are removed what remains is 1 through n in natural order. For example, a(4)=8 since there are exactly 8 permutations of this form, namely, (1 2 3 4), (1)(2 3 4), (1 2)(3 4), (1 2 3)(4), (1)(2)(3 4), (1)(2 3)(4), (1 2)(3)(4), and (1)(2)(3)(4). Our result follows readily by conditioning on k, the number of parentheses pairs of the form ")(" in the cyclic representation. Since there are C(n-1,k) ways to insert these in the cyclic representation and since k runs from 0 to n-1, we obtain a(n) = Sum_{k=0..n-1} C(n-1,k) = 2^(n-1). - Dennis P. Walsh, May 23 2020

Maximum number of preimages that a permutation of length n + 1 can have under the consecutive-231-avoiding stack-sorting map. - Colin Defant, Aug 28 2020

a(n) is the number of occurrences of the empty set {} in the von Neumann ordinals from 0 up to n. Each ordinal k is defined as the set of all smaller ordinals: 0 = {}, 1 = {0}, 2 = {0,1}, etc. Since {} is the foundational element of all ordinals, the total number of times it appears grows as powers of 2. - Kyle Wyonch, Mar 30 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

More generally, the g.f. for the number of partitions of n such that the least part occurs at least m times is sum(x^(mk)/product(1-x^j, j=k..infinity), k=1..infinity). Also, the number of partitions of n such that if k is the largest part, then k>=2 and k-1 does not occur. Example: a(5)=3 because we have [5],[4,1] and [3,1,1].

Also, the number of partitions of 2n such that the difference between greatest part and smallest part is n. - Vladeta Jovovic, May 09 2008

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)

The leaders of maximal weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.

Also the number of integer compositions of n matching the dashed pattern 1-32, ranked by A375137.

Also the number of integer compositions of n matching the dashed pattern 23-1, ranked by A375138.

Also compositions matching the pattern (1,2).

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.

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.

These are also numbers k such that the maximal weakly increasing runs in the k-th composition in standard order do not have weakly decreasing leaders, where the leaders of weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.

The reverse version (A375138) ranks compositions matching the dashed pattern 23-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)

Also compositions matching the pattern (2,1).

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.