# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a006190
Showing 1-1 of 1
%I A006190 M2844 #322 Aug 22 2024 17:39:31
%S A006190 0,1,3,10,33,109,360,1189,3927,12970,42837,141481,467280,1543321,
%T A006190 5097243,16835050,55602393,183642229,606529080,2003229469,6616217487,
%U A006190 21851881930,72171863277,238367471761,787274278560,2600190307441
%N A006190 a(n) = 3*a(n-1) + a(n-2), with a(0)=0, a(1)=1.
%C A006190 Denominators of continued fraction convergents to (3+sqrt(13))/2. - _Benoit Cloitre_, Jun 14 2003
%C A006190 a(n) and A006497(n) occur in pairs: (a,b): (1,3), (3,11), (10,36), (33,119), (109,393), ... such that b^2 - 13a^2 = 4(-1)^n. - _Gary W. Adamson_, Jun 15 2003
%C A006190 Form the 4-node graph with matrix A = [1,1,1,1; 1,1,1,0; 1,1,0,1; 1,0,1,1]. Then this sequence counts the walks of length n from the vertex with degree 5 to one (any) of the other vertices. - _Paul Barry_, Oct 02 2004
%C A006190 a(n+1) is the binomial transform of A006138. - _Paul Barry_, May 21 2006
%C A006190 a(n+1) is the diagonal sum of the exponential Riordan array (exp(3x),x). - _Paul Barry_, Jun 03 2006
%C A006190 Number of paths in the right half-plane from (0,0) to the line x=n-1, consisting of steps U=(1,1), D=(1,-1), h=(1,0) and H=(2,0). Example: a(3)=10 because we have hh, H, UD, DU, hU, Uh, UU, hD, Dh and DD. - _Emeric Deutsch_, Sep 03 2007
%C A006190 Equals INVERT transform of A000129. Example: a(5) = 109 = (29, 12, 5, 2, 1) dot (1, 1, 3, 10, 33) = (29 + 12 + 15 + 20 + 33). - _Gary W. Adamson_, Aug 06 2010
%C A006190 For n >= 2, a(n) equals the permanent of the (n-1) X (n-1) tridiagonal matrix with 3's along the main diagonal, 1's along the superdiagonal and subdiagonal, and 0's everywhere else. - _John M. Campbell_, Jul 08 2011
%C A006190 These numbers could also be called "bronze Fibonacci numbers". Indeed, for n >= 1, F(n+1) = ceiling(phi*F(n)), if n is even and F(n+1) = floor(phi*F(n)), if n is odd, where phi is the golden ratio; analogously, for Pell numbers (A000129), or "silver Fibonacci numbers", P(n+1) = ceiling(delta*a(n)), if n is even and P(n+1) = floor(delta*a(n)), if n is odd, where delta = delta_S = 1 + sqrt(2) is the silver ratio. Here, for n >= 1, we have a(n+1) = ceiling(c*a(n)), if n is even and a(n+1) = floor(c*a(n)), if n is odd, where c = (3 + sqrt(13))/2 is the bronze ratio (cf. comment in A098316). - _Vladimir Shevelev_, Feb 23 2013
%C A006190 Let p(n,x) denote the Fibonacci polynomial, defined by p(1,x) = 1, p(2,x) = x, p(n,x) = x*p(n-1,x) + p(n-2,x). Let q(n,x) be the numerator polynomial of the rational function p(n, x + 1 + 1/x). Then q(n,1) = a(n). - _Clark Kimberling_, Nov 04 2013
%C A006190 The (1,1)-entry of the matrix A^n where A = [0,1,0; 1,2,1; 1,1,2]. - _David Neil McGrath_, Jul 18 2014
%C A006190 a(n+1) counts closed walks on K2, containing three loops on the other vertex. Equivalently the (1,1)-entry of A^(n+1) where the adjacency matrix of digraph is A = (0,1; 1,3). - _David Neil McGrath_, Oct 29 2014
%C A006190 For n >= 1, a(n) equals the number of words of length n-1 on alphabet {0,1,2,3} avoiding runs of zeros of odd lengths. - _Milan Janjic_, Jan 28 2015
%C A006190 With offset 1 is the INVERTi transform of A001076. - _Gary W. Adamson_, Jul 24 2015
%C A006190 Apart from the initial 0, this is the p-INVERT transform of (1,0,1,0,1,0,...) for p(S) = 1 - 3 S. See A291219. - _Clark Kimberling_, Sep 02 2017
%C A006190 From _Rogério Serôdio_, Mar 30 2018: (Start)
%C A006190 This is a divisibility sequence (i.e., if n|m then a(n)|a(m)).
%C A006190 gcd(a(n),a(n+k)) = a(gcd(n, k)) for all positive integers n and k. (End)
%C A006190 Numbers of straight-chain fatty acids involving oxo and/or hydroxy groups, if cis-/trans isomerism and stereoisomerism are neglected. - _Stefan Schuster_, Apr 04 2018
%C A006190 Number of 3-compositions of n restricted to odd parts (and allowed zeros); see Hopkins & Ouvry reference. - _Brian Hopkins_, Aug 17 2020
%C A006190 From _Michael A. Allen_, Jan 25 2023: (Start)
%C A006190 Also called the 3-metallonacci sequence; the g.f. 1/(1-k*x-x^2) gives the k-metallonacci sequence.
%C A006190 a(n+1) is the number of tilings of an n-board (a board with dimensions n X 1) using unit squares and dominoes (with dimensions 2 X 1) if there are 3 kinds of squares available. (End)
%C A006190 a(n) is the number of compositions of n when there are P(k) sorts of parts k, with k,n >= 1, P(k) = A000129(k) is the k-th Pell number (see example below). - _Enrique Navarrete_, Dec 15 2023
%D A006190 H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178.
%D A006190 A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 128.
%D A006190 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A006190 L.-N. Machaut, Query 3436, L'Intermédiaire des Mathématiciens, 16 (1909), 62-63. - _N. J. A. Sloane_, Mar 08 2022
%H A006190 G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from T. D. Noe)
%H A006190 H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178. (Annotated scanned copy)
%H A006190 Michael A. Allen and Kenneth Edwards, Fence tiling derived identities involving the metallonacci numbers squared or cubed, Fib. Q. 60:5 (2022) 5-17.
%H A006190 Dorin Andrica, Ovidiu Bagdasar, and George Cătălin Tųrcąs, On some new results for the generalised Lucas sequences, An. Şt. Univ. Ovidius Constanţa (Romania, 2021) Vol. 29, No. 1, 17-36.
%H A006190 Ayoub B. Ayoub, Fibonacci-like sequences and Pell equations, The College Mathematics Journal, Vol. 38 (2007), pp. 49-53.
%H A006190 D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 8.
%H A006190 Henrique F. da Cruz, Ilda Inácio, and Rogério Serôdio, Convertible subspaces that arise from different numberings of the vertices of a graph, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 473-486.
%H A006190 Colin Defant, Meeting Covered Elements in nu-Tamari Lattices, arXiv:2104.03890 [math.CO], 2021.
%H A006190 Sergio Falcon, On The Generating Functions of the Powers of the K-Fibonacci Numbers, Scholars Journal of Engineering and Technology (SJET), 2014; 2 (4C):669-675.
%H A006190 Sergio Falcon, The k-Fibonacci difference sequences, Chaos, Solitons & Fractals, Volume 87, June 2016, Pages 153-157.
%H A006190 M. C. Firengiz and A. Dil, Generalized Euler-Seidel method for second order recurrence relations, Notes on Number Theory and Discrete Mathematics, Vol. 20, 2014, No. 4, 21-32.
%H A006190 Juan B. Gil and Aaron Worley, Generalized metallic means, arXiv:1901.02619 [math.NT], 2019.
%H A006190 Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.
%H A006190 A. F. Horadam, Generating identities for generalized Fibonacci and Lucas triples, Fib. Quart., 15 (1977), 289-292.
%H A006190 Haruo Hosoya, What Can Mathematical Chemistry Contribute to the Development of Mathematics?, HYLE--International Journal for Philosophy of Chemistry, Vol. 19, No.1 (2013), pp. 87-105.
%H A006190 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 158
%H A006190 Milan Janjic, Hessenberg Matrices and Integer Sequences , J. Int. Seq. 13 (2010) # 10.7.8, section 3.
%H A006190 Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
%H A006190 Tanya Khovanova, Recursive Sequences
%H A006190 W. F. Klostermeyer, M. E. Mays, L. Soltes and G. Trapp, A Pascal rhombus, Fibonacci Quarterly, 35 (1976), 318-328.
%H A006190 Pablo Lam-Estrada, Myriam Rosalía Maldonado-Ramírez, José Luis López-Bonilla, and Fausto Jarquín-Zárate, The sequences of Fibonacci and Lucas for each real quadratic fields Q(Sqrt(d)), arXiv:1904.13002 [math.NT], 2019.
%H A006190 Prabha Sivaraman Nair and Rejikumar Karunakaran, On k-Fibonacci Brousseau Sums, J. Int. Seq. (2024) Art. No. 24.6.4. See p. 2.
%H A006190 Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A006190 Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
%H A006190 S. Schuster, M. Fichtner and S. Sasso, Use of Fibonacci numbers in lipidomics - Enumerating various classes of fatty acids, Sci. Rep., 7 (2017) 39821.
%H A006190 Kai Wang, On k-Fibonacci Sequences And Infinite Series List of Results and Examples, 2020.
%H A006190 Index entries for sequences related to Chebyshev polynomials.
%H A006190 Index entries for linear recurrences with constant coefficients, signature (3,1).
%F A006190 G.f.: x/(1 - 3*x - x^2).
%F A006190 From _Benoit Cloitre_, Jun 14 2003
%F A006190 a(3*n) = 2*A041019(5*n-1), a(3*n+1) = A041019(5*n), a(3*n+2) = A041019(5*n+3).
%F A006190 a(2*n) = 3*A004190(n-1); a(3*n) = 10*A041613(n-1) for n >= 1. (End)
%F A006190 From _Gary W. Adamson_, Jun 15 2003: (Start)
%F A006190 a(n-1) + a(n+1) = A006497(n).
%F A006190 A006497(n)^2 - 13*a(n)^2 = 4(-1)^n. (End)
%F A006190 a(n) = U(n-1, (3/2)i)(-i)^(n-1), i^2 = -1. - _Paul Barry_, Nov 19 2003
%F A006190 a(n) = Sum_{k=0..n-1} binomial(n-k-1,k)*3^(n-2*k-1). - _Paul Barry_, Oct 02 2004
%F A006190 a(n) = F(n, 3), the n-th Fibonacci polynomial evaluated at x=3.
%F A006190 Let M = {{0, 1}, {1, 3}}, v[1] = {0, 1}, v[n] = M.v[n - 1]; then a(n) = Abs[v[n][[1]]]. - _Roger L. Bagula_, May 29 2005 [Or a(n) = [M^(n+1)]_{1,1}. - _L. Edson Jeffery_, Aug 27 2013
%F A006190 From _Paul Barry_, May 21 2006: (Start)
%F A006190 a(n+1) = Sum_{k=0..n} Sum_{j=0..n-k} C(k,j)*C(n-j,k)*2^(k-j).
%F A006190 a(n) = Sum_{k=0..n} Sum_{j=0..n-k} C(k,j)*C(n-j,k)*2^(n-j-k).
%F A006190 a(n+1) = Sum_{k=0..floor(n/2)} C(n-k,k)*3^(n-2*k).
%F A006190 a(n) = Sum_{k=0..n} C(k,n-k)*3^(2*k-n). (End)
%F A006190 E.g.f.: exp(3*x/2)*sinh(sqrt(13)*x/2)/(sqrt(13)/2). - _Paul Barry_, Jun 03 2006
%F A006190 a(n) = (ap^n - am^n)/(ap - am), with ap = (3 + sqrt(13))/2, am = (3 - sqrt(13))/2.
%F A006190 Let C = (3 + sqrt(13))/2 = exp arcsinh(3/2) = 3.3027756377... Then C^n, n > 0 = a(n)*(1/C) + a(n+1). Let X = the 2 X 2 matrix [0, 1; 1, 3]. Then X^n = [a(n-1), a(n); a(n), a(n+1)]. - _Gary W. Adamson_, Dec 21 2007
%F A006190 1/3 = 3/(1*10) + 3/(3*33) + 3/(10*109) + 3/(33*360) + 3/(109*1189) + ... . - _Gary W. Adamson_, Mar 16 2008
%F A006190 a(n) = ((3 + sqrt(13))^n - (3 - sqrt(13))^n)/(2^n*sqrt(13)). - Al Hakanson (hawkuu(AT)gmail.com), Jan 12 2009
%F A006190 a(p) == 13^((p-1)/2) mod p, for odd primes p. - _Gary W. Adamson_, Feb 22 2009
%F A006190 From _Johannes W. Meijer_, Jun 12 2010: (Start)
%F A006190 Limit_{k->oo} a(n+k)/a(k) = (A006497(n) + a(n)*sqrt(13))/2.
%F A006190 Limit_{n->oo} A006497(n)/a(n) = sqrt(13). (End)
%F A006190 Sum_{k>=1} (-1)^(k-1)/(a(k)*a(k+1)) = (sqrt(13)-3)/2. - _Vladimir Shevelev_, Feb 23 2013
%F A006190 From _Vladimir Shevelev_, Feb 24 2013: (Start)
%F A006190 (1) Expression a(n+1) via a(n): a(n+1) = (3*a(n) + sqrt(13*a^2(n) + 4*(-1)^n)/2;
%F A006190 (2) a^2(n+1) - a(n)*a(n+2) = (-1)^n;
%F A006190 (3) Sum_{k=1..n} (-1)^(k-1)/(a(k)*a(k+1)) = a(n)/a(n+1);
%F A006190 (4) a(n)/a(n+1) = (sqrt(13)-3)/2 + r(n), where |r(n)| < 1/(a(n+1)*a(n+2)). (End)
%F A006190 a(n) = sqrt(13*(A006497(n))^2 + (-1)^(n-1)*52)/13. - _Vladimir Shevelev_, Mar 13 2013
%F A006190 Sum_{n >= 1} 1/( a(2*n) + 1/a(2*n) ) = 1/3; Sum_{n >= 1} 1/( a(2*n + 1) - 1/a(2*n + 1) ) = 1/9. - _Peter Bala_, Mar 26 2015
%F A006190 From _Rogério Serôdio_, Mar 30 2018: (Start)
%F A006190 Some properties:
%F A006190 (1) a(n)*a(n+1) = 3*Sum_{k=1..n} a(k)^2;
%F A006190 (2) a(n)^2 + a(n+1)^2 = a(2*n+1);
%F A006190 (3) a(n)^2 - a(n-2)^2 = 3*a(n-1)*(a(n) + a(n-2));
%F A006190 (4) a(m*(p+1)) = a(m*p)*a(m+1) + a(m*p-1)*a(m);
%F A006190 (5) a(n-k)*a(n+k) = a(n)^2 + (-1)^(n+k+1)*a(k)^2;
%F A006190 (6) a(2*n) = a(n)*(3*a(n) + 2*a(n-1));
%F A006190 (7) 3*Sum_{k=2..n+1} a(k)*a(k-1) is equal to a(n+1)^2 if n odd, and is equal to a(n+1)^2 - 1 if n is even;
%F A006190 (8) a(n) - a(n-2*k+1) = alpha(k)*a(n-2*k+1) + a(n-4*k+2), where alpha(k) = (ap^(2*k-1) + am^(2*k-1), with ap = (3 + sqrt(13))/2, am = (3 - sqrt(13))/2;
%F A006190 (9) 131|Sum_{k=n..n+9} a(k), for all positive n. (End)
%F A006190 From _Kai Wang_, Feb 10 2020: (Start)
%F A006190 a(n)^2 - a(n+r)*a(n-r) = (-1)^(n-r)*a(r)^2 - Catalan's identity.
%F A006190 arctan(1/a(2n)) - arctan(1/a(2n+2)) = arctan(a(2)/a(2n+1)).
%F A006190 arctan(1/a(2n)) = Sum_{m>=n} arctan(a(2)/a(2m+1)).
%F A006190 The same formula holds for Fibonacci numbers and Pell numbers. (End)
%F A006190 a(n+2) = 3^(n+1) + Sum_{k=0..n} a(k)*3^(n-k). - _Greg Dresden_ and Gavron Campbell, Feb 22 2022
%F A006190 G.f. = 1/(1-Sum_{k>=1} P(k)*x^k), P(k)=A000129(k) (with a(0)=1). - _Enrique Navarrete_, Dec 17 2023
%F A006190 G.f.: x/(1 - 3*x - x^2) = Sum_{n >= 0} x^(n+1) *( Product_{k = 1..n} (m*k + 3 - m + x)/(1 + m*k*x) ) for arbitrary m (a telescoping series). - _Peter Bala_, May 08 2024
%e A006190 From _Enrique Navarrete_, Dec 15 2023: (Start)
%e A006190 From the comment on compositions with Pell number of parts, A000129(k), there are A000129(1)=1 type of 1, A000129(2)=2 types of 2, A000129(3)=5 types of 3, A000129(4)=12 types of 4, A000129(5)=29 types of 5 and A000129(6)=70 types of 6.
%e A006190 The following table gives the number of compositions of n=6:
%e A006190 Composition, number of such compositions, number of compositions of this type:
%e A006190 6, 1, 70;
%e A006190 5+1, 2, 58;
%e A006190 4+2, 2, 48;
%e A006190 3+3, 1, 25;
%e A006190 4+1+1, 3, 36;
%e A006190 3+2+1, 6, 60;
%e A006190 2+2+2, 1, 8;
%e A006190 3+1+1+1, 4, 20;
%e A006190 2+2+1+1, 6, 24;
%e A006190 2+1+1+1+1, 5, 10;
%e A006190 1+1+1+1+1+1, 1, 1;
%e A006190 for a total of a(6)=360 compositions of n=6. (End).
%p A006190 a[0]:=0: a[1]:=1: for n from 2 to 35 do a[n]:= 3*a[n-1]+a[n-2] end do: seq(a[n],n=0..30); # _Emeric Deutsch_, Sep 03 2007
%p A006190 A006190:=-1/(-1+3*z+z**2); # _Simon Plouffe_ in his 1992 dissertation, without the leading 0
%p A006190 seq(combinat[fibonacci](n,3),n=0..30); # _R. J. Mathar_, Dec 07 2011
%t A006190 a[n_] := (MatrixPower[{{1, 3}, {1, 2}}, n].{{1}, {1}})[[2, 1]]; Table[ a[n], {n, -1, 24}] (* _Robert G. Wilson v_, Jan 13 2005 *)
%t A006190 LinearRecurrence[{3,1},{0,1},30] (* or *) CoefficientList[Series[x/ (1-3x-x^2), {x,0,30}], x] (* _Harvey P. Dale_, Apr 20 2011 *)
%t A006190 Table[If[n==0, a1=1; a0=0, a2=a1; a1=a0; a0=3*a1+a2], {n, 0, 30}] (* _Jean-François Alcover_, Apr 30 2013 *)
%t A006190 Table[Fibonacci[n, 3], {n, 0, 30}] (* _Vladimir Reshetnikov_, May 08 2016 *)
%o A006190 (PARI) a(n)=if(n<1,0,contfracpnqn(vector(n,i,2+(i>1)))[2,1])
%o A006190 (PARI) a(n)=([1,3;1,2]^n)[2,1] \\ _Charles R Greathouse IV_, Mar 06 2014
%o A006190 (Sage) [lucas_number1(n,3,-1) for n in range(0, 30)] # _Zerinvary Lajos_, Apr 22 2009
%o A006190 (Magma)[ n eq 1 select 0 else n eq 2 select 1 else 3*Self(n-1)+Self(n-2): n in [1..30] ]; // _Vincenzo Librandi_, Aug 19 2011
%o A006190 (Haskell)
%o A006190 a006190 n = a006190_list !! n
%o A006190 a006190_list = 0 : 1 : zipWith (+) (map (* 3) $ tail a006190_list) a006190_list
%o A006190 -- _Reinhard Zumkeller_, Feb 19 2011
%o A006190 (PARI) concat([0],Vec(x/(1-3*x-x^2)+O(x^30))) \\ _Joerg Arndt_, Apr 30 2013
%o A006190 (GAP) a:=[0,1];; for n in [3..30] do a[n]:=3*a[n-1]+a[n-2]; od; a; # _Muniru A Asiru_, Mar 31 2018
%Y A006190 Row sums of Pascal's rhombus (A059317). Also row sums of triangle A054456(n, m).
%Y A006190 Sequences with g.f. 1/(1-k*x-x^2) or x/(1-k*x-x^2): A000045 (k=1), A000129 (k=2), this sequence (k=3), A001076 (k=4), A052918 (k=5), A005668 (k=6), A054413 (k=7), A041025 (k=8), A099371 (k=9), A041041 (k=10), A049666 (k=11), A041061 (k=12), A140455 (k=13), A041085 (k=14), A154597 (k=15), A041113 (k=16), A178765 (k=17), A041145 (k=18), A243399 (k=19), A041181 (k=20).
%Y A006190 Cf. A006497, A052906, A175182 (Pisano periods), A201001 (prime subsequence), A092936 (squares).
%Y A006190 Cf. A243399.
%K A006190 nonn,easy,nice
%O A006190 0,3
%A A006190 _N. J. A. Sloane_
%E A006190 Second formula corrected by _Johannes W. Meijer_, Jun 02 2010
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE