

A000071


a(n) = Fibonacci(n)  1.
(Formerly M1056 N0397)


276



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

a(n) is the number of allowable transition rules for passing from one change to the next (on n1 bells) in the English art of bellringing. This is also the number of involutions in the symmetric group S_{n1} which can be represented as a product of transpositions of consecutive numbers from {1, 2, ..., n1}. Thus for n = 6 we have a(6) from (12), (12)(34), (12)(45), (23), (23)(45), (34), (45), for instance. See my 1983 Math. Proc. Camb. Phil. Soc. paper.  Arthur T. White, letter to N. J. A. Sloane, Dec 18 1986
Number of permutations p of {1, 2, ..., n1} such that maxp(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 [For a(5) = 4 we have 2143, 1324, 2134 and 1243.  Jon Perry, Sep 14 2013]
Number of 001avoiding binary words of length n3. a(n) is the number of partitions of {1, ..., n1} into two blocks in which only 1 or 2strings of consecutive integers can appear in a block and there is at least one 2string. 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.  Augustine O. Munagi, Apr 11 2005
Numbers for which only one Fibonacci bitrepresentation is possible and for which the maximal and minimal Fibonacci bitrepresentations (A104326 and A014417) are equal. For example, a(12) = 10101 because 8 + 3 + 1 = 12.  Casey Mongoven, Mar 19 2006
a(n+2) is the minimum number of elements in an AVL tree of height n.  Lennert Buytenhek (buytenh(AT)wantstofly.org), May 31 2010
a(n) is the number of branch nodes in the Fibonacci tree of order n1. A Fibonacci tree of order n (n >= 2) is a complete binary tree whose left subtree is the Fibonacci tree of order n1 and whose right subtree is the Fibonacci tree of order n2; each of the Fibonacci trees of order 0 and 1 is defined as a single node (see the Knuth reference, p. 417).  Emeric Deutsch, Jun 14 2010
a(n+3) is the number of distinct threestrand positive braids of length n (cf. Burckel).  Maxime Bourrigan, Apr 04 2011
a(n+1) is the number of compositions of n with maximal part 2.  Joerg Arndt, May 21 2013
a(n+2) is the number of leafs of greatgrandparent DAG (directed acyclic graph) of height n. A greatgrandparent DAG of height n is a single node for n = 1; for n > 1 each leaf of ggpDAG(n1) has two child nodes where pairs of adjacent new nodes are merged into single node if and only if they have disjoint grandparents and same greatgrandparent. Consequence: a(n) = 2*a(n1)  a(n3).  Hermann StammWilbrandt, Jul 06 2014
We can establish Gerald McGarvey's conjecture mentioned in the Formula section, however we require n > 4. We need the following 4 prerequisites.
(1) a(n) = F(n)  1, with {F(n)}_{n >= 1} the Fibonacci numbers A000045. (2) (Binet form) F(n) = (d^n  e^n)/sqrt(5) with d = phi and e = 1  phi, de = 1 and d + e = 1. It follows that a(n) = (d(n)  e(n))/sqrt(5)  1. (3) To prove floor(x) = y is equivalent to proving that x  y lies in the halfopen interval [0, 1). (4) The series {s(n) = c1 x^n + c2}_{n >= 1}, with 1 < x < 0, and c1 and c2 positive constants, converges by oscillation with s(1) < s(3) < s(5) < ... < s(6) < s(4) < s(2). If follows that for any odd n, the open interval (s(n), s(n+1)) contains the subsequence {s(t)}_{t >= n + 2}. Using these prerequisites we can analyze the conjecture.
Using prerequisites (2) and (3) we see we must prove, for all n > 4, that d((d^(n1)  e^(n1))/sqrt(5)  1)  (d^n  e^n)/sqrt(5) + 1 + c lies in the interval [0, 1). But de = 1, implying de^(n1) = e^(n2). It follows that we must equivalently prove (for all n > 4) that E(n, c) = (e^(n2) + e^n)/sqrt(5) + 1  d + c = e^(n2) (e^2 + 1)/sqrt(5) + e + c lies in [0, 1). Clearly, for any particular n, E(n, c) has extrema (maxima, minima) when c = 2*(1d) and c = (1+d)*(1d). Therefore, the proof is completed by using prerequisite (4). It suffices to verify E(5, 2*(1d)) = 0, E(6, 2*(1d)) = 0.236068, E(5, (1d)*(1+d)) = 0.618034, E(6, (1d)*(1+d)) = 0.854102, all lie in [0, 1).
(End)
a(n) can be shown to be the number of distinct nonempty matchings on a path with n vertices. (A matching is a collection of disjoint edges.)  Andrew Penland, Feb 14 2017
Also, for n > 3, the lexicographically earliest sequence of positive integers such that {phi*a(n)} is located strictly between {phi*a(n1)} and {phi*a(n2)}.  Ivan Neretin, Mar 23 2017
Number of sequences (e(1), ..., e(n2)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) <= e(k). [Martinez and Savage, 2.5]
Number of sequences (e(1), ..., e(n2)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) <= e(k) and e(i) != e(k). [Martinez and Savage, 2.5]
(End)
Numbers whose Zeckendorf (A014417) and dual Zeckendorf (A104326) representations are the same: alternating digits of 1 and 0.  Amiram Eldar, Nov 01 2019
a(n+2) is the length of the longest array whose local maximum element can be found in at most n reveals. See link to the puzzle by Alexander S. Kulikov.  Dmitry Kamenetsky, Aug 08 2020
a(n+2) is the number of nonempty subsets of {1,2,...,n} that contain no consecutive elements. For example, the a(6)=7 subsets of {1,2,3,4} are {1}, {2}, {3}, {4}, {1,3}, {1,4} and {2,4}.  Muge Olucoglu, Mar 21 2021
a(n+3) is the number of allowed patterns of length n in the even shift (that is, a(n+3) is the number of binary words of length n in which there are an even number of 0s between any two occurrences of 1). For example, a(7)=12 and the 12 allowed patterns of length 4 in the even shift are 0000, 0001, 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1100, 1110, 1111.  Zoran Sunic, Apr 06 2022
Conjecture: for k a positive odd integer, the sequence {a(k^n): n >= 1} is a strong divisibility sequence; that is, for n, m >= 1, gcd(a(k^n), a(k^m)) = a(k^gcd(n,m)).  Peter Bala, Dec 05 2022
In general, the sum of a secondorder linear recurrence having signature (c,d) will be a thirdorder recurrence having a signature (c+1,dc,d).  Gary Detlefs, Jan 05 2023


REFERENCES

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 1.
GCHQ, The GCHQ Puzzle Book, Penguin, 2016. See page 28.
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 64.
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, AddisonWesley, Reading, MA, 1998, p. 417.
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).
J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 2129.


