cp's OEIS Frontend

From the second term 3 onward also one more than the partial sums of A076050.

Read by upwards antidiagonals as A(1,1), A(2,1), A(1,2), A(3,1), A(2,2), A(1,3), etc.

Given A007001: (1, 2, 1, 2, 3, 1, 2, 1, ...) as first row of an array, n-th row = partial sum sequence of (n-1)-th row.

Row sums = A133914: (1, 3, 5, 11, 23, 44, 89, 177, 355, ...).

Right border = A007001: (1, 2, 1, 2, 3, 1, 2, 1, ...).

This sequence represents the expected saturation of a binary search tree (or BST) on n nodes times the number of binary search trees on n nodes, or alternatively, the sum of the saturation of all binary search trees on n nodes. - Marko Riedel, Jan 24 2002

1->12, 2->123, 3->1234 etc. starting with 1, gives A007001: 1, 12, 12123, 12123121231234... summing the digits gives this sequence. - Miklos Kristof, Nov 05 2002

a(n-1) = number of n-th generation vertices in the tree of sequences with unit increase labeled by 2 (cf. Zoran Sunic reference). - Benoit Cloitre, Oct 07 2003

With offset 1, number of permutations beginning with 12 and avoiding 32-1.

Number of lattice paths from (0,0) to (n,n) with steps E=(1,0) and N=(0,1) which touch but do not cross the line x-y=1. - Herbert Kociemba, May 24 2004

a(n) is the number of Dyck (n+1)-paths that start with UU. For example, a(2)=3 counts UUUDDD, UUDUDD, UUDDUD. - David Callan, Dec 08 2004

a(n) is the number of Dyck (n+2)-paths that start with UUDU. For example, a(2)=3 counts UUDUDDUD, UUDUDUDD, UUDUUDDD. - David Scambler, Feb 14 2011

Hankel transform is (0,-1,-1,0,1,1,0,-1,-1,0,...). Hankel transform of a(n+1) is (1,0,-1,-1,0,1,1,0,-1,-1,0,...). - Paul Barry, Feb 08 2008

Starting with offset 1 = row sums of triangle A154558. - Gary W. Adamson, Jan 11 2009

Starting with offset 1 equals INVERT transform of A014137, partial sums of the Catalan numbers: (1, 2, 4, 9, 23, ...). - Gary W. Adamson, May 15 2009

With offset 1, a(n) is the binomial transform of the shortened Motzkin numbers: 1, 2, 4, 9, 21, 51, 127, 323, ... (A001006). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Sep 07 2009

The Catalan sequence convolved with its shifted variant, e.g. a(5) = 90 = (1, 1, 2, 5, 14) dot (42, 14, 5, 2, 1) = (42 + 14 + 10 + 10 + 14 ) = 90. - Gary W. Adamson, Nov 22 2011

a(n+2) = A214292(2*n+3,n). - Reinhard Zumkeller, Jul 12 2012

With offset 3, a(n) is the number of permutations on {1,2,...,n} that are 123-avoiding, i.e., do not contain a three term monotone subsequence, for which the first ascent is at positions (3,4); see Connolly link. There it is shown in general that the k-th Catalan Convolution is the number of 123-avoiding permutations for which the first ascent is at (k, k+1). (For n=k, the first ascent is defined to be at positions (k,k+1) if the permutation is the decreasing permutation with no ascents.) - Anant Godbole, Jan 17 2014

With offset 3, a(n)=number of permutations on {1,2,...,n} that are 123-avoiding and for which the integer n is in the 3rd spot; see Connolly link. For example, there are 297 123-avoiding permutations on n=9 at which the element 9 is in the third spot. - Anant Godbole, Jan 17 2014

With offset 1, a(n) is the number of North-East paths from (0,0) to (n+1,n+1) that bounce off y = x to the right exactly once but do not cross y = x vertically. Details can be found in Section 4.4 in Pan and Remmel's link. - Ran Pan, Feb 01 2016

The total number of returns (downsteps which end on the line y=0) within the set of all Dyck paths from (0,0) to (2n,0). - Cheyne Homberger, Sep 05 2016

a(n) is the number of intervals of the form [s,w] that are distributive (equivalently, modular) lattices in the weak order on S_n, for a fixed simple reflection s. - Bridget Tenner, Jan 16 2020

