A018902 -id:A018902 - cp's OEIS frontend

A116415 a(n) = 5a(n-1) - 3a(n-2).

1, 5, 22, 95, 409, 1760, 7573, 32585, 140206, 603275, 2595757, 11168960, 48057529, 206780765, 889731238, 3828313895, 16472375761, 70876937120, 304967558317, 1312206980225, 5646132226174, 24294040190195, 104531804272453

Offset: 0

Paul Barry, Feb 13 2006

Row sums of A116414.
Partial sums of A018902. - Greg Dresden and Mulong Xu, Aug 31 2024
Binomial transform of the sequence A006190. - Sergio Falcon, Nov 23 2007
a(n+1) equals the number of words of length n over {0,1,2,3,4} avoiding 01, 02 and 03. - Milan Janjic, Dec 17 2015

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Sergio Falcón, Iterated Binomial Transforms of the k-Fibonacci Sequence, British Journal of Mathematics & Computer Science, 4 (22): 2014.
Sergio Falcón and Ángel Plaza, On k-Fibonacci sequences and polynomials and their derivatives, Chaos, Solitons & Fractals, Volume 39, Issue 3, 15 February 2009, Pages 1005-1019.
Index entries for linear recurrences with constant coefficients, signature (5,-3).

Cf. A001906, A007070, A018902, A084326.

I:=[1,5]; [n le 2 select I[n] else 5*Self(n-1)-3*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Dec 16 2015

Join[{a=1,b=5},Table[c=5*b-3*a;a=b;b=c,{n,60}]] (* Vladimir Joseph Stephan Orlovsky, Jan 18 2011 *)
LinearRecurrence[{5,-3},{1,5},40] (* Harvey P. Dale, Jun 19 2012 *)

Vec(1/(1-5*x+3*x^2) + O(x^100)) \\ Altug Alkan, Dec 17 2015

[lucas_number1(n,5,3) for n in range(1, 24)] # Zerinvary Lajos, Apr 22 2009

G.f.: 1/(1 - 5*x + 3*x^2).
a(n) = Sum_{k=0..n} Sum_{j=0..n} C(n-j,k)*C(k+j,j)*3^j.
a(n) = (1/sqrt(13))*(((5+sqrt(13))/2)^n - ((5-sqrt(13))/2)^n). - Sergio Falcon, Nov 23 2007
If p[i] = (3^i-1)/2, and if A is the Hessenberg matrix of order n defined by: A[i,j] = p[j-i+1], (i <= j), A[i,j] = -1, (i = j+1), and A[i,j] = 0 otherwise. Then, for n >= 1, a(n-1) = det(A). - Milan Janjic, May 08 2010
a(n) = 4*a(n-1) + a(n-2) + a(n-3) + ... + a(0) + 1. These expansions with the partial sums on one side can be generated en masse by taking the g.f. of the partial sum and its partial fraction, 1/(1-x)/(1 - 5*x + 3*x^2) = -1/(1-x)+(2-3*x)/(1 - 5*x + 3*x^2) and reading this as a(0) + a(1) + ... + a(n) = -1 + 2*a(n)- 3*a(n-1). - Gary W. Adamson, Feb 18 2011

A081704 Let f(0)=1, f(1)=t, f(n+1) = (f(n)^2+t^n)/f(n-1). f(t) is a polynomial with integer coefficients. Then a(n) = f(n) when t=3.

Original entry on oeis.org

1, 3, 12, 51, 219, 942, 4053, 17439, 75036, 322863, 1389207, 5977446, 25719609, 110665707, 476169708, 2048851419, 8815747971, 37932185598, 163213684077, 702271863591, 3021718265724, 13001775737847, 55943723892063, 240713292246774, 1035735289557681

Offset: 0

Victor Ufnarovski (ufn(AT)maths.lth.se), Apr 02 2003

f satisfies the linear recursion f(n+1) = (t+2)*f(n)-t*f(n-1). For t=3 this gives a(n+1) = 5*a(n)-3*a(n-1).

Given the 3 X 3 matrix [1,1,1; 1,1,2; 1,1,3] = M, a(n) = term (1,1) in M^(n+1). - Gary W. Adamson, Aug 06 2010

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-3).

Cf. A006012, A001519.

Equals 3*A018902(n-1) for n>0.

f := proc(n) if n=0 then 1 elif n=1 then t else sort(simplify((f(n-1)^2+t^(n-1))/f(n-2)),t) fi end; a := i->subs(t=3,f(i));

a[0]=1; a[1]=3; a[n_] := a[n]=5a[n-1]-3a[n-2]; Array[a,25,0]
LinearRecurrence[{5,-3},{1,3},30] (* Harvey P. Dale, Jul 28 2013 *)