LINKS

Isha Agarwal, Matvey Borodin, Aidan Duncan, Kaylee Ji, Tanya Khovanova, Shane Lee, Boyan Litchev, Anshul Rastogi, Garima Rastogi, and Andrew Zhao, From Unequal Chance to a Coin Game Dance: Variants of Penney's Game, arXiv:2006.13002 [math.HO], 2020.
Emeric Deutsch, Problem Q915, Math. Magazine, vol. 74, No. 5, 2001, p. 404.
Christian Ennis, William Holland, Omer Mujawar, Aadit Narayanan, Frank Neubrander, Marie Neubrander, and Christina Simino, Words in Random Binary Sequences I, arXiv:2107.01029 [math.GM], 2021.
Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 96.
Sam Northshield, Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,..., Amer. Math. Month., Vol. 117 (7), pp. 581598, 2010.
Arthur T. White, Ringing the changes, Math. Proc. Cambridge Philos. Soc. 94 (1983), no. 2, 203215.


FORMULA

a(0) = 1, a(1) = 0; thereafter a(n) = a(n1) + a(n2) + 1.
G.f.: x^3/((1xx^2)*(1x)).  Simon Plouffe in his 1992 dissertation, dropping initial 0's
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(n1)) 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(n1) + c) for n > 4.  Gerald McGarvey, Jul 22 2004. This is true provided n > 3 is changed to n > 4, see proof in Comments section.  Russell Jay Hendel, Mar 15 2015
a(n) = Sum_{k = 0..floor((n2)/2)} binomial(nk2, k+1).  Paul Barry, Sep 23 2004
a(n+3) = Sum_{k = 0..floor(n/3)} binomial(n2*k, k)*(1)^k*2^(n3*k).  Paul Barry, Oct 20 2004
a(n+1) = Sum(binomial(nr, r)), r = 1, 2, ... which is the case t = 2 and k = 2 in the general case of tstrings and k blocks: a(n+1, k, t) = Sum(binomial(nr*(t1), r)*S2(nr*(t1)1, k1)), r = 1, 2, ...  Augustine O. Munagi, Apr 11 2005
a(n) = Sum_{k = 0..n2} k*Fibonacci(n  k  3).  Ross La Haye, May 31 2006
a(n) = term (3, 2) in the 3 X 3 matrix [1, 1, 0; 1, 0, 0; 1, 0, 1]^(n1).  Alois P. Heinz, Jul 24 2008
For n >= 4, a(n) = ceiling(phi*a(n1)), where phi is the golden ratio.  Vladimir Shevelev, Jul 04 2010
Closedform 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; closedform with two leading 0's 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, Jul 10 2011
G.f.: Q(0)*x^2/2, where Q(k) = 1 + 1/(1  x*(4*k + 2  x^2)/( x*(4*k + 4  x^2) + 1/Q(k+1) )); (continued fraction).  Sergei N. Gladkovskii, Aug 30 2013
E.g.f.: 1  exp(x) + 2*exp(x/2)*sinh(sqrt(5)*x/2)/sqrt(5).  Ilya Gutkovskiy, Jun 15 2016
a(n) = Sum_{i=0..n2} Fibonacci(i).  Giorgi Dalakishvili (mcnamara_gio(AT)yahoo.com), Apr 02 2005 [corrected by Doug Bell, Jun 01 2017]
a(n+2) = Sum_{j = 0..floor(n/2)} Sum_{k = 0..j} binomial(n  2*j, k+1)*binomial(j, k).  Tony Foster III, Sep 08 2017
a(4*n) = Fibonacci(2*n+1)*Lucas(2*n1) = A081006(n);
a(4*n+1) = Fibonacci(2*n)*Lucas(2*n+1) = A081007(n);
a(4*n+2) = Fibonacci(2*n)*Lucas(2*n+2) = A081008(n);
a(4*n+3) = Fibonacci(2*n+2)*Lucas(2*n+1) = A081009(n). (End)
G.f.: x^3/((1  x  x^2)*(1  x)) = Sum_{n >= 0} (1)^n * x^(n+3) *( Product_{k = 1..n} (k  x)/Product_{k = 1..n+2} (1  k*x) ) (a telescoping series).  Peter Bala, May 08 2024


