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. 21
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, 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) = (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

(PARI) a(n)=([0, 1; 1, 3]^(n-1)*[1; 4])[1, 1] \\ Charles R Greathouse IV, Aug 14 2017

CROSSREFS

Partial sums of A052906. Pairwise sums of A006190.

Cf. A136159, A290948, A003945.

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 September 26 00:10 EDT 2017. Contains 292500 sequences.