|
| |
|
|
A000071
|
|
Fibonacci numbers - 1.
(Formerly M1056 N0397)
|
|
175
|
|
|
|
0, 0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583, 4180, 6764, 10945, 17710, 28656, 46367, 75024, 121392, 196417, 317810, 514228, 832039, 1346268, 2178308, 3524577, 5702886, 9227464, 14930351, 24157816, 39088168
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
Number of permutations p of {1,2,...,n-1} such that max|p(i)-i|=1. Example: a(4)=2 since only the permutations 132 and 213 of {1,2,3} satisfy the given condition. - Emeric Deutsch, Jun 04 2003
Number of 001-avoiding binary words of length n-3.
Also, sum of first n Fibonacci numbers. - Giorgi Dalakishvili (mcnamara_gio(AT)yahoo.com), Apr 02 2005
a(n)=number of partitions of {1,...,n-1} into two blocks in which only 1- or 2-strings of consecutive integers can appear in a block and there is at least one 2-string. E.g. a(6) = 7 because the enumerated partitions of {1,2,3,4,5} are 124/35,134/25, 14/235,13/245,1245/3,145/23,125/34. - A. O. Munagi (amunagi(AT)yahoo.com), Apr 11 2005
Numbers for which only one Fibonacci bit-representation is possible and for which the maximal and minimal Fibonacci bit-representations (A104326 and A014417) are equal. For example, a(12) = 10101 because 8+3+1 = 12. - Casey Mongoven, Mar 19 2006
Beginning with a(2), the 'Recaman transform' (see A005132) of the Fibonacci numbers (A000045). - Nick Hobson (nickh(AT)qbyte.org), Mar 01 2007
Starting with nonzero terms = row sums of triangle A158950. [From Gary W. Adamson, Mar 31 2009]
a(n+2) = minimum number of elements in an AVL tree of height n. [From Lennert Buytenhek (buytenh(AT)wantstofly.org), May 31 2010]
Contribution from Emeric Deutsch, Jun 14 2010: a(n) is the number of branch nodes in the Fibonacci tree of order n-1. A Fibonacci tree of order n (n>=2) is a complete binary tree whose left subtree is the Fibonacci tree of order n-1 and whose right subtree is the Fibonacci tree of order n-2; each of the Fibonacci trees of order 0 and 1 is defined as a single node (see the Knuth reference, p. 417).
a(n+3) is the number of distinct three-strand positive braids of length n (cf. Burckel). - Maxime Bourrigan, Apr 04 2011
A000119(a(n)) = 1. - Reinhard Zumkeller, Dec 28 2012
|
|
|
REFERENCES
|
Mohammad K. Azarian, The Generating Function for the Fibonacci Sequence, Missouri Journal of Mathematical Sciences, Vol. 2, No. 2, Spring 1990, pp. 78-79. Zentralblatt MATH, Zbl 1097.11516.
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 1.
Dairyko, Michael; Tyner, Samantha; Pudwell, Lara; Wynn, Casey. Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227. - From N. J. A. Sloane, Feb 01 2013
E. Deutsch, Math. Magazine, vol. 74, No. 5, 2001, p. 404, problem Q915.
Fumio Hazama, Spectra of graphs attached to the space of melodies, Discr. Math., 311 (2011), 2368-2383. See Table 2.1.
Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168-178. [From Emeric Deutsch, Jun 14 2010]
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417. [From Emeric Deutsch, Jun 14 2010]
R. Lagrange, Quelques re'sultats dans la me'trique des permutations, Annales Scientifiques de l'\'{E}cole Normale Sup\'{e}rieure, Paris, 79 (1962), 199-241.
D. A. Lind, On a class of nonlinear binomial sums, Fib. Quart., 3 (1965), 292-298.
Rui Liu and Feng-Zhen Zhao, On the Sums of Reciprocal Hyperfibonacci Numbers and Hyperlucas Numbers, Journal of Integer Sequences, Vol. 15 (2012), #12.4.5. - From N. J. A. Sloane, Oct 05 2012
L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), http://faculty.valpo.edu/lpudwell/slides/notredame.pdf, 2012. - From N. J. A. Sloane, Jan 03 2013
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 155.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
P. Xu, Growth of positive braids semigroups, Journal of Pure and Applied Algebra, 1992.
J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29.
|
|
|
LINKS
|
Christian G. Bower, Table of n, a(n) for n=1..500
S. Burckel, Syntactical methods for braids of three strands, J. Symbolic Comput. 31 (2001), no. 5, 557-564.
A. Burstein and T. Mansour, Counting occurrences of some subword patterns.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Fan Chung, Ron Graham, Primitive juggling sequences, Am. Math. Monthly 115 (3) (2008) 185-194
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 384
R. Lagrange, Quelques re'sultats dans la me'trique des permutations, Annales Scientifiques de l'\'{E}cole Normale Sup\'{e}rieure, Paris, 79 (1962), 199-241.
A. O. Munagi, Set Partitions with Successions and Separations,IJMMS 2005:3 (2005), 451-463.
Sam Northshield, Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,..., Amer. Math. Month., Vol. 117 (7), pp. 581-598, 2010.
_Simon Plouffe_, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
_Simon Plouffe_, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
Index entries for sequences related to linear recurrences with constant coefficients, signature (2,0,-1).
|
|
|
FORMULA
|
a(n) = A000045(n)-1.
a(1)=0, a(2)=0; thereafter a(n)=a(n-1)+a(n-2)+1.
a(n) = 2*a(n-1)-a(n-3). [From R. H. Hardin, Apr 02 2011]
Partial sums of Fibonacci numbers. G.f.: x^3/((1-x-x^2)*(1-x)). [Wolfdieter Lang ]
a(n)=-1+(A*B^n+C*D^n)/10, with A, C=5+-3*sqrt(5), B, D=(1+-sqrt(5))/2. - Ralf Stephan, Mar 02 2003
a(1)=0, a(2)=0, a(3)=1, then a(n)=ceiling(phi*a(n-1)) where phi is the golden ratio (1+sqrt(5))/2 - Benoit Cloitre, May 06 2003
Conjecture: for all c such that 2*(2-Phi) <= c < (2+Phi)*(2-Phi) we have a(n) = floor(Phi*a(n-1)+c) for n > 3 - Gerald McGarvey, Jul 22 2004
a(n)=sum{k=0..floor((n-2)/2), binomial(n-k-2, k+1)} - Paul Barry, Sep 23 2004
a(n+3)=sum{k=0..floor(n/3), binomial(n-2k, k)(-1)^k*2^(n-3k)} - Paul Barry, Oct 20 2004
a(n+1)=Sum(binomial(n-r, r)), r=1, 2, ... which is the case t=2 and k=2 in the general case of t-strings and k blocks: a(n+1, k, t)=Sum(binomial(n-r*(t-1), r)*S2(n-r*(t-1)-1, k-1)), r=1, 2, ... - A. O. Munagi (amunagi(AT)yahoo.com), Apr 11 2005
a(n) = Sum[k*Fibonacci(n-k-3),{k,0,n-2}] - Ross La Haye (rlahaye(AT)new.rr.com), May 31 2006
a(n) = term (3,2) in the 3x3 matrix [1,1,0; 1,0,0; 1,0,1]^n. - Alois P. Heinz, Jul 24 2008
For n>=4, a(n)=ceil(phi*a(n-1)), where phi=Golden ratio. [From Vladimir Shevelev, Jul 04 2010]
Closed-form without two leading zeros G.f.: 1/(1-2*x-x^3); ((5+2*sqrt(5))*((1+sqrt(5))/2)^n + (5-2*sqrt(5))*((1-sqrt(5))/2)^n - 5)/5
Closed-form with two leading zeros G.f.: x^2/(1-2*x-x^3); ((5+sqrt(5))*((1+sqrt(5))/2)^n + (5-sqrt(5))*((1-sqrt(5))/2)^n - 10)/10 Tim Monahan (tmonahan54ATgmail.com), Jul 10 2011
|
|
|
MAPLE
|
a[0]:=0:a[1]:=0:for n from 2 to 50 do a[n]:=a[n-1]+a[n-2]+1 od: seq(a[n], n=0..50); (Kristof)
A000071 := proc(n) combinat[fibonacci](n)-1 ; end proc; # R. J. Mathar, Apr 07 2011
A000071:=1/(z-1)/(z^2+z-1); [Simon Plouffe in his 1992 dissertation, dropping initial zeros.]
a := n -> (Matrix ([[1, 1, 0], [1, 0, 0], [1, 0, 1]])^n)[3, 2]; seq (a(n), n=0..50); - Alois P. Heinz, Jul 24 2008
|
|
|
MATHEMATICA
|
Table[f=Fibonacci[k]; f-1, {k, 1, 40, 1}] (* Vladimir Orlovsky, Jul 21 2008 *)
|
|
|
PROG
|
(PARI) a(n)=if(n<1, 0, fibonacci(n)-1)
sage: from sage.combinat.sloane_functions import recur_gen2 sage: it = recur_gen2(1, 1, 1, 1) sage: [it.next()-1 for i in xrange(0, 39)] - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jul 06 2008
(MAGMA) [Fibonacci(n)-1: n in [1..150]] // Vincenzo Librandi, Apr 04 2011
|
|
|
CROSSREFS
|
Cf. A054761.
Antidiagonal sums of array A004070.
Right-hand column 2 of triangle A011794.
Cf. A105488, A105489.
a(n) = A101220(1, 1, n-2), for n > 1.
Cf. A119282, A001654, A005968, A005969, A098531, A098532, A098533, A128697.
Cf. A001611, 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]
Cf. A158950 [From Gary W. Adamson, Mar 31 2009]
Related to sum of Fibonacci(kn) over n. Cf. A099919, A058038, A138134, A053606
Sequence in context: A126348 A006731 A222036 * A179111 A093607 A005182
Adjacent sequences: A000068 A000069 A000070 * A000072 A000073 A000074
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
Removed attribute "conjectured" from Simon Plouffe g.f. - R. J. Mathar, Mar 11 2009
Edited by N. J. A. Sloane, Apr 04 2011
|
|
|
STATUS
|
approved
|
| |
|
|
