|
| |
|
|
A001629
|
|
Fibonacci numbers convolved with themselves.
(Formerly M1377 N0537)
|
|
44
| |
|
|
0, 0, 1, 2, 5, 10, 20, 38, 71, 130, 235, 420, 744, 1308, 2285, 3970, 6865, 11822, 20284, 34690, 59155, 100610, 170711, 289032, 488400, 823800, 1387225, 2332418, 3916061, 6566290, 10996580, 18394910, 30737759, 51310978, 85573315
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
COMMENTS
| 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 (deutsch(AT)duke.poly.edu), Dec 10 2003
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
Number of 3412-avoiding involutions containing exactly one subsequence of type 321.
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
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
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
a(n) = 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 (tauraso(AT)mat.uniroma2.it), May 02 2005; Graeme McRae (g_m(AT)mcraefamily.com), Jun 02 2006
a(n+1)=((-I)^(n-1))*diff(S(n,x),x)|_{x=I}, n>=1. First derivative of Chebyshev S-polynomials evaluated at x=I (imaginary unit) multiplied by (-I)^(n-1). See A049310 for the S-polynomials. W. Lang, Apr 04 2007.
For n>=4, a(n)=number of weak compositions of n-3 in which exactly one part is 0 and all other parts are either 1 or 2. [From Milan R. Janjic (agnus(AT)blic.net), Jun 28 2010]
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). [From John M. Campbell, Jun 23 2011]
|
|
|
REFERENCES
| V. E. Hoggatt, Jr. and M. Bicknell-Johnson, Fibonacci convolution sequences, Fib. Quart., 15 (1977), 117-122.
S. Klavzar, Structure of Fibonacci cubes: a survey; Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia; Preprint series Vol. 49 (2011), 1150 ISSN 2232-2094; http://www.imfm.si/preprinti/PDF/01150.pdf. (See Section 4.)
Thomas Koshy, Fibonacci and Lucas Numbers with Applications, Chapter 15, page 187, "Hosoya's Triangle"
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.
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).
S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989, p. 183, Nr.(98).
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..500
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
E. S. Egge, Restricted 3412-Avoiding Involutions, p. 16.
S. Klavzar, On median nature and enumerative properties of Fibonacci-like cubes, Disc. Math. 299 (2005), 145-153. [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Nov 05 2008]
T. Mansour, Generalization of some identities involving the Fibonacci numbers
P. Moree, Convoluted convolved Fibonacci numbers
Pieter Moree, Convoluted Convolved Fibonacci Numbers, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.2.
S. 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.
S. 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
|
|
|
FORMULA
| G.f.: x^2/(1-x-x^2)^2.
a(n)=2*a(n-1)+a(n-2)-2*a(n-3)-a(n-4), n>3.
a(n)=sum(F(k)*F(n-k)), k=0..n where F(k)=A000045(k) (the Fibonacci sequence).
a(n+1) = sum(A007895(i), 0 <= i <= F(n)), where F = A000045, the Fibonacci sequence - Claude Lenormand (claude.lenormand(AT)free.fr), Feb 04 2001
a(n)=sum((k+1)*binomial(n-k-1, k+1), k=0..floor(n/2)-1). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 15 2001
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 (benoit7848c(AT)orange.fr), Jan 05 2003
a(n)=a(n-1)+A010049(n-1) for n>0. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 10 2003
a(n)=sum{k=0..floor((n-2)/2), (n-k-1)binomial(n-k-2, k)} - Paul Barry (pbarry(AT)wit.ie), Jan 25 2005
a(n)= ((n-1)*F(n)+2*n*F(n-1))/5, F(n)=A000045(n) (see Vajda reference)
F'(n, 1), the first derivative of the n-th Fibonacci polynomial evaluated at 1. - T. D. Noe (noe(AT)sspectra.com), Jan 18 2006
a(n)=a(n-1)+a(n-2)+F(n-1), where F=A000045, the Fibonacci sequence. - Graeme McRae (g_m(AT)mcraefamily.com), Jun 02 2006
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 (g_m(AT)mcraefamily.com), Jun 02 2006
a(n) = A055244(n-1) - F(n-2). Example: a(6) = 20 = A055244(5) - F(3) = (23 - 3). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jul 27 2007
a(n) = sum of (n-1)-th row terms of triangle A134510; e.g., a(6) = 20 = (8 + 5 + 5 + 1 + 1). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 28 2007
Starting (1, 2, 5, 10, 20, 38,...), = row sums of triangle A134836. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 12 2007
a(n) = term (1,3) in the 4x4 matrix [2,1,0,0; 1,0,1,0; -2,0,0,1; -1,0,0,0]^n. [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Aug 01 2008]
|
|
|
MAPLE
| A001629:=1/(z**2+z-1)**2; [Conjectured by S. Plouffe in his 1992 dissertation.]
(Maple) 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..34); [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Aug 01 2008]
|
|
|
MATHEMATICA
| Table[Sum[Binomial[n - i, i]*i, {i, 0, n}], {n, 0, 34}] [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), May 04 2009]
Table[Abs[(1 - (1/2 - I/2) (1 + (-1)^(n + 1)))* Coefficient[ CharacteristicPolynomial[ Array[KroneckerDelta[#1, #2]*I + KroneckerDelta[#1 + 1, #2] + KroneckerDelta[#1 - 1, #2] &, {n - 1, n - 1}], x], x]], {n, 2, 50}] (* From John M. Campbell, Jun 23 2011 *)
|
|
|
PROG
| (Haskell)
a001629 n = sum $ zipWith (*) nFibs $ reverse nFibs where
nFibs = take n a000045_list
-- Reinhard Zumkeller, Oct 16 2011
|
|
|
CROSSREFS
| a(n)= A037027(n-1, 1), n >= 1, (Fibonacci convolution triangle). Cf. A000045, A001628.
Row sums of triangle A058071.
Cf. A010049.
First differences of A006478.
Cf. A055244.
Cf. A134510.
Cf. A134836.
Sequence in context: A000712 A032442 A102688 * A159230 A181366 A068034
Adjacent sequences: A001626 A001627 A001628 * A001630 A001631 A001632
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
