A006327 a(n) = Fibonacci(n) - 3. Number of total preorders.

0, 2, 5, 10, 18, 31, 52, 86, 141, 230, 374, 607, 984, 1594, 2581, 4178, 6762, 10943, 17708, 28654, 46365, 75022, 121390, 196415, 317808, 514226, 832037, 1346266, 2178306, 3524575, 5702884, 9227462, 14930349, 24157814, 39088166, 63245983, 102334152, 165580138

Offset: 4

Author

N. J. A. Sloane, Simon Plouffe

Keywords

• nonn
• easy
• nice

Comments

Minimal cost of maximum height Huffman tree of size n. - Alex Vinokur (alexvn(AT)barak-online.net), Oct 25 2004

Examples

			G.f. = 2*x^5 + 5*x^6 + 10*x^7 + 18*x^8 + 31*x^9 + 52*x^10 + 86*x^11 + ...
		

References

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

Links

• T. D. Noe, Table of n, a(n) for n = 4..1000
• G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
• G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• A. Sapounakis, I. Tasoulas and P. Tsikouras, On the Dominance Partial Ordering of Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.
• A. B. Vinokur, Huffman trees and Fibonacci numbers, Kibernetika Issue 6 (1986) 9-12 (in Russian); English translation in Cybernetics 21, Issue 6 (1986), 692-696.
• Alex Vinokur, Fibonacci connection between Huffman codes and Wythoff array, arXiv:cs/0410013 [cs.DM], 2004-2005.
• Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Crossrefs

A diagonal of A079502.

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]

Programs

GAP

List([4..45], n-> Fibonacci(n)-3) # G. C. Greubel, Jul 13 2019

Magma

[Fibonacci(n)-3: n in [4..45]]; // G. C. Greubel, Jul 13 2019

Maple

with(combinat):a:=n->sum(fibonacci(j),j=3..n): seq(a(n),n=2..40); # Zerinvary Lajos, Oct 03 2007
A006327:=(2+z)/(z-1)/(z**2+z-1); # conjectured by Simon Plouffe in his 1992 dissertation

Mathematica

Fibonacci[Range[4, 45]] - 3 (* Vladimir Joseph Stephan Orlovsky, Mar 19 2010 *)

PARI

a(n)=fibonacci(n)-3 \\ Charles R Greathouse IV, Feb 03 2014

Sage

[fibonacci(n)-3 for n in (4..45)] # G. C. Greubel, Jul 13 2019

Formula

G.f.: x^5*(2 + x)/((1-x)*(1-x-x^2)).

a(n) = a(n-1) + a(n-2) + 3.

a(n+3) = Sum_{k=-n+1..n} F(abs(n)+1). - Paul Barry, Oct 24 2007

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

Extensions

Offset corrected by Gary Detlefs, Apr 02 2012