OFFSET
0,2
COMMENTS
a(n-2) + 1 is the number of (3412,1243)-, (3412,2134)- and (3412,1324)-avoiding involutions in S_n, n>1. - Ralf Stephan, Jul 06 2003
The number of terms in all ordered partitions of (n+1) using only ones and twos. For example, a(3)=15 because there are 15 terms in 1+1+1+1;2+1+1;1+2+1;1+1+2;2+2 - Geoffrey Critzer, Apr 07 2008
a(n) is the number of n-matchings in the graph obtained by a zig-zag triangulation of a convex (2n+1)-gon. Example: a(2)=7 because in the triangulation of the convex pentagon ABCDEA with diagonals AD and AC we have 7 2-matchings: {AB,CD},{AB,DE},{BC,AD},{BC,DE},{BC,EA},{CD,EA} and {DE,AC}. - Emeric Deutsch, Dec 25 2004
Equals row sums of triangle A144154. - Gary W. Adamson, Sep 12 2008
Equals the number of 1's in Fibonacci Maximal notation for subsets of
(1, 2, 3, 5, 8, 13, ...) terms. For example (cf. A181630): 4, 5, and 6 are the 3 terms 101, 110, and 111 in Fibonacci Maximal. Total number of 1's for those terms = 7 = a(2). - Gary W. Adamson, Nov 02 2010
a(n) is half the number of strokes needed to draw all the domino tilings of a 2 X (n+2) rectangle. - Roberto Tauraso, Mar 15 2014
a(n) is the total number of 1's in all (n+1)-bit dual Zeckendorf representations of integers (A104326). For example, a(2) = 7 counts the 1's in 101, 110, 111. - Shenghui Yang, Feb 09 2025
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Marcella Anselmo, Giuseppa Castiglione, Manuela Flores, Dora Giammarresi, Maria Madonia, and Sabrina Mantaci, Hypercubes and Isometric Words based on Swap and Mismatch Distance, arXiv:2303.09898 [math.CO], 2023.
Marcella Anselmo, Giuseppa Castiglione, Manuela Flores, Dora Giammarresi, Maria Madonia, and Sabrina Mantaci, Generalized Fibonacci Cubes Based on Swap and Mismatch Distance, From Strings to Graphs, and Back Again, Open Acc. Ser. Informat. (OASIcs, 2025) Art. 5, 5:1-5:14. See p. 11.
Kassie Archer and Noel Bourne, Pattern avoidance in compositions and powers of permutations, arXiv:2505.05218 [math.CO], 2025. See p. 6.
Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.
Jean-Luc Baril and José L. Ramírez, Fibonacci and Catalan paths in a wall, 2023.
Camilo Barreto, Melissa Beerbower, Jennifer Elder, Pamela E. Harris, Lucy Martinez, José L. Ramírez, Samuel Ramírez, Grant Shirley, and Julio C. Vásquez, Lucky Cars in Fubini Rankings and Unit Fubini Rankings, arXiv:2510.27574 [math.CO], 2025. See p. 22.
Giuseppa Castiglione and Marinella Sciortino, Standard Sturmian words and automata minimization algorithms, Theoretical Computer Science, Volume 601, 11 October 2015, Pages 58-66 ("WORDS 2013").
Tomislav Došlic and Luka Podrug, Tilings of a Honeycomb Strip and Higher Order Fibonacci Numbers, arXiv:2203.11761 [math.CO], 2022.
Dmitry Efimov, Hafnian of two-parameter matrices, arXiv:2101.09722 [math.CO], 2021.
Eric S. Egge, Restricted 3412-Avoiding Involutions: Continued Fractions, Chebyshev Polynomials and Enumerations, arXiv:math/0307050 [math.CO], 2003. Sec. 8.
Neven Elezović, Asymptotic Expansions of Central Binomial Coefficients and Catalan Numbers, J. Int. Seq. 17 (2014) # 14.2.1.
Martin Griffiths, A Restricted Random Walk defined via a Fibonacci Process, Journal of Integer Sequences, Vol. 14 (2011), #11.5.4.
László Németh and László Szalay, Explicit solution of system of two higher-order recurrences, arXiv:2408.12196 [math.NT], 2024. See p. 10.
Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).
FORMULA
O.g.f.: (x+1)/(1-x-x^2)^2. - Len Smiley, Dec 11 2001
a(n) = (1/5)*((n+2)*F(n+4) + (n-1)*F(n+2)), with F(n)=A000045(n). - Ralf Stephan, Jul 06 2003
a(n) = Sum_{k=0..n+1} (n-k+1)*binomial(n-k+1, k). - Paul Barry, Nov 05 2005
Recurrence: a(n+2) = a(n+1) + a(n) + Fib(n+4), n >= 0. For n >= 2, a(n-2) = (-1)^n*((-2n+3)*Fib(-n) - (-n)*Fib(-n-1))/5 = (-1)^n*A010049(-n), the second-order Fibonacci numbers of negative index, where Fib(-n) = (-1)^(n+1)*Fib(n). - Peter Bala, Oct 24 2007
a(n) = (n+1)*F(n+2) - A001629(n+1) where F(n) is the n-th Fibonacci number. - Geoffrey Critzer, Apr 07 2008
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4), n >= 4. - L. Edson Jeffery, Mar 29 2013
E.g.f.: exp(x/2)*(5*(5 + 7*x)*cosh(sqrt(5)*x/2) + sqrt(5)*(11 + 15*x)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Dec 04 2023
MATHEMATICA
Table[Sum[Binomial[n - i, i]*(n - i), {i, 0, n}], {n, 1, 33}] (* Geoffrey Critzer, May 04 2009 *)
PROG
(SageMath)
def A023610():
a, b, c, d = 1, 3, 7, 15
while True:
yield a
a, b, c, d = b, c, d, 2*(d-b)+c-a
a = A023610(); [next(a) for i in range(33)] # Peter Luschny, Nov 20 2013
(Haskell)
a023610 n = a023610_list !! n
a023610_list = f [1] $ drop 3 a000045_list where
f us (v:vs) = (sum $ zipWith (*) us $ tail a000045_list) : f (v:us) vs
-- Reinhard Zumkeller, Jan 18 2014
(PARI) a(n)=(n+2)*fibonacci(n+4)/5+(n-1)*fibonacci(n+2)/5 \\ Charles R Greathouse IV, Jun 11 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
STATUS
approved