cp's OEIS Frontend

The binary Dyck-Language (A063171) in decimal representation.

These encode width 2n mountain ranges, rooted planar trees of n+1 vertices and n edges, planar planted trees with n nodes, rooted plane binary trees with n+1 leaves (2n edges, 2n+1 vertices, n internal nodes, the root included), Dyck words, binary bracketings, parenthesizations, non-crossing handshakes and partitions and many other combinatorial structures in Catalan family, enumerated by A000108.

Is Sum_{k=1..n} a(k) / n^(5/2) bounded? - Benoit Cloitre, Aug 18 2002

This list is the intersection of A061854 and A031443. - Jason Kimberley, Jan 18 2013

The sequence does start at n = 0, since in the binary interpretation of the Dyck language (e.g., as parenthesizations where "1" stands for "(" and "0" stands for ")") having a(0) = 0 will do since it would stand for the empty string where the "0"s and "1"s are balanced (hence the parentheses are balanced). - Daniel Forgues, Feb 17 2013

It appears that for n>=1 this sequence can be obtained by concatenating the terms of the irregular array whose n-th row length is A000108(n) and that is defined recursively by B(n,0) = A020988(n) and B(n,k) = B(n, k-1) + D(n, k-1) where D(x,y) = (2^(2*(A089309(B(x,y))-1))-1)*(2/3) + 2^A007814(B(x,y)). - Raúl Mario Torres Silva and Michel Marcus, May 01 2020

This encoding is related to the ranking by standard ordered tree numbers in that (1) the binary encoding of trees ordered by standard ranking is given by A358505, while (2) the standard ranking of trees ordered by binary encoding is given by A358523. - Gus Wiseman, Nov 21 2022

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

Note: this finite decimal representation works only up to the 6917th term, as the 6918th such word is already (10,0,0,0,0,0,0,0,0,0). The sequence A071154 shows the initial portion of this sequence sorted.

In addition to all the automorphisms whose signature permutation satisfies the more restricted condition A127301(SP(n)) = A127301(n) for all n, there are also general tree-rotating automorphisms like *A057501, *A057502, *A069771 and *A069772 that satisfy also the condition A129599(SP(n)) = A129599(n) for all n. However, in contrast to A129593 this is not invariant under the automorphism *A072797. A000041(n) distinct values (seem to) occur in each range [A014137(n)..A014138(n)].