%I M1371 #67 Sep 08 2022 08:44:34
%S 0,2,5,10,18,31,52,86,141,230,374,607,984,1594,2581,4178,6762,10943,
%T 17708,28654,46365,75022,121390,196415,317808,514226,832037,1346266,
%U 2178306,3524575,5702884,9227462,14930349,24157814,39088166,63245983,102334152,165580138
%N a(n) = Fibonacci(n) - 3. Number of total preorders.
%C Minimal cost of maximum height Huffman tree of size n. - Alex Vinokur (alexvn(AT)barak-online.net), Oct 25 2004
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A006327/b006327.txt">Table of n, a(n) for n = 4..1000</a>
%H G. Kreweras, <a href="http://www.numdam.org/item?id=MSH_1976__53__5_0">Les préordres totaux compatibles avec un ordre partiel</a>, Math. Sci. Humaines No. 53 (1976), 5-30.
%H G. Kreweras, <a href="/A019538/a019538.pdf">Les préordres totaux compatibles avec un ordre partiel</a>, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Tsikouras/tsikouras67.html">On the Dominance Partial Ordering of Dyck Paths</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.
%H A. B. Vinokur, <a href="http://dx.doi.org/10.1007/BF01068684">Huffman trees and Fibonacci numbers</a>, Kibernetika Issue 6 (1986) 9-12 (in Russian); English translation in Cybernetics 21, Issue 6 (1986), 692-696.
%H Alex Vinokur, <a href="http://arXiv.org/abs/cs/0410013">Fibonacci connection between Huffman codes and Wythoff array</a>, arXiv:cs/0410013 [cs.DM], 2004-2005.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1).
%F G.f.: x^5*(2 + x)/((1-x)*(1-x-x^2)).
%F a(n) = a(n-1) + a(n-2) + 3.
%F a(n+3) = Sum_{k=-n+1..n} F(abs(n)+1). - _Paul Barry_, Oct 24 2007
%F a(n) = F(4*n) mod F(n+1) = F(n) - (F(n+4)^2 - F(n)^2)/F(2*n+4). - _Gary Detlefs_, Apr 02 2012
%e G.f. = 2*x^5 + 5*x^6 + 10*x^7 + 18*x^8 + 31*x^9 + 52*x^10 + 86*x^11 + ...
%p with(combinat):a:=n->sum(fibonacci(j),j=3..n): seq(a(n),n=2..40); # _Zerinvary Lajos_, Oct 03 2007
%p A006327:=(2+z)/(z-1)/(z**2+z-1); # conjectured by _Simon Plouffe_ in his 1992 dissertation
%t Fibonacci[Range[4, 45]] - 3 (* _Vladimir Joseph Stephan Orlovsky_, Mar 19 2010 *)
%o (PARI) a(n)=fibonacci(n)-3 \\ _Charles R Greathouse IV_, Feb 03 2014
%o (Magma) [Fibonacci(n)-3: n in [4..45]]; // _G. C. Greubel_, Jul 13 2019
%o (Sage) [fibonacci(n)-3 for n in (4..45)] # _G. C. Greubel_, Jul 13 2019
%o (GAP) List([4..45], n-> Fibonacci(n)-3) # _G. C. Greubel_, Jul 13 2019
%Y A diagonal of A079502.
%Y Cf. A000045, A001611, A000071, A157725, A001911, A157726, A006327, A157727, A157728, A157729, A167616. [Added by _N. J. A. Sloane_, Jun 25 2010 in response to a comment from _Aviezri S. Fraenkel_]
%K nonn,easy,nice
%O 4,2
%A _N. J. A. Sloane_, _Simon Plouffe_
%E Offset corrected by _Gary Detlefs_, Apr 02 2012