login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003688 a(n) = 3*a(n-1) + a(n-2), with a(1)=1 and a(2)=4. 20
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 (list; graph; refs; listen; history; text; internal format)
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 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)

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

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 419

M. Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, 2014; http://matinf.pmfbl.org/wp-content/uploads/2015/01/za-arhiv-18.-1.pdf

Tanya Khovanova, Recursive Sequences

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

FORMULA

a(n) = (1/2-sqrt(13)/26)*(3/2+sqrt(13)/2)^n+(1/2+sqrt(13)/26)*(3/2-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)} C(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

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 eq 1 select 1 else n eq 2 select 4 else 3*Self(n-1)+Self(n-2): n in [1..30] ]; // Vincenzo Librandi, Aug 19 2011

CROSSREFS

Partial sums of A052906. Pairwise sums of A006190.

Cf. A136159.

Cf. A003945. - Gary W. Adamson, Aug 05 2010

Sequence in context: A266494 A121486 A188176 * A033434 A113986 A149426

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 24 20:05 EDT 2017. Contains 288707 sequences.