A125052 -id:A125052 - cp's OEIS frontend

A005270 Number of sequences s of length n with s[1]=1, s[2]=1, s[j-1]=3.

1, 1, 1, 2, 6, 27, 177, 1680, 23009, 455368, 13067353, 546378617, 33472296082, 3021920660821, 404374532614122, 80646410554881100, 24095492607316134304, 10837141045948365696938, 7369252748590790186483284, 7606603491185739308318700818

Offset: 2

N. J. A. Sloane

nonn

The sequences of length n that are counted here are sub-Fibonacci sequences (A005269) with the property that its members, except for the initial two terms, strictly increase. - Emeric Deutsch, Feb 15 2007

			G.f. = x^2 + x^3 + x^4 + 2*x^5 + 6*x^6 + 27*x^7 + 177*x^8 + 1680^x^9 + ...
a(2)=6 because we have (1,1,2,3,4,5), (1,1,2,3,4,6), (1,1,2,3,4,7), (1,1,2,3,5,6), (1,1,2,3,5,7) and (1,1,2,3,5,8).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 2..70
Peter C. Fishburn and Fred S. Roberts, Elementary sequences, sub-Fibonacci sequences, Discrete Appl. Math. 44 (1993), no. 1-3, 261-281.

Cf. A125051, A125052.

Cf. A005269.

g[0]:=1:for k from 0 to 20 do g[k+1]:=expand(sum(subs({x=y, y=z}, g[k]), z=y+1..x+y)) od:seq(subs({x=1, y=1}, g[k]), k=0..20); # Emeric Deutsch, Feb 15 2007

{a(n) = if(n<2, return(0)); my(c, e); forvec(s=vector(n, i, [1, fibonacci(i)]), e=0; for(k=3, n, if( s[k-1]>=s[k] || s[k]>s[k-2]+s[k-1], e=1; break)); if(e, next); c++, 1); c}; /* Michael Somos, Dec 02 2016 */

a(n) equals the number of nodes in generation n-2 of the sub-Fibonacci tree (A125051) for n>=2. - Paul D. Hanna, Nov 19 2006

See the Maple program; g[k](x, y) is the number of sequences s[1], s[2], ..., s[k+2] such that s[1]=x, s[2]=y, s[j-1] =3. - Emeric Deutsch, Feb 15 2007

a(12) from Paul D. Hanna, Nov 19 2006

Edited by Emeric Deutsch, Feb 15 2007

A125051 The sub-Fibonacci tree; a rooted tree in which every node with label k and parent node with label g has g child nodes that are assigned labels beginning with k+1 through k+g; the tree starts at generation n=0 with a root node labeled '1' and a child node labeled '2'.

Original entry on oeis.org

1, 2, 3, 4, 5, 5, 6, 7, 6, 7, 8, 6, 7, 8, 9, 7, 8, 9, 10, 8, 9, 10, 11, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 9, 10, 11, 12, 13, 7, 8, 9, 10, 11, 8, 9, 10, 11, 12, 9, 10, 11, 12, 13, 10, 11, 12, 13, 14, 8, 9, 10, 11, 12, 13, 9, 10, 11, 12, 13, 14, 10, 11, 12, 13, 14, 15, 11, 12, 13, 14, 15, 16, 9

Offset: 0

Paul D. Hanna, Nov 19 2006

The maximum label for nodes in generation n is Fibonacci(n+2) for n>=0. The total number of nodes in generation n equals A005270(n+2) for n>=0. The sum of the labels for nodes in generation n equals A125052(n).

			The initial nodes of the tree for generations 0..5 are:
gen.0: [1];
gen.1: [2];
gen.2: [3];
gen.3: [4,5];
gen.4: (4)->[5,6,7],(5)->[6,7,8];
gen.5: (5)->[6,7,8,9],(6)->[7,8,9,10],(7)->[8,9,10,11],
(6)->[7,8,9,10,11],(7)->[8,9,10,11,12],(8)->[9,10,11,12,13].
By definition, there are 2 child nodes for node [3] of gen.2 since the parent of node [3] has label 2;
likewise, there are 3 child nodes for nodes [4] and [5] of gen.3 since the parent of both nodes has label 3.
The number of nodes in generation n begins:
1, 1, 1, 2, 6, 27, 177, 1680, 23009, 455368, 13067353, ...
The sum of the labels for nodes in generation n begins:
1, 2, 3, 9, 39, 252, 2361, 32077, 631058, 18035534, ...

Alois P. Heinz, Table of n, a(n) for n = 0..24903 (generations 0..8)
Peter C. Fishburn and Fred S. Roberts, Elementary sequences, sub-Fibonacci sequences, Discrete Appl. Math. 44 (1993), no. 1-3, 261-281.

Cf. A005270, A125052.

g:= proc(n) option remember; `if`(n=0, [[1, 1]],
      map(x-> seq([x[2], x[2]+i], i=1..x[1]), g(n-1)))
    end:
T:= n-> map(x-> x[2], g(n)):
a:= proc() local i, l; i, l:= -1, []; proc(n) while
      nops(l)<=n do i:=i+1; l:=[l[], T(i)[]] od; l[n+1] end
    end():
seq(a(n), n=0..200);  # Alois P. Heinz, Feb 08 2013

cp's OEIS Frontend

A005270 Number of sequences s of length n with s[1]=1, s[2]=1, s[j-1]=3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions