|
%I M1234 #31 Mar 03 2020 10:26:57
%S 1,2,4,10,31,127,711,5621,64049,1067599,26287664,963023487,
%T 52766766100,4342736509018,538755914902622,101067429677072459,
%U 28751803102222498512,12436935036300286507123,8200693250120852291693833,8262592110164298068793701546
%N a(n) = number of length-n sequences s with s[1]=1, s[2]=1, s[k-1] <=s[k] <= s[k-2]+s[k-1] (s is called a sub-Fibonacci sequence of length n).
%D Fishburn, Peter C.; Roberts, Fred S., Uniqueness in finite measurement. Applications of combinatorics and graph theory to the biological and social sciences, 103--137, IMA Vol. Math. Appl., 17, Springer, New York, 1989. MR1009374 (90e:92099)
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A005269/b005269.txt">Table of n, a(n) for n = 2..70</a>
%H Peter C. Fishburn and Fred S. Roberts, <a href="/A005269/a005269.pdf">Uniqueness in finite measurement</a>, in Applications of combinatorics and graph theory to the biological and social sciences, 103--137, IMA Vol. Math. Appl., 17, Springer, New York, 1989. MR1009374 (90e:92099). [Annotated scan of five pages only]
%H Peter C. Fishburn and Fred S. Roberts, <a href="https://doi.org/10.1016/0166-218X(93)90236-H">Elementary sequences, sub-Fibonacci sequences</a>, Discrete Appl. Math. 44 (1993), no. 1-3, 261-281.
%F See the Maple program; f[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]. - _Emeric Deutsch_ and _Don Reble_, Feb 07 2005
%e G.f. = x^2 + 2*x^3 + 4*x^4 + 10*x^5 + 31*x^6 + 127*x^7 + 711*x^8 + 5621*x^9 + ...
%e a(4)=4 because we have (1,1,1,1), (1,1,1,2), (1,1,2,2), (1,1,2,3).
%p f[0]:=1:for k from 0 to 19 do f[k+1]:=expand(sum(subs({x=y,y=z},f[k]),z=y..x+y)) od: seq(subs({x=1,y=1},f[k]),k=0..19);
%o (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 */
%Y Sequences in the Fishburn-Roberts (1989) article: A005269, A005268, A234595, A005272, A003513, A008926.
%K nonn
%O 2,2
%A _N. J. A. Sloane_.
%E More terms from _Emeric Deutsch_ and _Don Reble_, Feb 07 2005
|
