A071159 -id:A071159 - cp's OEIS frontend

A239903 List of Restricted-Growth Strings a_{k-1}a_{k-2}...a_{2}a_{1}, with k=2 and a_1 in {0,1} or k>2, a_{k-1}=1 and a_{j+1}>=1+a_j, for k-1>j>0.

0, 1, 10, 11, 12, 100, 101, 110, 111, 112, 120, 121, 122, 123, 1000, 1001, 1010, 1011, 1012, 1100, 1101, 1110, 1111, 1112, 1120, 1121, 1122, 1123, 1200, 1201, 1210, 1211, 1212, 1220, 1221, 1222, 1223, 1230, 1231, 1232, 1233, 1234, 10000, 10001, 10010, 10011

Offset: 0

N. J. A. Sloane, Apr 06 2014

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

			Catalan's Triangle T(row,col) = A009766 begins with row n=0 and 0<=col<=n as:
  Row 0: 1
  Row 1: 1, 1
  Row 2: 1, 2,  2
  Row 3: 1, 3,  5,  5
  Row 4: 1, 4,  9, 14, 14
  Row 5: 1, 5, 14, 28, 42,  42
  Row 6: 1, 6, 20, 48, 90, 132, 132
  (the leftmost diagonal of 1s is "column 0").
  ...
For example, for n=38, we find that A081290(38)=14, which occurs on row A081288(n)-1 = 4, in columns A081288(n)-1 and A081288(n)-2, i.e., as T(4,4) and T(4,3). Thus we subtract 38-14 to get 24, and we see that the next term downward on the same diagonal, 28, is too large to accommodate into the same sum, so we go one diagonal up, starting now from T(3,2) = 5. This fits in, so we now have 24 - 5 = 19, and also the next term on the same diagonal, T(4,2) = 9, fits in, so we now have 19-9 = 10. The next term on the same diagonal, T(5,2) = 14, would not fit in anymore, so we rewind ourselves back to penultimate column, but one step up from where we started on this diagonal, so T(2,1) = 2, which fits in, 10 - 2 = 8, also the next one T(3,1) = 3, 8 - 3 = 5, and the next one T(4,1) = 4, 5 - 4 = 1, after which comes T(5,1) = 5 > 1, thus we jump to T(1,0) = 1, 1-1 = 0, and T(2,0)=1 would not fit anymore, thus next time the row would be zero, and the algorithm is ready with 1 (14), 2 (5+9), 3 (2+3+4) and 1 (1) terms collected, whose total sum 14+5+9+2+3+4+1 = 38, thus a(38) = 1231.
For n=20, the same algorithm results in 1 (14), 1 (5), 0 (not even the first tentative term T(2,1) = 2 from the column 1 would fit, so it is skipped), and from one row higher we get the needed 1 (1), so the total sum of these is 14+5+0+1 = 20, thus a(20) = 1101.

D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, third edition, Addison-Wesley, 1977, p. 192.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999, Exercise 19, interpretation (u).

Antti Karttunen, Table of n, a(n) for n = 0..16796
Joerg Arndt, Matters Computational: Ideas, Algorithm, Source Code, Springer, 2011; freely downloadable here: Fxtbook.
Georg Cantor, Über die einfachen Zahlensysteme, Zeitschrift fur Mathematik und Physik, 14 (1869), 121-128.
Italo J. Dejter, A system of numeration for middle levels, arXiv:1012.0995 [math.CO], (2014).
Italo J. Dejter, The role of restricted growth strings in the two middle levels of the Boolean lattice B_(2k+1), University of Puerto Rico, 2018.
Italo J. Dejter, Reinterpreting Mütze's theorem via natural enumeration of ordered rooted trees, arXiv:1911.02100 [math.CO], (2019).
Italo J. Dejter, A numeral system for the middle-levels graphs, Elec. J. Graph Theory and Applications (2021) Vol. 9, No. 1, 137-156. See p. 138.
Italo J. Dejter, Edge-supplementary arc factorizations of odd graphs, uniform 2-factors and Hamilton cycles, arXiv:2203.05326 [math.CO], 2022.
Italo J. Dejter, Integer sequence of Dyck-path single changes, arXiv:2209.11122 [math.CO], 2022.
Italo J. Dejter, A Dyck-word tree that controls all odd graphs, arXiv:2306.14249 [math.CO], 2023.
Aviezri S. Fraenkel, The Use and Usefulness of Numeration Systems, Inf. Comput., 81(1), (1989), 46-61.
Aviezri S. Fraenkel, Systems of numeration, IEEE Symposium on Computer Arithmetic, (1983), 37-42.
Aviezri S. Fraenkel, Systems of numeration, The American Mathematical Monthly, Vol. 92, No. 2 (Feb., 1985), pp. 105-114.
Antti Karttunen, Catalan ranking and unranking functions, OEIS Wiki.
R. P. Stanley, Exercises on Catalan and Related Numbers, interpretation (u) of Catalan numbers, on page 224 (page 4/27 in the November 1 2000 version of the PDF-file).

