cp's OEIS Frontend

This is similar to the Abramowitz and Stegun ordering for partitions (see A036036). The standard ordering for compositions is A066099, which is more similar to the Mathematica partition ordering (A080577).

This can be regarded as a table in two ways: with each composition as a row, or with the compositions of each integer as a row. The first way has A124736 as row lengths and A070939 as row sums; the second has A001792 as row lengths and A001788 as row sums.

This sequence includes every finite sequence of positive integers.

Number of states in the planning domain FERRY, when n-3 cars are at one of two shores while the (n-2)nd car may be on the ferry or at one of the shores.

If the ferry could board any number of cars (instead of only one), the number of states would form the Pisot sequence P(2,6) (A008776). In addition, if k shores existed, the sequence would form the Pisot sequence P(k,k(k+1)). This corresponds to the BRIEFCASE planning domain.

a(i) is the number of occurrences of the number 1 in all palindromic compositions of n = 2*(i+1). - Silvia Heubach (sheubac(AT)calstatela.edu), Jan 10 2003. E.g., there are 5 palindromic compositions of 6, namely 111111 11211 2112 1221 141, containing a total of 16 1's.

Number of occurrences of 00's in all circular binary words of length n. Example: a(3)=6 because in the circular binary words 000, 001, 010, 011, 100, 101, 110 and 111 we have a total of 3+1+1+0+1+0+0+0=6 occurrences of 00. a(n) = Sum_{k=0..n} k*A119458(n,k). - Emeric Deutsch, May 20 2006

a(n) is the number of permutations on [n] for which the entries of each left factor form a circular subinterval of [n]. A subset I of [n] forms a circular subinterval of [n] if it is an ordinary interval [a,b] or has the form [1,a]-union-[b,n] for 1 <= a < b <= n. For example, (5,4,2) is a left factor of the permutation (5,4,2,1,3) which does not form a circular subinterval of [5] and a(4)=16 counts all 24 permutations of [4] except the eight whose first two entries are 1,3 (in either order) or 2,4. - David Callan, Mar 30 2007

a(n) is the total number of runs in all Boolean (n-1)-strings. For example, the 8 Boolean 3-strings, 000, 001, 010, 011, 100, 101, 110, 111 have 1, 2, 3, 2, 2, 3, 2, 1 runs respectively. - David Callan, Jul 22 2008

From Gary W. Adamson, Jul 31 2010: (Start)

Starting with "1" = (1, 2, 4, 8, ...) convolved with (1, 0, 2, 4, 8, ...).

Example: a(6) = 96 = (32, 16, 8, 4, 2, 1) dot (1, 0, 2, 4, 8, 16) = (32 + 0 + 16 + 16 + 16, + 16) = 32 + 4*16 (End)

An elephant sequence, see A175654. For the corner squares 24 A[5] vectors, with decimal values between 27 and 432, lead to this sequence (without the leading 0). For the central square these vectors lead to the companion sequence A087447 (without the first leading 1). - Johannes W. Meijer, Aug 15 2010

Starting with 1 = (1, 1, 2, 4, 8, 16, ...) convolved with (1, 1, 3, 7, 15, 31, ...). - Gary W. Adamson, Oct 26 2010

a(n) is the number of ways to draw simple polygonal chains for n vertices lying on a circle. - Anton Zakharov, Dec 31 2016

Also the number of edges, maximal cliques, and maximum cliques in the n-folded cube graph for n > 3. - Eric W. Weisstein, Dec 01 2017 and Mar 21 2018

Number of pairs of compositions of n corresponding to a seaweed algebra of index n-2 for n > 2. - Nick Mayers, Jun 25 2018

Starting with 1, 2, 6, 16, ..., number of permutations of length n>0 avoiding the partially ordered pattern (POP) {1>2, 1>3} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the second and third elements. - Sergey Kitaev, Dec 08 2020

Third column of A027465.

With offset = 2, a(n) is the number of length n words on alphabet {u,v,w,z} such that each word contains exactly 2 u's. - Zerinvary Lajos, Dec 29 2007

Also convolution of A002802 with A000984 (central binomial coefficients).

With a different offset, number of n-permutations of 5 objects u, v, w, z, x with repetition allowed, containing exactly two u's. - Zerinvary Lajos, Dec 29 2007

Also convolution of A000302 with A002697, also convolution of A002457 with itself. - Rui Duarte, Oct 08 2011

Number of 3-dimensional cubes in n-dimensional hypercube. - Henry Bottomley, Apr 14 2000

With three leading zeros, this is the second binomial transform of (0,0,0,1,0,0,0,0,...). - Paul Barry, Mar 07 2003

With 3 leading zeros, binomial transform of C(n,3). - Paul Barry, Apr 10 2003

Let M=[1,0,i;0,1,0;i,0,1], i=sqrt(-1). Then 1/det(I-xM)=1/(1-2x)^4. - Paul Barry, Apr 27 2005

If X_1,X_2,...,X_n is a partition of a 2n-set X into 2-blocks then, for n>2, a(n+1) is equal to the number of (n+3)-subsets of X intersecting each X_i (i=1,2,...,n). - Milan Janjic, Jul 21 2007

With offset 0, a(n) is the number of ways to separate [n] into four non-overlapping intervals (allowed to be empty) and then choose a subset from each interval. - Geoffrey Critzer, Feb 07 2009

