A005270 Number of sequences s of length n with s[1]=1, s[2]=1, s[j-1]<s[j]<=s[j-2]+s[j-1] for j>=3. (Formerly M1684)

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

Offset

2,4

Comments

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

References

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

Links

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.

Formula

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] <s[j] <= s[j-2]+s[j-1] for j>=3. - Emeric Deutsch, Feb 15 2007

Example

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).

Maple

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

Prog

(PARI) {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 */

Crossrefs

Cf. A125051, A125052.

Cf. A005269.

Sequence in context: A227222 A370982 A130455 * A308444 A277611 A080839

Adjacent sequences: A005267 A005268 A005269 * A005271 A005272 A005273

Keyword

nonn

Author

N. J. A. Sloane.

Extensions

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

Edited by Emeric Deutsch, Feb 15 2007

Status

approved