|
%I M3314 #274 Jan 16 2024 05:28:33
%S 1,1,4,7,19,40,97,217,508,1159,2683,6160,14209,32689,75316,173383,
%T 399331,919480,2117473,4875913,11228332,25856071,59541067,137109280,
%U 315732481,727060321,1674257764,3855438727,8878212019,20444528200
%N a(n) = a(n-1) + 3*a(n-2) for n > 1, a(0) = a(1) = 1.
%C Counts walks of length n at the vertex of degree five in the graph with adjacency matrix A = [1,1,1,1;1,0,0,0;1,0,0,0;1,0,0,0]. - _Paul Barry_, Oct 02 2004
%C Form the graph with matrix A = [0,1,1,1;1,1,0,0;1,0,1,0;1,0,0,1]. The sequence 0,1,1,4,... counts walks of length n between the vertex without loop and another vertex. - _Paul Barry_, Oct 02 2004
%C Length-n words with letters {0,1,2,3} where no two consecutive letters are nonzero, see fxtbook link below. - _Joerg Arndt_, Apr 08 2011
%C Hankel transform is the sequence [1,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,...]. - _Philippe Deléham_, Nov 10 2007
%C Let M = [1, sqrt(3); sqrt(3), 0] be a 2 X 2 matrix. Then A006130(n)={[M^n]_(1,1)}. Note that A006130-A052533 = A006130 (shifted to the right one place, with first term = 0). - _L. Edson Jeffery_, Nov 25 2011 [Any matrix M = [1, y; 3/y, 0], with y not 0, will do it. - _Wolfdieter Lang_, Feb 18 2018]
%C The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=2, 4*a(n-2) equals the number of 4-colored compositions of n with all parts >=2, such that no adjacent parts have the same color. - _Milan Janjic_, Nov 26 2011
%C a(n) is the number of compositions (ordered partitions) of n into parts 1 and 2 where there are three sorts of part 2 (see the g.f.). - _Joerg Arndt_, Jan 16 2024
%C Number of pairs of rabbits when there are 3 pairs per litter and offspring reach parenthood after 2 gestation periods. - _Robert FERREOL_, Oct 28 2018
%C Numerators of stationary probabilities sequence for number of customers in steady state of M2/M/1 queue, whose g.f. is (1-z)/(3-3z-z(1-z^2)). - _Igor Kleiner_, Nov 03 2018
%C INVERT transform of (1, 0, 3, 0, 9, 0, 27, ...). - _Gary W. Adamson_, Jul 15 2019
%C Number of 3-compositions of n+2 with 1 not allowed as a part; see Hopkins & Ouvry reference. - _Brian Hopkins_, Aug 17 2020
%C Number of ways to tile a strip of length n with 3 colors of dominoes and 1 color of squares. - _Greg Dresden_, Sep 01 2021
%C Number of 3-permutations of n elements avoiding the patterns 231, 312, 321. See Bonichon and Sun. - _Michel Marcus_, Aug 20 2022
%C a(n-1), with a(-1) = 0, appears in the formula for the powers of the fundamental (integer) algebraic number c = (1 + sqrt(13))/2 = A209927: c^n = A052533(n) + a(n-1)*c. With the formulas given below, and also in A052533, in terms of S-Chebyshev polynomials this is valid also for the powers of 1/c = (-1 + sqrt(13))/6 = A356033. - _Wolfdieter Lang_, Nov 26 2023
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D Stephen Wolfram, 'The Mathematica Book,' Fourth Edition, Wolfram Media or Cambridge University Press, 1999, p. 96.
%H Vincenzo Librandi, G. C. Greubel and Robert Israel, <a href="/A006130/b006130.txt">Table of n, a(n) for n = 0..2485</a> (n = 0..149 from Vincenzo Librandi, n = 150..300 from G. C. Greubel)
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp.317-318.
%H Nicolas Bonichon and Pierre-Jean Morel, <a href="https://arxiv.org/abs/2202.12677">Baxter d-permutations and other pattern avoiding classes</a>, arXiv:2202.12677 [math.CO], 2022.
%H Brian Hopkins and Stéphane Ouvry, <a href="https://arxiv.org/abs/2008.04937">Combinatorics of Multicompositions</a>, arXiv:2008.04937 [math.CO], 2020.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=436">Encyclopedia of Combinatorial Structures 436</a>
%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html">On Linear Recurrence Equations Arising from Compositions of Positive Integers</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
%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 Arulalan Rajan, R. Vittal Rao, Ashok Rao and H. S. Jamadagni, <a href="http://arxiv.org/abs/1205.5398">Fibonacci Sequence, Recurrence Relations, Discrete Probability Distributions and Linear Convolution</a>, arXiv preprint arXiv:1205.5398 [math.PR], 2012.
%H A. G. Shannon and J. V. Leyendekkers, <a href="http://nntdm.net/volume-21-2015/number-2/35-42/">The Golden Ratio family and the Binet equation</a>, Notes on Number Theory and Discrete Mathematics, Vol. 21, 2015, No. 2, 35-42.
%H Nathan Sun, <a href="https://arxiv.org/abs/2208.08506">On d-permutations and Pattern Avoidance Classes</a>, arXiv:2208.08506 [math.CO], 2022.
%H A. K. Whitford, <a href="http://www.fq.math.ca/Scanned/15-1/whitford-a.pdf">Binet's formula generalized</a>, Fib. Quart., 15 (1977), pp. 21, 24, 29.
%H Fatih Yılmaz and Mustafa Özkan, <a href="https://doi.org/10.3390/axioms11060255">On the Generalized Gaussian Fibonacci Numbers and Horadam Hybrid Numbers: A Unified Approach</a>, Axioms (2022) Vol. 11, No. 6, 255.
%H Paul Thomas Young, <a href="https://www.fq.math.ca/Scanned/32-1/young.pdf">p-adic congruences for generalized Fibonacci sequences</a>, The Fibonacci Quarterly, Vol. 32, No. 1, 1994.
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,3).
%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials</a>.
%F O.g.f.: 1/(1 - x - 3*x^2). - _Simon Plouffe_ in his 1992 dissertation.
%F a(n) = (( (1 + sqrt(13))/2 )^(n+1) - ( (1 - sqrt(13))/2 )^(n+1))/sqrt(13).
%F a(n) = Sum_{k = 0..ceiling(n/2)} 3^k*C(n-k, k)). - _Benoit Cloitre_, _Philippe Deléham_, Mar 07 2004
%F a(0) = 1; a(1) = 1; for n >= 1, a(n+1) = (a(n)^2 - (-3)^n) / a(n-1). - _Philippe Deléham_, Mar 07 2004
%F The i-th term of the sequence is the (1, 2) entry in the i-th power of the 2 X 2 matrix M = ((-1, 1), (1, 2)). - _Simone Severini_, Oct 15 2005
%F a(n) = lower right term in the 2 X 2 matrix [0,3; 1,1]^n. - _Gary W. Adamson_, Mar 02 2008
%F a(n) = Sum_{k = 0..n} A109466(n,k)*(-3)^(n-k). - _Philippe Deléham_, Oct 26 2008
%F a(n) = Product_{k = 1..floor((n - 1)/2)} (1 + 12*cos(k*Pi/n)^2). - _Roger L. Bagula_ and _Gary W. Adamson_, Nov 21 2008
%F Limiting ratio = (1 + sqrt(13))/2 = 2.30277563.. = A098316 - 1. - _Roger L. Bagula_ and _Gary W. Adamson_, Nov 21 2008
%F G.f.: G(0)/(2-x), where G(k)= 1 + 1/(1 - x*(13*k - 1)/(x*(13*k + 12) - 2/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Jun 18 2013
%F G.f.: Q(0)/2 , where Q(k) = 1 + 1/(1 - x*(4*k+1 + 3*x)/( x*(4*k+3 + 3*x) + 1/Q(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Sep 08 2013
%F a(n) = ( Sum_{1 <= k <= n+1, k odd} C(n+1,k)*13^((k-1)/2) )/2^n. - _Vladimir Shevelev_, Feb 05 2014
%F E.g.f.: (1/(a - b))*(a*exp(a*x) - b*exp(b*x)), where 2*a = 1 + sqrt(13) and 2*b = 1 - sqrt(13). - _G. C. Greubel_, Aug 30 2015
%F a(n) = ((i*sqrt(3))^n)*S(n, (-i/sqrt(3))), with the imaginary unit i and the Chebyshev S polynomials (coefficients in A049310). - _Wolfdieter Lang_, Feb 18 2018
%F a(n) = hypergeom([(1-n)/2, -n/2], [-n], -12) for n >= 1. - _Peter Luschny_, Feb 18 2018
%F a(n) = 3 * (-3)^n * a(-2-n) for all n in Z. - _Michael Somos_, Nov 04 2018
%F a(n) = ( sqrt(3) )^n * Fibonacci(n+1, 1/sqrt(3)). - _G. C. Greubel_, Dec 26 2019
%F a(n) = numerator of the continued fraction 1 + 3/(1 + 3/(1 + 3/ ... + 3/1)) with exactly n 1's, for n>0. - _Greg Dresden_ and _Alexander Mark_, Aug 16 2020
%F With an initial 0 prepended, the sequence [0, 1, 1, 4, 7, 19, 40, ...] satisfies the congruences a(n*p^k) == e*a(n*p^(k-1)) (mod p^k) for positive integers k and n and all primes p, where e = +1 for the primes p listed in A296937, e = 0 if p = 13, otherwise e = -1. See Young, Theorem 1, Corollary 1 (i). - _Peter Bala_, Dec 28 2022
%F From _Wolfdieter Lang_, Nov 27 2023: (Start)
%F a(n) = sqrt(-3)^n*S(n, 1/sqrt(-3)) with the S-Chebyshev polynomials (see A049310), also valid for negative n, using S(-n, x) = -S(n-2, x), for n >= 2, and S(-1, x) = 0. See above the formula in terms of Fibonacci polynomials).
%F a(n) = A052533(n+2)/3, for n >= 0. (End)
%e G.f. = 1 + x + 4*x^2 + 7*x^3 + 19*x^4 + 40*x^5 + 97*x^6 + 217*x^7 + ...
%p a := n -> add(binomial(n-k, k)*3^k, k=0..n): seq(a(n), n=0..29); # _Zerinvary Lajos_, Sep 30 2006
%p f:= gfun:-rectoproc({a(n) = a(n-1) + 3*a(n-2), a(0) = 1, a(1) = 1},a(n),remember):
%p map(f, [$0..100]); # _Robert Israel_, Aug 31 2015
%t a[0] = a[1] = 1; a[n_] := a[n] = a[n - 1] + 3a[n - 2]; Table[ a[n], {n, 0, 30}]
%t LinearRecurrence[{1, 3}, {1, 1}, 30] (* _Vincenzo Librandi_, Oct 17 2012 *)
%t RecurrenceTable[{a[n]== a[n-1] + 3*a[n-2], a[0]== 1, a[1]== 1}, a, {n,0,30}] (* _G. C. Greubel_, Aug 30 2015 *)
%t a[0] := 1; a[n_] := Hypergeometric2F1[1/2-n/2, -n/2, -n, -12]; Table[a[n], {n, 0, 29}] (* _Peter Luschny_, Feb 18 2018 *)
%t a[ n_] := With[{s = Sqrt[-1/3]}, ChebyshevU[n, s/2] / s^n] // Simplify; (* _Michael Somos_, Nov 04 2018 *)
%o (Sage) from sage.combinat.sloane_functions import recur_gen2
%o it = recur_gen2(1,1,1,3)
%o [next(it) for i in range(30)] # _Zerinvary Lajos_, Jun 25 2008
%o (Sage) [lucas_number1(n,1,-3) for n in range(1, 31)] # _Zerinvary Lajos_, Apr 22 2009
%o (PARI) Vec(1/(1-x-3*x^2+O(x^66))) \\ _Franklin T. Adams-Watters_, May 26 2011
%o (Python)
%o an = an1 = 1
%o while an<10**5:
%o print(an)
%o an1 += an*3
%o an = an1 - an*3 # _Alex Ratushnyak_, Apr 20 2012
%o (Magma) [n le 2 select 1 else Self(n-1) + 3*Self(n-2): n in [1..40]]; // _Vincenzo Librandi_, Oct 17 2012
%o (GAP) a := [1, 1];; for n in [3..30] do a[n] := a[n-1] + 3*a[n-2]; od; a; # _Muniru A Asiru_, Feb 18 2018
%Y Cf. A006131, A015440, A049310, A052533, A140167, A175291 (Pisano periods), A099232 (partial sums), A274977.
%Y Cf. A209927, A356033.
%K nonn,easy
%O 0,3
%A _N. J. A. Sloane_
|