MAPLE

a:= n> (Matrix([[1, 1, 0], [1, 0, 0], [1, 0, 1]])^(n1))[3, 2]; seq(a(n), n=1..50); # Alois P. Heinz, Jul 24 2008


MATHEMATICA

Fibonacci[Range[40]]  1 (* or *) LinearRecurrence[{2, 0, 1}, {0, 0, 1}, 40] (* Harvey P. Dale, Aug 23 2013 *)
Join[{0}, Accumulate[Fibonacci[Range[0, 39]]]] (* Alonso del Arte, Oct 22 2017, based on Giorgi Dalakishvili's formula *)


PROG

(PARI) {a(n) = if( n<1, 0, fibonacci(n)1)};
(Haskell)
a000071 n = a000071_list !! n
a000071_list = map (subtract 1) $ tail a000045_list


CROSSREFS

Cf. A000045, A054761, A119282, A001654, A005968, A005969, A098531, A098532, A098533, A128697, A001611, A157725, A001911, A157726, A006327, A157727, A157728, A157729, A167616, A158950, A105488, A105489, A014417, A104326.
Antidiagonal sums of array A004070.
Righthand column 2 of triangle A011794.
a(n) = A101220(1, 1, n2), for n > 1.


KEYWORD



AUTHOR



EXTENSIONS



STATUS

approved



