|
%I M1377 N0537 #361 Mar 22 2024 11:06:10
%S 0,0,1,2,5,10,20,38,71,130,235,420,744,1308,2285,3970,6865,11822,
%T 20284,34690,59155,100610,170711,289032,488400,823800,1387225,2332418,
%U 3916061,6566290,10996580,18394910,30737759,51310978,85573315,142587180,237387960,394905492
%N Self-convolution of Fibonacci numbers.
%C Number of elements in all subsets of {1,2,...,n-1} with no consecutive integers. Example: a(5)=10 because the subsets of {1,2,3,4} that have no consecutive elements, i.e., {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}, the total number of elements is 10. - _Emeric Deutsch_, Dec 10 2003
%C If g is either of the real solutions to x^2-x-1=0, g'=1-g is the other one and phi is any 2 X 2-matricial solution to the same equation, not of the form gI or g'I, then Sum'_{i+j=n-1} g^i phi^j = F_n + (A001629(n) - A001629(n-1)g')*(phi-g'I), where i,j >= 0, F_n is the n-th Fibonacci number and I is the 2 X 2 identity matrix... - Michele Dondi (blazar(AT)lcm.mi.infn.it), Apr 06 2004
%C Number of 3412-avoiding involutions containing exactly one subsequence of type 321.
%C Number of binary sequences of length n with exactly one pair of consecutive 1's. - George J. Schaeffer (gschaeff(AT)andrew.cmu.edu), Sep 02 2004
%C For this sequence the n-th term is given by (nF(n+1)-F(n)+nF(n-1))/5 where F(n) is the n-th Fibonacci number. - Mrs. J. P. Shiwalkar and M. N. Deshpande (dpratap_ngp(AT)sancharnet.in), Apr 20 2005
%C If an unbiased coin is tossed n times then there are 2^n possible strings of H and T. Out of these, number of strings with exactly one 'HH' is given by a(n) where a(n) denotes n-th term of this sequence. - Mrs. J. P. Shiwalkar and M. N. Deshpande (dpratap_ngp(AT)sancharnet.in), May 04 2005
%C a(n) is half the number of horizontal dominoes in all domino tilings of a horizontally aligned 2 X n rectangle; a(n+1) = the number of vertical dominoes in all domino tilings of a horizontally aligned 2 X n rectangle; thus 2*a(n)+a(n+1)=n*F(n+1) = the number of dominoes in all domino tilings of a 2 X n rectangle, where F=A000045, the Fibonacci sequence. - _Roberto Tauraso_, May 02 2005; _Graeme McRae_, Jun 02 2006
%C a(n+1) = (-i)^(n-1)*(d/dx)S(n,x)|_{x=i}, where i is the imaginary unit, n >= 1. First derivative of Chebyshev S-polynomials evaluated at x=i multiplied by (-i)^(n-1). See A049310 for the S-polynomials. - _Wolfdieter Lang_, Apr 04 2007
%C For n >= 4, a(n) is the number of weak compositions of n-2 in which exactly one part is 0 and all other parts are either 1 or 2. - _Milan Janjic_, Jun 28 2010
%C For n greater than 1, a(n) equals the absolute value of (1 - (1/2 - i/2)*(1 + (-1)^(n + 1))) times the x-coefficient of the characteristic polynomial of the (n-1) X (n-1) tridiagonal matrix with i's along the main diagonal (i is the imaginary unit), 1's along the superdiagonal and the subdiagonal and 0's everywhere else (see Mathematica code below). - _John M. Campbell_, Jun 23 2011
%C For n > 0: a(n) = Sum_{k=1..n-1} (A039913(n-1,k)) / 2. - _Reinhard Zumkeller_, Oct 07 2012
%C The right-hand side of a binomial-coefficient identity [Gauthier]. - _N. J. A. Sloane_, Apr 09 2013
%C a(n) is the number of edges in the Fibonacci cube Gamma(n-1) (see the Klavzar 2005 reference, p. 149). Example: a(3)=2; indeed, the Fibonacci cube Gamma(2) is the path P(3) having 2 edges. - _Emeric Deutsch_, Aug 10 2014
%C a(n) is the number of c(i)'s, including repetitions, in p(n), where p(n)/q(n) is the n-th convergent p(n)/q(n) of the formal infinite continued fraction [c(0), c(1), ...]; e.g., the number of c(i)'s in p(3) = c(0)*c(1)*c(2)*c(3) + c(0)*c(1) + c(0)*c(3) + c(2)*c(3) + 1 is a(5) = 10. - _Clark Kimberling_, Dec 23 2015
%C Also the number of maximal and maximum cliques in the (n-1)-Fibonacci cube graph. - _Eric W. Weisstein_, Sep 07 2017
%C a(n+1) is the total number of fixed points in all permutations p on 1, 2, ..., n such that |k-p(k)| <= 1 for 1 <= k <= n. - _Katharine Ahrens_, Sep 03 2019
%C From _Steven Finch_, Mar 22 2020: (Start)
%C a(n+1) is the total binary weight (cf. A000120) of all A000045(n+2) binary sequences of length n not containing any adjacent 1's.
%C The only three 2-bitstrings without adjacent 1's are 00, 01 and 10. The bitsums of these are 0, 1 and 1. Adding these give a(3)=2.
%C The only five 3-bitstrings without adjacent 1's are 000, 001, 010, 100 and 101. The bitsums of these are 0, 1, 1, 1 and 2. Adding these give a(4)=5.
%C The only eight 4-bitstrings without adjacent 1's are 0000, 0001, 0010, 0100, 1000, 0101, 1010 and 1001. The bitsums of these are 0, 1, 1, 1, 1, 2, 2, and 2. Adding these give a(5)=10. (End)
%D Donald E. Knuth, Fundamental Algorithms, Addison-Wesley, 1968, p. 83, Eq. 1.2.8--(17). - _Don Knuth_, Feb 26 2019
%D Thomas Koshy, Fibonacci and Lucas Numbers with Applications, Chapter 15, page 187, "Hosoya's Triangle", and p. 375, eq. (32.13).
%D J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989, p. 183, Nr.(98).
%H T. D. Noe, <a href="/A001629/b001629.txt">Table of n, a(n) for n = 0..500</a>
%H Marco Abrate, Stefano Barbero, Umberto Cerruti and Nadir Murru, <a href="http://dx.doi.org/10.1016/j.disc.2014.06.026">Colored compositions, Invert operator and elegant compositions with the "black tie"</a>, Discrete Math. 335 (2014), 1--7. MR3248794.
%H Katharine A. Ahrens, <a href="https://www.lib.ncsu.edu/resolver/1840.20/37364">Combinatorial Applications of the k-Fibonacci Numbers: A Cryptographically Motivated Analysis</a>, Ph. D. thesis, North Carolina State University (2020).
%H Carlos Alirio Rico Acevedo and Ana Paula Chaves, <a href="https://arxiv.org/abs/1903.07490">Double-Recurrence Fibonacci Numbers and Generalizations</a>, arXiv:1903.07490 [math.NT], 2019.
%H Marcella Anselmo, Giuseppa Castiglione, Manuela Flores, Dora Giammarresi, Maria Madonia, and Sabrina Mantaci, <a href="https://arxiv.org/abs/2303.09898">Hypercubes and Isometric Words based on Swap and Mismatch Distance</a>, arXiv:2303.09898 [math.CO], 2023.
%H Ali Reza Ashrafi, Jernej Azarija, Khadijeh Fathalikhani, Sandi Klavžar and Marko Petkovšek, <a href="http://arxiv.org/abs/1407.4962">Vertex and edge orbits of Fibonacci and Lucas cubes</a>, arXiv:1407.4962 [math.CO], 2014. See Table 2.
%H A. R. Ashrafi, J. Azarija, K. Fathalikhani, S. Klavzar, et al., <a href="http://www.fmf.uni-lj.si/~klavzar/preprints/Fib-Luc-orbits-August-11-2014.pdf">Orbits of Fibonacci and Lucas cubes, dihedral transformations, and asymmetric strings</a>, 2014.
%H Jean-Luc Baril, Sergey Kirgizov and Vincent Vajnovszki, <a href="https://arxiv.org/abs/2010.09505">Gray codes for Fibonacci q-decreasing words</a>, arXiv:2010.09505 [cs.DM], 2020.
%H D. Birmajer, J. Gil and M. Weiner, <a href="http://arxiv.org/abs/1405.7727">Linear recurrence sequences and their convolutions via Bell polynomials</a>, arXiv:1405.7727 [math.CO], 2014.
%H D. Birmajer, J. B. Gil and M. D. Weiner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Gil/gil3.html">Linear Recurrence Sequences and Their Convolutions via Bell Polynomials</a>, Journal of Integer Sequences, 18 (2015), #15.1.2.
%H Matthew Blair, Rigoberto Flórez and Antara Mukherjee, <a href="https://arxiv.org/abs/1808.05278">Matrices in the Hosoya triangle</a>, arXiv:1808.05278 [math.CO], 2018.
%H Matthew Blair, Rigoberto Flórez and Antara Mukherjee, <a href="https://arxiv.org/abs/2203.13205">Honeycombs in the Pascal triangle and beyond</a>, arXiv:2203.13205 [math.HO], 2022. See p. 5.
%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H G. Castiglione, A. Restivo and M. Sciortino, <a href="https://doi.org/10.1016/j.tcs.2009.07.018">Circular Sturmian words and Hopcroft’s algorithm</a>, Theor. Comput. Sci. 410, No. 43, 4372-4381 (2009)
%H Charles H. Conley and Valentin Ovsienko, <a href="https://arxiv.org/abs/2209.10426">Shadows of rationals and irrationals: supersymmetric continued fractions and the super modular group</a>, arXiv:2209.10426 [math-ph], 2022.
%H É. Czabarka, R. Flórez and L. Junes, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Florez/florez12.html">A Discrete Convolution on the Generalized Hosoya Triangle</a>, Journal of Integer Sequences, 18 (2015), #15.1.6.
%H E. S. Egge, <a href="https://arxiv.org/abs/math/0307050">Restricted 3412-Avoiding Involutions</a>, p. 16, arXiv:math/0307050 [math.CO], 2003.
%H Sergio Falcon, <a href="https://doi.org/10.7546/nntdm.2020.26.3.96-106">Half self-convolution of the k-Fibonacci sequence</a>, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 3, 96-106.
%H Luca Ferrari and Emanuele Munarini, <a href="http://arxiv.org/abs/1203.6792">Enumeration of edges in some lattices of paths</a>, arXiv:1203.6792 [math.CO], 2012.
%H Steven Finch, <a href="https://arxiv.org/abs/2003.09458">Cantor-solus and Cantor-multus distributions</a>, arXiv:2003.09458 [math.CO], 2020.
%H Rigoberto Flórez, Robinson Higuita and Alexander Ramírez, <a href="https://arxiv.org/abs/1808.01264">The resultant, the discriminant, and the derivative of generalized Fibonacci polynomials</a>, arXiv:1808.01264 [math.NT], 2018.
%H N. Gauthier (Proposer), <a href="http://www.fq.math.ca/Problems/November2012advanced.pdf">Problem H-703</a>, Fib. Quart., 50 (2012), 379-381.
%H Ricardo Gómez Aíza, <a href="https://arxiv.org/abs/2402.16111">Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis</a>, arXiv:2402.16111 [math.CO], 2024. See p. 23.
%H Martin Griffiths, <a href="http://www.fq.math.ca/Papers1/48-2/Griffiths.pdf">Digit Proportions in Zeckendorf Representations</a>, Fibonacci Quart. 48 (2010), no. 2, 168-174.
%H V. E. Hoggatt, Jr. and M. Bicknell-Johnson, <a href="http://www.fq.math.ca/Scanned/15-2/hoggatt1.pdf">Fibonacci convolution sequences</a>, Fib. Quart., 15 (1977), 117-122.
%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Janjic/janjic33.html">Hessenberg Matrices and Integer Sequences </a>, J. Int. Seq. 13 (2010) # 10.7.8, section 3.
%H S. Klavzar, <a href="http://dx.doi.org/10.1016/j.disc.2004.02.023">On median nature and enumerative properties of Fibonacci-like cubes</a>, Disc. Math. 299 (2005), 145-153.
%H S. Klavzar, <a href="http://www.imfm.si/preprinti/PDF/01150.pdf">Structure of Fibonacci cubes: a survey</a>, Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia; Preprint series Vol. 49 (2011), 1150 ISSN 2232-2094. (See Section 4.)
%H T. Mansour, <a href="https://arxiv.org/abs/math/0301157">Generalization of some identities involving the Fibonacci numbers</a>, arXiv:math/0301157 [math.CO], 2003.
%H Pieter Moree, <a href="https://arxiv.org/abs/math/0311205">Convoluted convolved Fibonacci numbers</a>, arXiv:math/0311205 [math.CO], 2003.
%H Pieter Moree, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL7/Moree/moree12.htm">Convoluted Convolved Fibonacci Numbers</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.2.
%H László Németh, <a href="https://arxiv.org/abs/2403.12159">Walks on tiled boards</a>, arXiv:2403.12159 [math.CO], 2024. See p. 2.
%H Valentin Ovsienko, <a href="https://arxiv.org/abs/2111.02553">Shadow sequences of integers, from Fibonacci to Markov and back</a>, arXiv:2111.02553 [math.CO], 2021.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H Jeffrey B. Remmel and J. L. B. Tiefenbruck, <a href="https://ajc.maths.uq.edu.au/pdf/64/ajc_v64_p166.pdf">Q-analogues of convolutions of Fibonacci numbers</a>, Australasian Journal of Combinatorics, Volume 64(1) (2016), Pages 166-193.
%H J. Riordan, <a href="/A001820/a001820.pdf">Notes to N. J. A. Sloane, Jul. 1968</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EdgeCount.html">Edge Count</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FibonacciCubeGraph.html">Fibonacci Cube Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EdgeCount.html">Edge Count</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalClique.html">Maximal Clique</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximumClique.html">Maximum Clique</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2,-1).
%F G.f.: x^2/(1 - x - x^2)^2. - _Simon Plouffe_ in his 1992 dissertation
%F a(n) = A037027(n-1, 1), n >= 1 (Fibonacci convolution triangle).
%F a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4), n > 3.
%F a(n) = Sum_{k=0..n} A000045(k)*A000045(n-k).
%F a(n+1) = Sum_{i=0..F(n)} A007895(i), where F = A000045, the Fibonacci sequence. - Claude Lenormand (claude.lenormand(AT)free.fr), Feb 04 2001
%F a(n) = Sum_{k=0..floor(n/2)-1} (k+1)*binomial(n-k-1, k+1). - _Emeric Deutsch_, Nov 15 2001
%F a(n) = floor( (1/5)*(n - 1/sqrt(5))*phi^n + 1/2 ) where phi=(1+sqrt(5))/2 is the golden ratio. - _Benoit Cloitre_, Jan 05 2003
%F a(n) = a(n-1) + A010049(n-1) for n > 0. - _Emeric Deutsch_, Dec 10 2003
%F a(n) = Sum_{k=0..floor((n-2)/2)} (n-k-1)*binomial(n-k-2, k). - _Paul Barry_, Jan 25 2005
%F a(n) = ((n-1)*F(n) + 2*n*F(n-1))/5, F(n)=A000045(n) (see Vajda and Koshy reference).
%F F'(n, 1), the first derivative of the n-th Fibonacci polynomial evaluated at 1. - _T. D. Noe_, Jan 18 2006
%F a(n) = a(n-1) + a(n-2) + F(n-1), where F=A000045, the Fibonacci sequence. - _Graeme McRae_, Jun 02 2006
%F a(n) = (1/5)*(n-1/sqrt(5))*((1+sqrt(5))/2)^n + (1/5)*(n+1/sqrt(5))*((1-sqrt(5))/2)^n. - _Graeme McRae_, Jun 02 2006
%F a(n) = A055244(n-1) - F(n-2). Example: a(6) = 20 = A055244(5) - F(3) = (23 - 3). - _Gary W. Adamson_, Jul 27 2007
%F a(n) = term (1,3) in the 4 X 4 matrix [2,1,0,0; 1,0,1,0; -2,0,0,1; -1,0,0,0]^n. - _Alois P. Heinz_, Aug 01 2008
%F a(n) = A214178(n,1) for n > 0. - _Reinhard Zumkeller_, Jul 08 2012
%F a(n) = ((n+1)*F(n-1) + (n-1)*F(n+1))/5. - _Richard R. Forberg_, Aug 04 2014
%F (n-2)*a(n) - (n-1)*a(n-1) - n*a(n-2) = 0, n > 1. - _Michael D. Weiner_, Nov 18 2014
%F a(n) = Sum_{i=0..n-1} Sum_{j=0..i} F(j-1)*F(i-j), where F(n) = A000045 Fibonacci Numbers. - _Carlos A. Rico A._, Jul 14 2016
%F a(n) = (n*Lucas(n) - Fibonacci(n))/5, where Lucas = A000032, Fibonacci = A000045. - _Vladimir Reshetnikov_, Sep 27 2016
%F a(n) = (n-1)*hypergeom([1-n/2, (3-n)/2], [1-n], -4) for n >= 2. - _Peter Luschny_, Apr 10 2018
%F a(n) = -(-1)^n a(-n) for all n in Z. - _Michael Somos_, Jun 24 2018
%F E.g.f.: (1/50)*exp(-2*x/(1+sqrt(5)))*(2*sqrt(5)-5*(-1+sqrt(5))*x+exp(sqrt(5)*x)*(-2*sqrt(5)+5*(1+sqrt(5))*x)). - _Stefano Spezia_, Sep 03 2019
%e G.f. = x^2 + 2*x^3 + 5*x^4 + 10*x^5 + 20*x^6 + 38*x^7 + 71*x^8 + 130*x^9 + ... - _Michael Somos_, Jun 24 2018
%p a:= n-> (Matrix(4, (i,j)-> if (i=j-1) then 1 elif j=1 then [2, 1, -2, -1][i] else 0 fi)^n)[1,3]: seq(a(n), n=0..40); # _Alois P. Heinz_, Aug 01 2008
%p # Alternative:
%p A001629 := n -> `if`(n<2, 0, (n-1)*hypergeom([1-n/2, (3-n)/2], [1-n], -4)):
%p seq(simplify(A001629(n)), n=0..37); # _Peter Luschny_, Apr 10 2018
%t Table[Sum[Binomial[n-i, i] i, {i, 0, n}], {n, 0, 34}] (* _Geoffrey Critzer_, May 04 2009 *)
%t Table[Abs[(1 -(1/2 -I/2)(1 - (-1)^n))*Coefficient[CharacteristicPolynomial[ Array[KroneckerDelta[#1, #2] I + KroneckerDelta[#1 + 1, #2] + KroneckerDelta[#1 -1, #2] &, {n-1, n-1}], x], x]], {n,2,50}] (* _John M. Campbell_, Jun 23 2011 *)
%t LinearRecurrence[{2,1,-2,-1}, {0,0,1,2}, 40] (* _Harvey P. Dale_, Aug 26 2013 *)
%t CoefficientList[Series[x^2/(1-x-x^2)^2, {x, 0, 40}], x] (* _Vincenzo Librandi_, Nov 19 2014 *)
%t Table[(2nFibonacci[n-1] + (n-1)Fibonacci[n])/5, {n, 0, 40}] (* _Vladimir Reshetnikov_, May 08 2016 *)
%t Table[With[{fibs=Fibonacci[Range[n]]},ListConvolve[fibs,fibs]],{n,-1,40}]//Flatten (* _Harvey P. Dale_, Aug 19 2018 *)
%o (Haskell)
%o a001629 n = a001629_list !! (n-1)
%o a001629_list = f [] $ tail a000045_list where
%o f us (v:vs) = (sum $ zipWith (*) us a000045_list) : f (v:us) vs
%o -- _Reinhard Zumkeller_, Jan 18 2014, Oct 16 2011
%o (PARI) Vec(1/(1-x-x^2)^2+O(x^99)) \\ _Charles R Greathouse IV_, Feb 03 2014
%o (PARI) a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; -1,-2,1,2]^n)[2,4] \\ _Charles R Greathouse IV_, Jul 20 2016
%o (Magma) I:=[0,0,1,2]; [n le 4 select I[n] else 2*Self(n-1)+Self(n-2)-2*Self(n-3)-Self(n-4): n in [1..40]]; // _Vincenzo Librandi_, Nov 19 2014
%o (GAP) List([0..40],n->Sum([0..n],k->Fibonacci(k)*Fibonacci(n-k))); # _Muniru A Asiru_, Jun 24 2018
%o (SageMath)
%o def A001629(n): return (1/5)*(n*lucas_number2(n, 1, -1) - fibonacci(n))
%o [A001629(n) for n in (0..40)] # _G. C. Greubel_, Apr 06 2022
%Y Row sums of triangles A058071, A134510, A134836.
%Y First differences of A006478.
%Y Cf. A000032, A000045, A001628, A010049, A037027, A055244, A214178.
%K nonn,easy,nice
%O 0,4
%A _N. J. A. Sloane_
|