Vec((1-2*x)/(1-5*x+3*x^2) + O(x^30)) \\ Colin Barker, Nov 26 2016

a(n+1) = (a(n)^2 + 3^n) / a(n-1).
From Philippe Deléham, Nov 14 2008: (Start)
G.f.: (1-2*x)/(1-5*x+3*x^2).
a(n) = Sum_{k, 0<=k<=n} A147703(n,k)*2^k. (End)
a(n) = (2^(-1-n)*((5-sqrt(13))^n*(-1+sqrt(13)) + (1+sqrt(13))*(5+sqrt(13))^n))/sqrt(13). - Colin Barker, Nov 26 2016
E.g.f.: exp(5*x/2)*(sqrt(13)*cosh(sqrt(13)*x/2) + sinh(sqrt(13)*x/2))/sqrt(13). - Stefano Spezia, Jul 09 2022

A331406 Array read by antidiagonals: A(n,m) is the number of ways to place non-adjacent counters on the black squares of a 2n-1 X 2m-1 checker board.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 17, 8, 1, 1, 16, 73, 73, 16, 1, 1, 32, 314, 689, 314, 32, 1, 1, 64, 1351, 6556, 6556, 1351, 64, 1, 1, 128, 5813, 62501, 139344, 62501, 5813, 128, 1, 1, 256, 25012, 596113, 2976416, 2976416, 596113, 25012, 256, 1

Offset: 0

Andrew Howroyd, Jan 16 2020

The array has been extended with A(n,0) = A(0,m) = 1 for consistency with recurrences and existing sequences.
The checker board is such that the black squares are in the corners and adjacent means diagonally adjacent, since the white squares are not included.
Equivalently, A(n,m) is the number of independent sets in the generalized Aztec diamond graph E(L_{2n-1}, L_{2m-1}). The E(L_{2n-1},L_{2m-1}) Aztec diamond is the graph with vertices {(a,b) : 1<=a<=2n-1, 1<=b<=2m-1, a+b even} and edges between (a,b) and (c,d) if and only if |a-b|=|c-d|=1.
All rows (or columns) are linear recurrences with constant coefficients. For n > 0 an upper bound on the order of the recurrence is A005418(n-1), which is the number of binary words of length n up to reflection.
A stronger upper bound on the recurrence order is A005683(n+2). This upper bound is exact for at least 1 <= n <= 10. This bound follows from considerations about which patterns of counters in a row are redundant because they attack the same points in adjacent rows. For example, the pattern of counters 1101101 is equivalent to 1111111 because they each attack all points in the neighboring rows.
It appears that the denominators for the recurrences are the same as those for the rows and columns of A254414. This suggests there is a connection.

			Array begins:
===========================================================
n\m | 0  1    2      3        4          5            6
----+------------------------------------------------------
  0 | 1  1    1      1        1          1            1 ...
  1 | 1  2    4      8       16         32           64 ...
  2 | 1  4   17     73      314       1351         5813 ...
  3 | 1  8   73    689     6556      62501       596113 ...
  4 | 1 16  314   6556   139344    2976416     63663808 ...
  5 | 1 32 1351  62501  2976416  142999897   6888568813 ...
  6 | 1 64 5813 596113 63663808 6888568813 748437606081 ...
  ...
Case A(2,2): the checker board has 5 black squares as shown below.
      __    __
     |__|__|__|
      __|__|__
     |__|  |__|
If a counter is placed on the central square then a counter cannot be placed on the other 4 squares, otherwise counters can be placed in any combination. The total number of arrangements is then 1 + 2^4 = 17, so A(2, 2) = 17.

Andrew Howroyd, Table of n, a(n) for n = 0..860
Eric Weisstein's World of Mathematics, Independent Vertex Set
Wikipedia, Independent set
Z. Zhang, Merrifield-Simmons index of generalized Aztec diamond and related graphs, MATCH Commun. Math. Comput. Chem. 56 (2006) 625-636.

Rows n=0..5 are A000012, A000079, A018902, A254150, A254151, A254152.
Main diagonal is A054867.
Cf. A005418, A005683, A089934, A254414.