a(n+2) is the number of coalescent histories for a pair (G,S) where G is a gene tree with 3-pseudocaterpillar shape and n leaves, S is a species tree with caterpillar shape and n leaves, and G and S have identical leaf labeling. - Noah A Rosenberg, Jun 15 2022

a(n) is the number of parking functions of size n avoiding the patterns 132, 213, and 312. - Lara Pudwell, Apr 10 2023

a(n) is the number of parking functions of size n avoiding the patterns 123 and 213. - Lara Pudwell, Apr 10 2023

We write the nonnegative integers as restricted growth strings (so called by J. Arndt in his book fxtbook.pdf, p. 325) in such a way that the Catalan numbers (cf. A000108) are expressed: 1=1, 10=2, 100=5, 1000=14, etc., 10...0 (with k zeros) = the k-th Catalan number. Once the entries of a restricted-growth string grow above 9, one would need commas or parentheses, say, to separate those entries. See Dejter (2017) for the precise definition.

In the paper "A system of numeration for middle-levels", restricted growth strings (RGSs) are defined as sequences that begin with either 0 or 1, with each successive number to the right being at least zero and at most one greater than its immediate left neighbor. Moreover, apart from case a(0), the RGSs are finite integer sequences of restricted growth which always start with 1 as their first element b_1 in position 1, and from then on, each successive element b_{i+1} in the sequence is restricted to be in range [0,(b_i)+1].

This sequence gives all such finite sequences in size-wise and lexicographic order, represented as decimal numbers by concatenating the integers of such finite sequences (e.g., from [1,2,0,1] we get 1201). The 58784th such sequence is [1, 2, 3, 4, 5, 6, 7, 8, 9, 9], thus a(58784) = 1234567899, after which comes the first RGS, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], where an element larger than 9 is present, which means that the decimal system employed here is unambiguous only up to n=58784. Note that 58785 = A000108(11)-1.

Also, if one considers Stanley's interpretation (u) of Catalan numbers, "sequences of a_1, a_2, ..., a_n of integers such that a_1 = 0 and 0 <= a_{i+1} <= a_{i} + 1" (e.g., 000, 001, 010, 011, 012 for C_3), and discards their initial zero, then one has a bijective correspondence with Dejter's RGSs of one element shorter length, which in turn are in bijective correspondence with the first C_n terms of this sequence (by discarding any leading zeros), from a(0) to a(C_n - 1). From this follows that the k-th Catalan number, A000108(k) (k>0), is represented in this system as 1 followed by k-1 zeros: a(1)=1, a(2)=10, a(5)=100, a(14)=1000, etc., and also that there exist exactly A000245(k) RGSs of length k.

Note how this differs from other number representations utilizing Catalan numbers, A014418 and A244159, in that while the latter are base-systems, where a simple weighted Sum_{k} digit(k)*C(k) recovers the natural number n (which the n-th numeral of such system represents), in contrast here it is the sum of appropriate terms in Catalan's Triangle (A009766, A030237), obtained by unranking a unique instance of a certain combinatorial structure (one of the Catalan interpretations), that gives a correspondence with a unique natural number. (Cf. also A014486.)

This sequence differs from "Semigreedy Catalan Representation", A244159, for the first time at n=10, where a(10) = 120, while A244159(10) = 121. That is also the first position where A244158(a(n)) <> n.

Please see Dejter's preprint for a more formal mathematical definition and how this number system is applied in relation to Havel's Conjecture on the existence of Hamiltonian cycles in the middle-levels graphs.

a(n) is given by the concatenation (with leading zeros removed) of the terms of row n + 23714 of A370222. - Paolo Xausa, Feb 17 2024

Also a triangle collected from the Catalan generating tree, with row n containing A000108(n) terms and ending with n. Rows converge towards A007001, the "last" row. - Antti Karttunen, Jun 17 2003

The paths through the tree represent the compositions counted in A173258 that have first part 1.

For rows n > 1, row n starts with row n-2.

Any positive number k will first appear in the (k-1)-th row and thereafter in rows of opposite parity to k. The number of times k will appear in row n is A053121(n,k-1).

Row n >= 1 gives the row lengths of the Christmas tree pattern of order n (cf. A367508). - Paolo Xausa, Nov 26 2023

A new row can be generated by applying the morphism 1 -> 2, t -> {t-1,t+1} (for t > 1) to the previous row. - Paolo Xausa, Dec 08 2023