

A007001


Trajectory of 1 under the morphism 1 > 12, 2 > 123, 3 > 1234, etc.
(Formerly M0108)


15



1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Records in this sequence occur at positions: 1, 2, 5, 14, 42, 132, 429, 1430, ... (which appear to be the Catalan numbers A000108).  Robert G. Wilson v, May 07 2005
The records do occur at Catalan numbers. Of the first C(n) numbers, the number that are equal to k is A033184(n,k), with the one n last.  Franklin T. AdamsWatters, Mar 29 2009
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, if we take away the zeros from (f(T(1), T(A000108(m)  i + 1))  f(T(A000108(m)  i), T(A000108(m)  i + 1)), i=1..A000108(m)1), we obtain the first A000108(m  1)  1 terms in this sequence. This is illustrated in the below example.  John M. Campbell, Sep 07 2018


REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
J. West, Generating trees and forbidden subsequences, Proc. 6th FPSAC [ Conference on Formal Power Series and Algebraic Combinatorics ] (1994), pp. 441450 (see p. 443).


LINKS

T. D. Noe, Table of n, a(n) for n = 1..4862 (8 iterations)
C. Banderier, A. Denise, P. Flajolet, M. BousquetMÃ©lou et al., Generating Functions for Generating Trees, Discrete Mathematics 246(13), March 2002, pp. 2955.
A. Karttunen, Notes concerning A080237tree and related sequences.
S. Lehr, J. Shallit and J. Tromp, On the vector space of the automatic reals, Theoret. Comput. Sci. 163 (1996), no. 12, 193210.
James Propp and N. J. A. Sloane, Email, March 1994
Index entries for sequences that are fixed points of mappings


FORMULA

From n > 1 onward a(n) = A080237(A081291(n1)).  Antti Karttunen, Jul 31 2003


EXAMPLE

From John M. Campbell, Sep 07 2018: (Start)
Letting m = 5, as above let (T(1) < T(2) < ... < T(42)) denote the lexicographic sequence of Young tableaux of shape (2, 2, 2, 2, 2). In this case, the sequence (f(T(1), T(43  i))  f(T(42  i), T(43  i)), i=1..41) is equal to (0, 1, 0, 0, 2, 0, 1, 0, 0, 2, 0, 0, 0, 3, 0, 1, 0, 0, 2, 0, 1, 0, 0, 2, 0, 0, 0, 3, 0, 1, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0). Removing the zeroes from this tuple, we obtain (1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3), which gives us the first 13 = A000108(m  1)  1 terms in this sequence. For example, the first term in the preceding tuple is 0 since T(1) and T(42) are respectively
[ 5 10] [ 9 10]
[ 4 9 ] [ 7 8 ]
[ 3 8 ] [ 5 6 ]
[ 2 7 ] [ 3 4 ]
[ 1 6 ] [ 1 2 ]
and T(41) is equal to
[ 9 10]
[ 7 8 ]
[ 5 6 ]
[ 2 4 ]
[ 1 3 ]
so that the first letter of disagreement between T(1) and T(42) is 2, and that between T(41) and T(42) is also 2. (End)


MATHEMATICA

Nest[ Flatten[ # /. a_Integer > Range[a + 1]] &, {1}, 6] (* Robert G. Wilson v, Jan 24 2006 *)


PROG

(PARI) a(n)=local(v, w); if(n<1, 0, v=[1]; while(#v<n, w=[]; for(i=1, #v, w=concat(w, vector(v[i]+1, j, j))); v=w); v[n])


CROSSREFS

Cf. A000245, A085182. a(n)=A076050(n)1. Partial sums: A080336. Positions of ones: A085197. The first occurrence of each n is at A000108(n). See A085180.
Sequence in context: A171712 A091412 A106036 * A094917 A082691 A280052
Adjacent sequences: A006998 A006999 A007000 * A007002 A007003 A007004


KEYWORD

easy,nonn,nice


AUTHOR

N. J. A. Sloane, Mira Bernstein, James Propp


EXTENSIONS

More terms from Larry Reeves (larryr(AT)acm.org), Sep 22 2000


STATUS

approved



