A003688 a(n) = 3*a(n-1) + a(n-2), with a(1)=1 and a(2)=4.

1, 4, 13, 43, 142, 469, 1549, 5116, 16897, 55807, 184318, 608761, 2010601, 6640564, 21932293, 72437443, 239244622, 790171309, 2609758549, 8619446956, 28468099417, 94023745207, 310539335038, 1025641750321, 3387464586001, 11188035508324, 36951571110973

Offset

1,2

Comments

Number of 2-factors in K_3 X P_n.

Form the graph with matrix [1,1,1,1;1,1,1,0;1,1,0,1;1,0,1,1]. The sequence 1,1,4,13,... with g.f. (1-2*x)/(1-3*x-x^2) counts closed walks of length n at the vertex of degree 5. - Paul Barry, Oct 02 2004

a(n) is term (1,1) in M^n, where M is the 3x3 matrix [1,1,2; 1,1,1; 1,1,1]. - Gary W. Adamson, Mar 12 2009

Starting with 1, INVERT transform of A003945: (1, 3, 6, 12, 24, ...). - Gary W. Adamson, Aug 05 2010

Row sums of triangle

m/k.|..0.....1.....2.....3.....4.....5.....6.....7

==================================================

.0..|..1

.1..|..1.....3

.2..|..1.....3.....9

.3..|..1.....6.....9.....27

.4..|..1.....6....27.....27...81

.5..|..1.....9....27....108...81...243

.6..|..1.....9....54....108..405...243...729

.7..|..1....12....54....270..405..1458...729..2187

which is the triangle for numbers 3^k*C(m,k) with duplicated diagonals. - Vladimir Shevelev, Apr 12 2012

Pisano period lengths: 1, 3, 1, 6, 12, 3, 16, 12, 6, 12, 8, 6, 52, 48, 12, 24, 16, 6, 40, 12, ... - R. J. Mathar, Aug 10 2012

a(n-1) is the number of length-n strings of 4 letters {0,1,2,3} with no two adjacent nonzero letters identical. The general case (strings of L letters) is the sequence with g.f. (1+x)/(1-(L-1)*x-x^2). - Joerg Arndt, Oct 11 2012

References

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Joerg Arndt, Matters Computational (The Fxtbook)

Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.

C. Bautista-Ramos and C. Guillen-Galvan, Fibonacci numbers of generalized Zykov sums, J. Integer Seq., 15 (2012), Article 12.7.8.

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

F. Faase, Counting Hamiltonian cycles in product graphs

F. Faase, Results from the counting program

Sergio Falcón and Ángel Plaza, On the Fibonacci k-numbers, Chaos, Solitons & Fractals 2007; 32(5): 1615-24.

Taras Goy and Mark Shattuck, Determinants of Toeplitz-Hessenberg Matrices with Generalized Leonardo Number Entries, Ann. Math. Silesianae (2023). See p. 15.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 419

Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.

Tanya Khovanova, Recursive Sequences

Index entries for linear recurrences with constant coefficients, signature (3,1).

Formula

a(n) = ((13 - sqrt(13))/26)*((3 + sqrt(13))/2)^n + ((13 + sqrt(13))/26)*((3 - sqrt(13))/2)^n. - Paul Barry, Oct 02 2004

a(n) = Sum_{k=0..n} 2^k*A055830(n,k). - Philippe Deléham, Oct 18 2006

Starting (1, 1, 4, 13, 43, 142, 469, ...), row sums (unsigned) of triangle A136159. - Gary W. Adamson, Dec 16 2007

G.f.: x*(1+x)/(1-3*x-x^2). - Philippe Deléham, Nov 03 2008

a(n) = A006190(n) + A006190(n-1). - Sergio Falcon, Nov 26 2009

For n>=2, a(n) = F_n(3) + F_(n+1)(3), where F_n(x) is Fibonacci polynomial (cf. A049310): F_n(x) = Sum_{i=0..floor((n-1)/2)} binomial(n-i-1,i) * x^(n-2*i-1). - Vladimir Shevelev, Apr 13 2012

G.f.: G(0)*(1+x)/(2-3*x), where G(k) = 1 + 1/(1 - (x*(13*k-9))/( x*(13*k+4) - 6/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 15 2013

a(n)^2 is the denominator of continued fraction [3,3,...,3, 5, 3,3,...,3], which has n-1 3's before, and n-1 3's after, the middle 5. - Greg Dresden, Sep 18 2019

a(n) = Sum_{k=0..n} A046854(n-1,k)*3^k. - R. J. Mathar, Feb 10 2024

Example

G.f. = x + 4*x^2 + 13*x^3 + 43*x^4 + 142*x^5 + 469*x^6 + 1549*x^7 + 5116*x^8 + ...

Maple

with(combinat): a:=n->fibonacci(n, 3)-2*fibonacci(n-1, 3): seq(a(n), n=2..25); # Zerinvary Lajos, Apr 04 2008

Mathematica

a[n_] := (MatrixPower[{{1, 3}, {1, 2}}, n].{{1}, {1}})[[1, 1]]; Table[ a[n], {n, 0, 23}] (* Robert G. Wilson v, Jan 13 2005 *)
LinearRecurrence[{3, 1}, {1, 4}, 30] (* Harvey P. Dale, Mar 15 2015 *)

Prog

(Magma) [n le 2 select 4^(n-1) else 3*Self(n-1)+Self(n-2): n in [1..30]]; // Vincenzo Librandi, Aug 19 2011
(PARI) a(n)=([0, 1; 1, 3]^(n-1)*[1; 4])[1, 1] \\ Charles R Greathouse IV, Aug 14 2017
(SageMath)
@CachedFunction
def a(n): # a = A003688
    if (n<3): return 4^(n-1)
    else: return 3*a(n-1) + a(n-2)
[a(n) for n in range(1, 41)] # G. C. Greubel, Dec 26 2023

Crossrefs

Cf. A003945, A006190, A049310, A055830, A136159, A290948.

Partial sums of A052906.

Pairwise sums of A006190.

Sequence in context: A121486 A339063 A188176 * A033434 A297928 A363366

Adjacent sequences: A003685 A003686 A003687 * A003689 A003690 A003691

Keyword

nonn,easy

Author

Frans J. Faase

Extensions

Formula added by Olivier Gérard, Aug 15 1997

Name clarified by Michel Marcus, Oct 16 2016

Status

approved