Cf. A000108 (Catalan numbers), A000245 (their first differences), A009766 (Catalan's triangle), A236855 (the sum of elements in k-th RGS), A236859 (for n>=1, gives the length of the initial ascent 123... in term a(n)), A244159 (different kinds of Catalan number systems).
Other Catalan combinatorial structures represented as integer sequences: A014486/A063171: Dyck words, parenthesizations, etc., A071156/A071158: Similar restricted words encoded with help of A007623 (Integers written in factorial base), A071153/A079436 (Łukasiewicz words).
Cf. A007001, A007623, A014418, A071154, A071159, A081288, A081290, A081291, A082853, A126307, A244155, A244156, A244157, A244158, A370222.

function CatalanNumerals(z)
    z == 0 && return 0
    f(n) = factorial(n)
    t(j, k) = div(f(k+j)*(k-j+1), f(j)*f(k+1))
    k, i = 2, 0
    while z >= t(i, i + 1) i += 1 end
    dig = fill(0, i); dig[1] = 1
    x = z - t(i - 1, i)
    m = i - 1
    while x > 0
        w, s, p = 0, 0, 0
        while w <= x
            p = w
            w += t(m - 1, m + s)
            s += 1
        end
        dig[k] = s - 1
        m -= 1; k += 1; x -= p
    end
    s = ""; for d in dig s *= string(d) end
    parse(Int, s)
end
[CatalanNumerals(n) for n in 0:42] |> println # Peter Luschny, Nov 10 2019

function [ c ] = catrep(z)
i=0; x=0; y=0; s=0;
while z>=(factorial(2*i+1)*(2))/(factorial(i)*factorial(i+2))
i=i+1;
end
y=(factorial(2*i-1)*(2))/(factorial(i-1)*factorial(i+1));
a=zeros(1,i); a(1,1)=1; k=2; x=z-y; m=1;
while x>0
w=0; s=0; p=0;
while w<=x
p=w;
w=w+(factorial(2*i-2*m+s-1)*(s+2))/(factorial(i-1-m)*factorial(i-m+s+1));
s=s+1;
end
m=m+1; a(1,k)=s-1; k=k+1; x=x-p;
end
a
end

A239903full = With[{r = 2*Range[2, 11]-1}, Reverse[Map[FromDigits[r-#] &, Rest[Select[Subsets[Range[2, 21], {10}, 125477], Min[r-#] >= 0 &]]]]];
A239903full[[;;100]] (* Paolo Xausa, Feb 17 2024 *)

define (t(j,k), (factorial(k+j)*(k-j+1))/(factorial(j)*factorial(k+1)));
i:0;
x:19;
z:0;y:0;s:0;
while x>=t(i,i+1) do (i:i+1);
y:t(i-1,i);a:zeromatrix(1,i);a[1,1]:1;k:2;z:x-y;m:1;
while (z>0) do (
w:0,s:0,p=0,
while (w<=z) do (
p:w,
w:w+t(i-1-m,i-m+s),
s:s+1
),
m:m+1,
a[1,k]:s-1,k:k+1,
z:z-p
);
print(a);

\\ Valid for n<58786 (=A000108(11)).
nxt(w)=if(w[1]==#w, vector(#w+1, i, i>#w), my(k=1); while(w[k]>w[k+1], w[k]=0; k++); w[k]++; w)
seq(n)={my(a=vector(n), w=[1]); a[1]=0; for(i=2, #v, a[i]=fromdigits(Vecrev(w)); w=nxt(w)); a} \\ Andrew Howroyd, Jan 24 2023

(define (A239903_only_upto_16794 n) (if (zero? n) n (A235049 (A071159 (A081291 n))))) ;; Gives correct results only up to 16794.
;; The following gives correct results all the way up to n=58784.
(define (A239903 n) (baselist-as-decimal (A239903raw n)))
(definec (A239903raw n) (if (zero? n) (list) (let loop ((n n) (row (A244160 n)) (col (- (A244160 n) 1)) (srow (- (A244160 n) 1)) (catstring (list 0))) (cond ((or (zero? row) (negative? col)) (reverse! (cdr catstring))) ((> (A009766tr row col) n) (loop n srow (- col 1) (- srow 1) (cons 0 catstring))) (else (loop (- n (A009766tr row col)) (+ row 1) col srow (cons (+ 1 (car catstring)) (cdr catstring))))))))
(define (baselist-as-decimal lista) (baselist->n 10 lista))
(define (baselist->n base bex) (let loop ((bex bex) (n 0)) (cond ((null? bex) n) (else (loop (cdr bex) (+ (* n base) (car bex)))))))
;; From Antti Karttunen, Apr 14-19 2014

To find an RGS corresponding to natural number n, one first finds a maximum row index k such that T(k,k-1) <= n in the Catalan Triangle (A009766) illustrated in the Example section. Note that as the last two columns of this triangle consist of Catalan numbers (that is, T(k,k-1) = T(k,k) = A000108(k)), it means that the first number to be subtracted from n is A081290(n) which occurs as a penultimate element of the row A081288(n)-1, in the column A081288(n)-2. The unranking algorithm then proceeds diagonally downwards, keeping the column index the same, and incrementing the row index, as long as it will encounter terms such that their total sum stays less than or equal to n.
If the total sum of encountered terms on that diagonal would exceed n, the algorithm jumps back to the penultimate column of the triangle, but one row higher from where it started the last time, and again starts summing the terms as long as the total sum stays <= n.
When the algorithm eventually reaches either row zero or column less than zero, the result will be a list of numbers, each element being the number of terms summed from each diagonal, so that the diagonal first traversed appears as the first 1 (as that first diagonal will never allow more than one term), and the number of terms summed from the last traversed diagonal appears the last number in the list. These lists of numbers are then concatenated together as decimal numbers.
These steps can also be played backwards in order to recover the corresponding decimal integer n from such a list of numbers, giving a "ranking function" which will be the inverse to this "unranking function".
For n=1..16794 (where 16794 = A000108(10)-2), a(n) = A235049(A071159(A081291(n))). - Antti Karttunen, Apr 14 2014
Alternative, simpler description of the algorithm from Antti Karttunen, Apr 21 2014: (Start)
Consider the following square array, which is Catalan triangle A009766 without its rightmost, "duplicate" column, appropriately transposed (cf. also tables A030237, A033184 and A054445):
   Row| Terms on that row
   ---+--------------------------
    1 |   1   1   1    1    1 ...
    2 |   2   3   4    5    6 ...
    3 |   5   9  14   20   27 ...
    4 |  14  28  48   75  110 ...
    5 |  42  90 165  275  429 ...
    6 | 132 297 572 1001 1638 ...
To compute the n-th RGS, search first for the greatest Catalan number C_k which is <= n (this is A081290(n), found as the first term of row A081288(n)-1). Then, by a greedy algorithm, select from each successive row (moving towards the top of table) as many terms from the beginning of that row as will still fit into n, subtracting them from n as you go. The number of terms selected from the beginning of each row gives each element of the n-th RGS, so that the number of terms selected from the topmost row (all 1's) appears as its last element.
(End)

Description, formula and examples edited/rewritten by Italo J Dejter, Apr 13 2014 and Antti Karttunen, Apr 18 2014

A071153 Łukasiewicz word for each rooted plane tree (interpretation e in Stanley's exercise 19) encoded by A014486 (or A063171), with the last leaf implicit, i.e., these words are given without the last trailing zero, except for the null tree which is encoded as 0.

Original entry on oeis.org

0, 1, 20, 11, 300, 201, 210, 120, 111, 4000, 3001, 3010, 2020, 2011, 3100, 2101, 2200, 1300, 1201, 2110, 1210, 1120, 1111, 50000, 40001, 40010, 30020, 30011, 40100, 30101, 30200, 20300, 20201, 30110, 20210, 20120, 20111, 41000, 31001, 31010

Offset: 0

Antti Karttunen, May 14 2002

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.

			The 11th term of A063171 is 10110010, corresponding to parenthesization ()(())(), thus its Łukasiewicz word is 3010. The 18th term of A063171 is 11011000, corresponding to parenthesization (()(())), thus its Łukasiewicz word is 1201. I.e., in the latter example there is one list on the top-level, which in turn contains two sublists, of which the first is zero elements long and the second is a sublist containing one empty sublist (the last zero is omitted).

A. Karttunen, Gatomorphisms and other excursions amidst the plane trees and parenthesizations (Includes the complete Scheme program for computing this sequence)
R. P. Stanley, Hipparchus, Plutarch, Schröder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
R. P. Stanley, Exercises on Catalan and Related Numbers
OEIS Wiki, Łukasiewicz words
Index entries for sequences related to Łukasiewicz
Index entries for sequences related to parenthesizing

For n >= 1, the number of zeros in the term a(n) is given by A057514(n)-1.
The first digit of each term is given by A057515.
Cf. A014486, A059984, A059985, A071152, A071154.
Corresponding factorial walk encoding: A071155 (A071157, A071159).
a(n) = A079436(n)/10.

A358497 Replace each new digit in n with index 1, 2, ..., 9, 0 in order in which that digit appears in n, from left to right.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 12, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 12

Offset: 0

Gleb Ivanov, Nov 19 2022

a(n) gives the canonical form which enumerates digits in order of their first occurrence in n, from left to right. a(n) uniquely defines the pattern of identical digits in n. - Dmytro Inosov, Jul 16 2024

			n = 10 has 2 different digits; replace first encountered digit 1 -> 1, replace second digit 0 -> 2, therefore a(10) = 12.
n = 141 has 3 digits, but only 2 different ones; replace first encountered digit 1 -> 1, replace second encountered digit 4 -> 2, therefore a(141) = 121.

David A. Corneth, Table of n, a(n) for n = 0..9999
Dmytro S. Inosov and Emil Vlasák, Cryptarithmically unique terms in integer sequences, arXiv:2410.21427 [math.NT], 2024. See pp. 3, 18.

Cf. A071159, A227362, A358615 (record high values).

A358497[k_] := With[{pI = Values@PositionIndex@IntegerDigits@k}, MapIndexed[#1 -> Mod[#2[[1]], 10] &, pI, {2}] // Flatten // SparseArray // FromDigits]; (* Dmytro Inosov, Jul 15 2024 *)

a(n) = {if(n == 0, return(1)); my(d = digits(n), m = Map(), t = 0); for(i = 1, #d, if(mapisdefined(m, d[i]), d[i] = mapget(m, d[i]) , t++; if(t == 10, t = 0); mapput(m, d[i], t); d[i] = t ) ); fromdigits(d) } \\ David A. Corneth, Nov 23 2022

def A358497(n):
    d,s,k = dict(),str(n),1
    for i in range(len(s)):
        if d.get(s[i],0) == 0:
            d[s[i]] = str(k)
            k = (k + 1)%10
    s_t = list(s)
    for i in range(len(s)):s_t[i] = d[s[i]]
    return int(''.join(s_t))
print([A358497(i) for i in range(100)])

def A358497(n):
    s, c, i  = str(n), {}, 49
    for d in map(ord,s):
        if d not in c:
            c[d] = i
            i += 1
    return int(s.translate(c)) # Chai Wah Wu, Jul 09 2024

a(a(n)) = a(n). - Dmytro Inosov, Jul 16 2024

A076050 Limiting sequence if we start with 2 and successively replace n with 2,3,4,...,n,n+1.

Original entry on oeis.org

2, 3, 2, 3, 4, 2, 3, 2, 3, 4, 2, 3, 4, 5, 2, 3, 2, 3, 4, 2, 3, 2, 3, 4, 2, 3, 4, 5, 2, 3, 2, 3, 4, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 2, 3, 4, 2, 3, 2, 3, 4, 2, 3, 4, 5, 2, 3, 2, 3, 4, 2, 3, 2, 3, 4, 2, 3, 4, 5, 2, 3, 2, 3, 4, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 2, 3, 4, 2, 3, 2, 3, 4, 2, 3, 4, 5, 2, 3, 2, 3, 4, 2, 3

Offset: 1

Miklos Kristof, Oct 30 2002

We get 2, 23, 23234, 23234232342345 and so on. The lengths are 1,2,5,14,42,... which are the Catalan numbers: A000108. The sums of the numbers in these strings are also the Catalan numbers.
In A071159 the n-digit terms follow the 2, 3, 2, 3, 4, ... rule: the number of terms in which the first n-1 digits are the same is 2, 3, 2, 3, 4, ... and the last digits of the terms are 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, ..., A007001. For example, 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1221, 1222, 1223, 1231, 1232, 1233, 1234.
a(A000108(n)) = n+1 and a(m) < n+1 for m < A000108(n). - Reinhard Zumkeller, Feb 17 2012
Let (T(1) < T(2) < ... < T(A000108(m))) denote the sequence of Young tableaux of shape (2^m) ordered lexicographically with respect to their columns, and let f(T(i), T(j)) denote the first label of disagreement among T(i) and T(j). Then, empirically, the reverse of the list (f(T(1), T(2)), f(T(1), T(3)), ..., f(T(1), T(A000108(m)))) agrees with the first A000108(m) - 1 terms in this sequence, for all m > 1, as illustrated in the below example. - John M. Campbell, Sep 07 2018

			From _John M. Campbell_, Sep 07 2018: (Start)
There are A000108(3) = 5 Young tableaux of shape (2^3) = (2, 2, 2), which are listed below lexicographically.
   [3 6]   [4 6]   [4 6]   [5 6]   [5 6]
   [2 5] < [2 5] < [3 5] < [2 4] < [3 4]
   [1 4]   [1 3]   [1 2]   [1 3]   [1 2]
As above, let (T(1), T(2), ..., T(5)) denote this list. The first label of disagreement between T(1) and T(5) is 2; that between T(1) and T(4) is 3; that between T(1) and T(3) is 2; that between T(1) and T(2) is 3. The sequence (2, 3, 2, 3) agrees with the first 4 terms in this sequence. If we repeat this process using Young tableaux of shape (2^4), we obtain the sequence (2, 3, 2, 3, 4, 2, 3, 2, 3, 4, 2, 3, 4). (End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Italo J. Dejter, The role of restricted growth strings in the two middle levels of the Boolean lattice B_(2k+1), University of Puerto Rico, 2018.
Italo J. Dejter, Reinterpreting Mütze's Theorem via Natural Enumeration of Ordered Rooted Trees, arXiv:1911.02100 [math.CO], 2019.

Cf. A000108, A071159, A007001.

a076050 n = a076050_list !! (n-1)
a076050_list = 2 : f [2] where
   f xs = (drop (length xs) xs') ++ (f xs') where
     xs' = concatMap ((enumFromTo 2) . (+ 1)) xs
-- Reinhard Zumkeller, Feb 17 2012

Nest[Flatten[Map[Range[2, #+1] &, #]] &, {2}, 5] (* Paolo Xausa, Mar 04 2024 *)

a(n)=local(v,w); if(n<1,0,v=[1]; while(#v

a(n) = A007001(n) + 1.

A071157 The zero-free, right-to-left factorial walk encoding for each rooted plane tree encoded by A014486. Sequence A071155 shown with factorial expansion (A007623).

Original entry on oeis.org

0, 1, 11, 21, 111, 211, 121, 221, 321, 1111, 2111, 1211, 2211, 3211, 1121, 2121, 1221, 2221, 3221, 1321, 2321, 3321, 4321, 11111, 21111, 12111, 22111, 32111, 11211, 21211, 12211, 22211, 32211, 13211, 23211, 33211, 43211, 11121, 21121, 12121

Offset: 0

Antti Karttunen, May 14 2002

Apart from the initial term (0, which encodes the null tree), if we scan the digits from the right (the least significant digit which is always 1) to the left (the most significant), then each successive digit to the left is at most one greater than the previous and never less than one.

Note: this finite decimal representation works only up to the 23712nd term, as the 23713rd such walk is already (10,9,8,7,6,5,4,3,2,1). The sequence A071158 shows the initial portion of this sequence sorted.

C. Banderier, A. Denise, P. Flajolet, M. Bousquet-Mélou et al., Generating Functions for Generating Trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
A. Karttunen, Gatomorphisms and other excursions amidst the plane trees and parenthesizations (Includes the complete Scheme program for computing this sequence)

Corresponding Łukasiewicz words: A071153.

Essentially the same as A071159 but with digits reversed.

a(n) = A007623(A071155(n)).

A278985 List of words of length n over an alphabet of size 3 that are in standard order.

Original entry on oeis.org

1, 11, 12, 111, 112, 121, 122, 123, 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1221, 1222, 1223, 1231, 1232, 1233, 11111, 11112, 11121, 11122, 11123, 11211, 11212, 11213, 11221, 11222, 11223, 11231, 11232, 11233, 12111, 12112, 12113, 12121, 12122

Offset: 1

N. J. A. Sloane, Dec 05 2016

We study words made of letters from an alphabet of size b, where b >= 1. We assume the letters are labeled {1,2,3,...,b}. There are b^n possible words of length n.
We say that a word is in "standard order" if it has the property that whenever a letter i appears, the letter i-1 has already appeared in the word.  This implies that all words begin with the letter 1.
These are the words described in row b=3 of the array in A278984.
A007051(n-1) gives the number of n-digit terms in this sequence. - Rémy Sigrist, Dec 18 2016

Rémy Sigrist and N. J. A. Sloane, Table of n, a(n) for n = 1..14767 [Terms 1 through 185 by N. J. A. Sloane]
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"

Cf. A278984, A007051.

Similar to but different from A071159.

b:= proc(n) option remember; `if`(n=1, [[1]], map(x->
      seq([x[], i], i=1..min(3, max(x[])+1)), b(n-1)))
    end:
T:= n-> map(x-> parse(cat(x[])), b(n))[]:
seq(T(n), n=1..5);  # Alois P. Heinz, Jan 02 2022

Table[FromDigits /@ Select[Tuples[Range@ 3, n], And[Times @@ Boole@ MapIndexed[#1 <= First@ #2 &, #] > 0, Max@ Differences@ # <= 1] &], {n, 5}] // Flatten (* Michael De Vlieger, Dec 18 2016 *)

gen(n, len, mx) = if (len==0, print1 (n ", "), for (d=1, min(mx+1, 3), gen(10*n + d, len-1, max(mx, d))))
for (len=1, 5, gen(0, len, 0)) \\ Rémy Sigrist, Dec 18 2016

A193023 Triangle read by rows: the n-th row has length A000110(n) and contains all set partitions of an n-set in canonical order.

Original entry on oeis.org

1, 11, 12, 111, 112, 121, 122, 123, 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1221, 1222, 1223, 1231, 1232, 1233, 1234, 11111, 11112, 11121, 11122, 11123, 11211, 11212, 11213, 11221, 11222, 11223, 11231, 11232, 11233, 11234, 12111, 12112, 12113, 12121

Offset: 1

N. J. A. Sloane, Jul 14 2011

The set partition of [1,2,3,4] given by 13/2/4 would be encoded as 1213: simply record which part i is in, for i=1..n.
To get row n, read row n-1 from left to right. If row n-1 contains a word abc...d, in which the maximal number is m, then in row n we place the words abc...d1, abc...d2, abc...d3, ..., abc...d(m+1).
This provides a canonical ordering for partitions of a labeled set.

			Triangle begins:
  1;
  11,12;
  111,112,121,122,123;
  1111,1112,1121,1122,1123,1211,1212,1213,1221,1222,1223,1231,1232,1233,1234;
  11111,11112,11121,11122,11123,...

Alois P. Heinz, Rows n = 1..8, flattened
R. Kaye, A Gray code for set partitions, Info. Proc. Letts., 5 (1976), 171-173.

This is different from A071159.

Cf. A000110, A120698.

b:= proc(n) option remember;
      `if`(n=1, [[1]], map(x-> seq([x[], i], i=1..max(x[])+1), b(n-1)))
    end:
T:= n-> map(x-> parse(cat(x[])), b(n))[]:
seq(T(n), n=1..5);  # Alois P. Heinz, Sep 30 2011

b[n_] := b[n] = If[n == 1, {{1}}, Table[Append[#, i], {i, 1, Max[#]+1}]& /@ b[n-1] // Flatten[#, 1]&];
T[n_] := FromDigits /@ b[n];
Array[T, 8] // Flatten (* Jean-François Alcover, Feb 19 2021, after Alois P. Heinz *)

A358615 Record high values in A358497.

Original entry on oeis.org

1, 12, 122, 123, 1222, 1223, 1232, 1233, 1234, 12222, 12223, 12232, 12233, 12234, 12322, 12323, 12324, 12332, 12333, 12334, 12342, 12343, 12344, 12345, 122222, 122223, 122232, 122233, 122234, 122322, 122323, 122324, 122332, 122333, 122334, 122342, 122343, 122344

Offset: 1

Gleb Ivanov, Nov 23 2022

Cf. A358497, A071159.

def A358497(n):
    d, s, k = dict(), str(n), 1
    for i in range(len(s)):
        if d.get(s[i], 0) == 0:
            d[s[i]] = str(k)
            k = (k + 1)%10
    s_t = list(s)
    for i in range(len(s)):s_t[i] = d[s[i]]
    return int(''.join(s_t))
terms = [1,]
for i in range(1, 10**6):
    if A358497(i)>terms[-1]:terms.append(A358497(i))
print(terms)

A231870 Elements of the sub-operad FCat(2) of TN generated by 00, 01, 02.

Original entry on oeis.org

1, 11, 12, 13, 111, 112, 113, 121, 122, 123, 124, 131, 132, 133, 134, 135, 1111, 1112, 1113, 1121, 1122, 1123, 1124, 1131, 1132, 1133, 1134, 1135, 1211, 1212, 1213, 1221, 1222, 1223, 1224, 1231, 1232, 1233, 1234, 1235, 1241, 1242, 1243, 1244, 1245, 1246, 1311, 1312, 1313, 1321, 1322, 1323, 1324, 1331, 1332, 1333, 1334

Offset: 1

N. J. A. Sloane, Nov 14 2013

nonn

Since nonzero terms in the OEIS may not begin with 0, 1 has been added to all the digits.

S. Giraudo, Combinatorial operads from monoids, arXiv preprint arXiv:1306.6938, 2013

Cf. A071159.

cp's OEIS Frontend

A239903 List of Restricted-Growth Strings a_{k-1}a_{k-2}...a_{2}a_{1}, with k=2 and a_1 in {0,1} or k>2, a_{k-1}=1 and a_{j+1}>=1+a_j, for k-1>j>0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Julia

MATLAB

Mathematica

Maxima

PARI

Scheme

Formula

Extensions

A071153 Łukasiewicz word for each rooted plane tree (interpretation e in Stanley's exercise 19) encoded by A014486 (or A063171), with the last leaf implicit, i.e., these words are given without the last trailing zero, except for the null tree which is encoded as 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A358497 Replace each new digit in n with index 1, 2, ..., 9, 0 in order in which that digit appears in n, from left to right.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

Formula

A076050 Limiting sequence if we start with 2 and successively replace n with 2,3,4,...,n,n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A071157 The zero-free, right-to-left factorial walk encoding for each rooted plane tree encoded by A014486. Sequence A071155 shown with factorial expansion (A007623).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A278985 List of words of length n over an alphabet of size 3 that are in standard order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A193023 Triangle read by rows: the n-th row has length A000110(n) and contains all set partitions of an n-set in canonical order.

Views

Author

Keywords

Comments

Examples

Links