step1(v)={vector(#v/2, t, my(i=t-1); sum(j=0, #v-1, if(!bitand(i, bitor(j, j>>1)), v[1+j])))}
step2(v)={vector(#v*2, t, my(i=t-1); sum(j=0, #v-1, if(!bitand(i, bitor(j, j<<1)), v[1+j])))}
T(n,k)={if(n==0||k==0, 1, my(v=vector(2^k, i, 1)); for(i=2, n, v=step2(step1(v))); vecsum(v))}
{ for(n=0, 7, for(k=0, 7, print1(T(n,k), ", ")); print) }

A(n,m) = A(m,n).

A087165 a(n)=1 when n == 1 (mod 4), otherwise a(n) = a(n - ceiling(n/4)) + 1. Removing all the 1's results in the original sequence with every term incremented by 1.

Original entry on oeis.org

1, 2, 3, 4, 1, 5, 2, 6, 1, 3, 7, 2, 1, 4, 8, 3, 1, 2, 5, 9, 1, 4, 2, 3, 1, 6, 10, 2, 1, 5, 3, 4, 1, 2, 7, 11, 1, 3, 2, 6, 1, 4, 5, 2, 1, 3, 8, 12, 1, 2, 4, 3, 1, 7, 2, 5, 1, 6, 3, 2, 1, 4, 9, 13, 1, 2, 3, 5, 1, 4, 2, 8, 1, 3, 6, 2, 1, 7, 4, 3, 1, 2, 5, 10, 1, 14, 2, 3, 1, 4, 6, 2, 1, 5, 3, 9, 1, 2, 4, 7, 1, 3, 2

Offset: 1

Paul D. Hanna, Aug 24 2003

Indices of records are given by A087192: a(A087192(n))=n, where A087192(n) = ceiling(A087192(n-1)*4/3).
From Benoit Cloitre, Mar 07 2009: (Start)
To construct the sequence:
Step 1: start from a sequence of 1's, leaving 3 undefined places between 1's, giving 1,(),(),(),1,(),(),(),1,(),(),(),1,(),(),(),1,(),(),(),1,...
Step 2: replace the first undefined place with a 2 and leave 3 undefined places between 2's, giving 1,2,(),(),1,(),2,(),1,(),(),2,1,(),(),(),1,2,(),(),1,...
Step 3: replace the first undefined place with a 3 and leave 3 undefined places between 3's, giving 1,2,3,(),1,(),2,(),1,3,(),2,1,(),(),3,1,2,(),(),1,...
Step 4: replace the first undefined place with a 4 and leave 3 undefined places between 4's, giving 1,2,3,4,1,(),2,(),1,3,(),2,1,4,(),3,1,2,(),(),1,...
Iterating the process indefinitely yields the sequence: 1,2,3,4,1,5,2,6,1,3,7,2,1,4,8,3,1,2,5,9,1,... (End)

Cf. A001511, A087088, A087192, A244041.

a(n+1) - a(n) = 4*A018902(n-3), n > 2.

for n from 1 to 100 do
  if n mod 4 = 1 then A[n]:= 1
  else A[n]:= A[n - ceil(n/4)] + 1
  fi
od:
seq(A[n],n=1..100); # Robert Israel, Aug 05 2014

a(n)=my(s); while(n>4, if(n%4==1, return(s+1)); n=(n\4*3)+max(n%4 - 1,0); s++); s+n \\ Charles R Greathouse IV, Sep 22 2022

a(n) = 4 + A244041(4*(n-1)) - A244041(4*n). - Tom Edgar and James Van Alstine, Aug 05 2014
a(4*n) = a(3*n)+1.
a(4*n+1) = 1.
a(4*n+2) = a(3*n+1)+1.
a(4*n+3) = a(3*n+2)+1. - Robert Israel, Aug 05 2014
a(n) < k*log(n) + 4 for n > 1 where k = 1/log(4/3) < 3.5. - Charles R Greathouse IV, Sep 22 2022

A095940 a(n+2) = 5a(n+1) - 3a(n) (n >= 1); a(0) = 0, a(1) = 1, a(2) = 4.

Original entry on oeis.org

0, 1, 4, 17, 73, 314, 1351, 5813, 25012, 107621, 463069, 1992482, 8573203, 36888569, 158723236, 682950473, 2938582657, 12644061866, 54404561359, 234090621197, 1007239421908, 4333925245949, 18647907964021, 80237764082258

Offset: 0

N. J. A. Sloane, Jul 13 2004

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

Cf. A018902; equals A095934 - A095939.

Join[{0},LinearRecurrence[{5,-3},{1,4},30]] (* Harvey P. Dale, Aug 20 2011 *)

G.f.: (x-x^2)/(3*x^2-5*x+1). - Harvey P. Dale, Aug 20 2011

Extended by Ray Chandler, Jul 16 2004

A228352 Triangle read by rows, giving antidiagonals of an array of sequences representing the number of compositions of n when there are N types of ones (the sequences in the array begin (1, N, ...)).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 5, 4, 1, 4, 10, 13, 8, 1, 5, 17, 34, 34, 16, 1, 6, 26, 73, 116, 89, 32, 1, 7, 37, 136, 314, 396, 233, 64, 1, 8, 50, 229, 712, 1351, 1352, 610, 128, 1, 9, 65, 358, 1418, 3728, 5813, 4616, 1597, 256, 1, 10, 82, 529, 2564, 8781, 19520, 25012, 15760, 4181, 512

Offset: 1

Gary W. Adamson, Aug 20 2013

The array sequence beginning (1, N, ...) is such that a(n) in the sequence represents the numbers of compositions of n when there are N types of ones.

			Array sequence beginning (1, 3, 10, 34, 116, ...) is the binomial transform of (1, 2, 5, 12, 70, ...) in A073133.
First few sequences in the array:
  1, 1,  2,  4,   8,  16, ...; = A011782
  1, 2,  5, 13,  34,  89, ...; = A001519
  1, 3, 10, 34, 116, 396, ...; = A007052
... followed by A018902, A018903, A018904, the latter beginning (1, 6, ...). First few rows of the triangle:
  1;
  1,  1;
  1,  2,  2;
  1,  3,  5,   4;
  1,  4, 10,  13,    8;
  1,  5, 17,  34,   34,   16;
  1,  6, 26,  73,  116,   89,    32;
  1,  7, 37, 136,  314,  396,   233,    64;
  1,  8, 50, 229,  712, 1351,  1352,   610,   128;
  1,  9, 65, 358, 1418, 3728,  5813,  4616,  1597,  256;
  1, 10, 82, 529, 2564, 8781, 19520, 25012, 15760, 4181, 512;
  ...

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A073133, A011782, A001519, A007052, A018902, A018903, A018904.

A:= proc(N, n) option remember;
      `if`(n=0, 1, N*A(N, n-1) +add(A(N, n-j), j=2..n))
    end:
seq(seq(A(d-n, n), n=0..d-1), d=1..11); # Alois P. Heinz, Aug 20 2013

A[k_, n_] := A[k, n] = If[n == 0, 1, k*A[k, n-1] + Sum[A[k, n-j], {j, 2, n}]]; Table[A[d-n, n], {d, 1, 11}, {n, 0, d-1}] // Flatten (* Jean-François Alcover, May 27 2016, after Alois P. Heinz *)

Antidiagonals of an array in which a(n+2) = (N+1)*a(n+1) - (n-1)*a(n); with array sequences beginning (1, N, ...).
Array sequence beginning (1, N, ...) is the binomial transform of the sequence in A073133 beginning (1, (N-1), ...).
Given the first sequence of the array is (1, 1, 2, 4, 8, 16, ...), successive sequences are INVERT transforms of previous sequences.
Array sequence beginning (1, N, ...) is such that a(n), n>1 is N*(a) + a(n-1) + a(n-2) + a(n-3) + a(n-4) + ... + a(0).

A052629 Expansion of e.g.f. (1-x)/(1-5x+3x^2).

Original entry on oeis.org

1, 4, 34, 438, 7536, 162120, 4185360, 126060480, 4339278720, 168038478720, 7230318681600, 342214829510400, 17669683572710400, 988372892015308800, 59538455210371737600, 3842709218808235776000, 264549049753191211008000

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 575 [broken link].

Cf. A018902.

spec := [S,{S=Sequence(Union(Z,Z,Z,Prod(Z,Sequence(Z))))},labeled]: seq(combstruct[count](spec,size=n), n=0..20);

E.g.f.: -(-1+x)/(1-5*x+3*x^2).
Recurrence: a(0)=1, a(1)=4, (3*n^2+9*n+6)*a(n) +(-10-5*n)*a(n+1) +a(n+2)=0.
Sum(-1/13*(-3+_alpha)*_alpha^(-1-n), _alpha=RootOf(1-5*_Z+3*_Z^2))*n!
a(n) = n!*A018902(n). - R. J. Mathar, Jun 03 2022

cp's OEIS Frontend

A116415 a(n) = 5*a(n-1) - 3*a(n-2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A081704 Let f(0)=1, f(1)=t, f(n+1) = (f(n)^2+t^n)/f(n-1). f(t) is a polynomial with integer coefficients. Then a(n) = f(n) when t=3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A331406 Array read by antidiagonals: A(n,m) is the number of ways to place non-adjacent counters on the black squares of a 2n-1 X 2m-1 checker board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A087165 a(n)=1 when n == 1 (mod 4), otherwise a(n) = a(n - ceiling(n/4)) + 1. Removing all the 1's results in the original sequence with every term incremented by 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

PARI

Formula

A095940 a(n+2) = 5*a(n+1) - 3*a(n) (n >= 1); a(0) = 0, a(1) = 1, a(2) = 4.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A228352 Triangle read by rows, giving antidiagonals of an array of sequences representing the number of compositions of n when there are N types of ones (the sequences in the array begin (1, N, ...)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A052629 Expansion of e.g.f. (1-x)/(1-5x+3x^2).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A116415 a(n) = 5a(n-1) - 3a(n-2).

A095940 a(n+2) = 5a(n+1) - 3a(n) (n >= 1); a(0) = 0, a(1) = 1, a(2) = 4.