Number of 4D hypercubes in n-dimensional hypercube. - Henry Bottomley, Apr 14 2000

With four leading zeros, binomial transform of C(n,4). - Paul Barry, Apr 10 2003

If X_1, X_2, ..., X_n is a partition of a 2n-set X into 2-blocks, then, for n>3, a(n) is equal to the number of (n+4)-subsets of X intersecting each X_i (i=1,2,...,n). - Milan Janjic, Jul 21 2007

Number of permutations of length n+3 containing 132 and 123 exactly once. Likewise for the pairs (123,213), (231,321), (312,321).

a(n) is the number of ways to assign n distinct contestants to two (not necessarily equal) distinct teams and then choose a captain for each team. - Geoffrey Critzer, Apr 07 2009

Consider all binary words of length n, and assign a weight to each set bit - the leftmost gets a weight of n-1, the rightmost a weight of 0. a(n) gives the sum of the weights of all n-bit words. For example, if n=3, we have 000, 001, 010, 011, 100, 101, 110, 111 with weights of 0, 0, 1, 1, 2, 2, 3, 3, giving a sum of 12.

a(n) is the number of North-East paths from (0,0) to (n+2,n+2) that have exactly one east step below y = x-1 and exactly one east step above y = x+1. This is related to the paired pattern P_1 and P_2. More details can be found in Pan and Remmel's link. - Ran Pan, Feb 03 2016

a(n) is the number of diagonals of length sqrt(2) in an n-dimensional hypercube (same as diagonals of its two-dimensional faces). - Stanislav Sykora, Oct 23 2016

a(n) is the number of ways to select a team from n players with at least two players, two of whom are the captain and the goalkeeper. - Wojciech Raszka, Apr 10 2019

a(n) is the sum of N_0*N_1 for all binary strings of length n, where N_0 and N_1 are the number of 0's and 1's in the string, respectively. For example, if n=3, we have 000, 001, 010, 011, 100, 101, 110, 111 with products 0, 2, 2, 2, 2, 2, 2, 0, giving a sum of 12. - Sigurd Kittilsen and Jens Otten, Sep 17 2020

Starting at 1, the three-fold convolution of A001019 (powers of 9).

Number of Dyck paths of semilength n, having k uu's with midpoint at even height. Example: T(4,1) = 6 because we have u(uu)duddd, u(uu)udddd, udu(uu)ddd, u(uu)dddud, u(uu)ddudd and uud(uu)ddd [here u = (1,1), d = (1,-1) and the uu's with midpoint at even height are shown between parentheses]. Row sums are the Catalan numbers (A000108). T(2n+1,n) = A000108(n) (the Catalan numbers). Sum_{k>=0} k*T(n,k) = binomial(2n-2,n-3) = A002694(n-1).

Sometimes called the Touchard distribution (after Touchard's Catalan number identity). T(n,k) = number of full binary trees on 2n edges with k deep interior vertices (deep interior means you have to traverse at least 2 edges to reach a leaf) = number of binary trees on n-1 edges with k vertices having a full complement of 2 children. - David Callan, Jul 19 2004

From David Callan, Oct 25 2004: (Start)

T(n,k) = number of ordered trees on n edges with k prolific edges. A prolific edge is one whose child vertex has at least two children. For example with n=3, drawing ordered trees down from the root, /|\ has no prolific edge and the only tree with one prolific edge has the shape of an inverted Y, so T(3,1)=1.

Proof: Consider the following bijection, recorded by Emeric Deutsch, from ordered trees on n edges to Dyck n-paths. For a given ordered tree, traverse the tree in preorder (walk-around from root order). To each node of outdegree r there correspond r upsteps followed by 1 downstep; nothing corresponds to the last leaf. This bijection sends prolific edges to noninitial ascents of length >=2, that is, to DUU's. Then reverse the resulting Dyck n-path so that prolific edges correspond to DDU's. (End)

T(n,k) is the number of Łukasiewicz paths of length n having k fall steps (1,-1) that start at an even level. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: T(3,1) = 1 because we have U(2)(D)D, where U(2) = (1,2), D = (1,-1) and the fall steps that start at an even level are shown between parentheses. Row n contains ceiling(n/2) terms (n >= 1). - Emeric Deutsch, Jan 06 2005

Number of binary trees with n-1 edges and k+1 leaves (a binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child). - Emeric Deutsch, Jul 31 2006

Number of full binary trees with 2n edges and k+1 vertices both children of which are leaves (n >= 1; a full binary tree is a rooted tree in which each vertex has either 0 or two children). - Emeric Deutsch, Dec 26 2006

Number of ordered trees with n edges and k jumps. In the preorder traversal of an ordered tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump. - Emeric Deutsch, Jan 18 2007

It is remarkable that we can generate the coefficients of the right hand columns of triangle A175136 with the aid of the coefficients in the rows of the triangle given above. See A175136 for more information. - Johannes W. Meijer, May 06 2011

The antidiagonal sums equal A152225. - Johannes W. Meijer, Sep 13 2012

This array also counts 231-avoiding permutations according to the number of peaks, i.e., positions w[i-1] < w[i] > w[i+1]. For example, 123, 213, 312, and 321 have no peaks, while 132 has one peak. Note also T(n,k) = 2^(n - 1 - 2*k)*A055151(n-1,k). - Kyle Petersen, Aug 02 2013