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

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,2

Comments

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

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

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

Example

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

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

Prog

(PARI) a(n)=fibonacci(n)-3 \\ Charles R Greathouse IV, Feb 03 2014
(Magma) [Fibonacci(n)-3: n in [4..45]]; // G. C. Greubel, Jul 13 2019
(Sage) [fibonacci(n)-3 for n in (4..45)] # G. C. Greubel, Jul 13 2019
(GAP) List([4..45], n-> Fibonacci(n)-3) # G. C. Greubel, Jul 13 2019

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]

Sequence in context: A084835 A298107 A034350 * A185721 A304796 A103577

Adjacent sequences: A006324 A006325 A006326 * A006328 A006329 A006330

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, Simon Plouffe

Extensions

Offset corrected by Gary Detlefs, Apr 02 2012

Status

approved