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

Author

Frans J. Faase

Keywords

• nonn
• easy

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

Examples

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

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).

Crossrefs

Partial sums of A052906. Pairwise sums of A006190.

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

Cf. A374439.

Programs

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

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 *)

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

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

a(n) = 3^n*Sum_{k=0..n} A374439(n, k)*(-1/3)^k. - Peter Luschny, Jul 26 2024

Extensions

Formula added by Olivier Gérard, Aug 15 1997

Name clarified by Michel Marcus, Oct 16 2016