A080237 Start with 1 and apply the process: k-th run is 1, 2, 3, ..., a(k-1)+1.

1, 1, 2, 1, 2, 1, 2, 3, 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, 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

Offset: 1

Author

Benoit Cloitre, Mar 18 2003

Keywords

• nonn
• tabf

Comments

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

Examples

			As an irregular triangle:
  1;
  1,2;
  1,2,1,2,3;
  1,2,1,2,3,1,2,1,2,3,1,2,3,4;
  ...
Sequence begins: 1,(1,2),(1,2),(1,2,3), ... where runs are between 2 parentheses. 5th run is (1,2) since a(4)=1 and sequence continues: 1,1,2,1,2,1,2,3,1,2....
G.f. = x + x^2 + 2*x^3 + x^4 + 2*x^5 + x^6 + 2*x^7 + 3*x^8 + x^9 + 2*x^10 + ...
		

Links

• Reinhard Zumkeller, Rows n = 1..10 of triangle, flattened
• 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.
• Antti Karttunen, Notes concerning A080237-tree and related sequences.
• R. P. Stanley, Catalan addendum. See the interpretation (www, "Vertices of height n-1 of the tree T ...").

Crossrefs

Cf. A000002, A007001. Positions of ones: A085223. The first occurrence of each n is at A014138(n). See A085178.

Programs

Haskell

a080237 n k = a080237_tabf !! (n-1) !! (k-1)
a080237_row n = a080237_tabf !! (n-1)
a080237_tabf = [1] : f a080237_tabf where
   f [[]] =[]
   f (xs:xss) = concatMap (enumFromTo 1 . (+ 1)) xs : f xss
a080237_list = concat a080237_tabf
-- Reinhard Zumkeller, Jun 01 2015

Mathematica

run[1] = {1}; run[k_] := run[k] = Range[ Flatten[ Table[run[j], {j, 1, k-1}]][[k-1]] + 1]; Table[run[k], {k, 1, 29}] // Flatten (* Jean-François Alcover, Sep 12 2012 *)
NestList[ Flatten[# /. # -> Range[# + 1]] &, {1}, 5] // Flatten (* Robert G. Wilson v, Jun 24 2014 *)

PARI

{a(n) = my(v, i, j, k); if( n<1, 0, v=vector(n); for(m=1, n, v[m]=k++; if( k>j, j=v[i++]; k=0)); v[n])}; /* Michael Somos, Jun 24 2014 */

Formula

It seems that Sum_{k=1..n} a(k) = C*n*log(log(n)) + O(n*log(log(n))) with C = 0.6....

a(n) = A007814(A014486(n)) (i.e., number of trailing zeros in A063171(n)).