A020698 -id:A020698 - cp's OEIS frontend

A107839 a(n) = 5a(n-1) - 2a(n-2); a(0)=1, a(1)=5.

1, 5, 23, 105, 479, 2185, 9967, 45465, 207391, 946025, 4315343, 19684665, 89792639, 409593865, 1868384047, 8522732505, 38876894431, 177339007145, 808941246863, 3690028220025, 16832258606399, 76781236591945, 350241665746927, 1597645855550745, 7287745946259871

Offset: 0

Emeric Deutsch, Jun 12 2005

Kekulé numbers for certain benzenoids.
This is the number of spanning, connected subgraphs of the "ladder graph" of n squares (ladder graph = the vertices and edges of the tiling of a 1 X n rectangle by unit squares). - David Pasino (davepasino(AT)yahoo.com), Sep 18 2007
a(n) equals the number of words of length n over {0,1,2,3,4} avoiding 01 and 02. - Milan Janjic, Dec 17 2015

S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 78).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Tomislav Doslic, Planar polycyclic graphs and their Tutte polynomials, Journal of Mathematical Chemistry, Volume 51, Issue 6, 2013, pp. 1599-1607. See Cor. 3.7(e).
A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 117. Book's website
Index entries for linear recurrences with constant coefficients, signature (5,-2).

Cf. A020698, A055099 (inverse binomial transform).

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

a:= n-> (<<0|1>, <-2|5>>^n)[2$2]:
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 21 2020

a[n_] := (MatrixPower[{{1, 2}, {1, 4}}, n].{{1}, {1}})[[2, 1]]; Table[a[n], {n, 0, 40}] (* Vladimir Joseph Stephan Orlovsky, Feb 19 2010 *)
Table[(((5 + Sqrt[17])/2)^n - ((5 - Sqrt[17])/2)^n)/Sqrt[17], {n, 20}] // Expand (* Eric W. Weisstein, Nov 03 2024 *)
LinearRecurrence[{5, -2}, {1, 5}, 20] (* Eric W. Weisstein, Nov 03 2024 *)
CoefficientList[Series[1/(1 - 5 x + 2 x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Nov 03 2024 *)

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

[lucas_number1(n,5,2) for n in range(27)] # Zerinvary Lajos, Jun 25 2008

a(n) = A020698(n)-2*A020698(n-1) (n>=1).
a(n) = [M^(n+1)]1,2, where M is the 3 X 3 matrix defined as follows: M = [2,1,2; 1,1,1; 2,1,2]. - _Simone Severini, Jun 12 2006
a(n) = (((5 + s)/2)^(n+1) - ((5 - s)/2)^(n+1))/s with s = 17^(1/2). - David Pasino (davepasino(AT)yahoo.com), Jan 09 2009
G.f.: 1/(1 - 5*x + 2*x^2). - R. J. Mathar, Apr 07 2009
E.g.f.: exp(5*x/2)*(17*cosh(sqrt(17)*x/2) + 5*sqrt(17)*sinh(sqrt(17)*x/2))/17. - Stefano Spezia, Jun 17 2025

A207997 T(n,k) = number of n X k 0..2 arrays with new values 0..2 introduced in row major order and no element equal to any horizontal or vertical neighbor (colorings ignoring permutations of colors).

Original entry on oeis.org

1, 1, 1, 2, 3, 2, 4, 9, 9, 4, 8, 27, 41, 27, 8, 16, 81, 187, 187, 81, 16, 32, 243, 853, 1302, 853, 243, 32, 64, 729, 3891, 9075, 9075, 3891, 729, 64, 128, 2187, 17749, 63267, 96831, 63267, 17749, 2187, 128, 256, 6561, 80963, 441090, 1034073, 1034073, 441090, 80963

Offset: 1

R. H. Hardin, Feb 22 2012

Number of colorings of the grid graph P_n X P_k using a maximum of 3 colors up to permutation of the colors. - Andrew Howroyd, Jun 26 2017

			Table starts
..1....1.....2.......4.........8.........16...........32............64
..1....3.....9......27........81........243..........729..........2187
..2....9....41.....187.......853.......3891........17749.........80963
..4...27...187....1302......9075......63267.......441090.......3075255
..8...81...853....9075.....96831....1034073.....11045757.....117997043
.16..243..3891...63267...1034073...16932816....277458045....4547477370
.32..729.17749..441090..11045757..277458045...6978332618..175605187731
.64.2187.80963.3075255.117997043.4547477370.175605187731.6787438272198
...
Some solutions for n=4, k=3:
..0..1..2....0..1..0....0..1..0....0..1..2....0..1..2....0..1..2....0..1..0
..2..0..1....2..0..2....1..0..2....1..2..1....2..0..1....1..2..1....1..2..1
..0..2..0....0..1..0....2..1..0....0..1..2....0..2..0....0..1..2....2..0..2
..1..0..1....1..2..1....1..0..1....1..2..0....2..0..2....2..0..1....1..2..0

R. H. Hardin, Table of n, a(n) for n = 1..544
R. J. Mathar, Counting 2-way monotonic terrace forms over rectangular landscapes, vixra:1511.0225, eq. (33)-(35).
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Vertex Coloring
Wikipedia, Graph Coloring

Cf. A020698 (column 3), A078100 (column 4), A207994 (column 5), A207995 (column 6), A207996 (column 7).
Main diagonal is A207993.
Cf. A198715 (4 colorings), A198906 (5 colorings), A198982 (6 colorings), A198723 (7 colorings), A198914 (8 colorings), A207868 (unlimited).

2*T(n,m) = A078099(n,m) for m>1. - R. J. Mathar, Nov 23 2015

A052984 a(n) = 5a(n-1) - 2a(n-2) for n>1, with a(0) = 1, a(1) = 3.

Original entry on oeis.org

1, 3, 13, 59, 269, 1227, 5597, 25531, 116461, 531243, 2423293, 11053979, 50423309, 230008587, 1049196317, 4785964411, 21831429421, 99585218283, 454263232573, 2072145726299, 9452202166349, 43116719379147, 196679192563037, 897162524056891, 4092454235158381

Offset: 0

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

a(n) = A020698(n) - 4*A020698(n-1) + 4*A020698(n-2) (n>=2). Kekulé numbers for certain benzenoids. - Emeric Deutsch, Jun 12 2005

S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 78).
Stanley, Richard P. "Some Linear Recurrences Motivated by Stern’s Diatomic Array." The American Mathematical Monthly 127.2 (2020): 99-111.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1058
Richard P. Stanley, Some Linear Recurrences Motivated by Stern's Diatomic Array, arXiv:1901.04647 [math.CO], 2019. See p. 3.
Zeying Xu, Graphical zonotopes with the same face vector, arXiv:1809.08764 [math.CO], 2018.
Index entries for linear recurrences with constant coefficients, signature (5,-2).

Cf. A005824, A020698, A107839, A147703.

a:=[1,3];; for n in [3..30] do a[n]:=5*a[n-1]-2*a[n-2]; od; a; # G. C. Greubel, Oct 23 2019

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-2*x)/(1-5*x+2*x^2) )); // G. C. Greubel, Feb 10 2019

a:=[1,3]; [n le 2 select a[n] else 5*Self(n-1)-2*Self(n-2):n in [1..25]]; // Marius A. Burtea, Oct 23 2019

spec:= [S,{S=Sequence(Union(Prod(Sequence(Union(Z,Z)),Union(Z,Z)),Z))}, unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
a[0]:=1: a[1]:=3: for n from 2 to 25 do a[n]:=5*a[n-1]-2*a[n-2] od: seq(a[n],n=0..25); # Emeric Deutsch

a[0]=1; a[1]=3; a[n_]:= a[n] = 5a[n-1]-2a[n-2]; Table[ a[n], {n, 0, 30}]
LinearRecurrence[{5,-2},{1,3},30] (* Harvey P. Dale, Apr 08 2014 *)
CoefficientList[Series[(1-2x)/(1-5x+2x^2), {x, 0, 30}], x] (* Vincenzo Librandi, Apr 09 2014 *)

Vec((1-2*x)/(1-5*x+2*x^2)+O(x^30)) \\ Charles R Greathouse IV, Nov 20 2011

def A052984_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1-2*x)/(1-5*x+2*x^2) ).list()
A052984_list(30) # G. C. Greubel, Feb 10 2019

a(n) = A005824(2n).
G.f.: (1-2*x)/(1-5*x+2*x^2).
a(n) = Sum_{alpha=RootOf(1-5*z+2*z^2)} (1 + 6*alpha)*alpha^(-1-n)/17.
a(n) = [M^(n+1)]2,2, where M is the 3 X 3 matrix defined as follows: M = [2,1,2; 1,1,1; 2,1,2]. - _Simone Severini, Jun 12 2006
a(n-1) = Sum_{k=0..n} A147703(n,k)*(-1)^k*2^(n-k), n>1. - Philippe Deléham, Nov 29 2008
a(n) = (a(n-1)^2 + 2^n)/a(n-2). - Irene Sermon, Oct 29 2013
a(n) = A107839(n) - 2*A107839(n-1). - R. J. Mathar, Feb 27 2019
E.g.f.: exp(5*x/2)*(sqrt(17)*cosh(sqrt(17)*x/2) + sinh(sqrt(17)*x/2))/sqrt(17). - Stefano Spezia, Jun 17 2025

Edited by Robert G. Wilson v, Dec 29 2002

A078099 Array T(m,n) read by antidiagonals: T(m,n) = number of ways of 3-coloring an m X n grid (m >= 1, n >= 1).

Original entry on oeis.org

1, 2, 2, 4, 6, 4, 8, 18, 18, 8, 16, 54, 82, 54, 16, 32, 162, 374, 374, 162, 32, 64, 486, 1706, 2604, 1706, 486, 64, 128, 1458, 7782, 18150, 18150, 7782, 1458, 128, 256, 4374, 35498, 126534, 193662, 126534, 35498, 4374, 256, 512, 13122, 161926, 882180, 2068146, 2068146, 882180, 161926, 13122, 512

Offset: 1

N. J. A. Sloane, Dec 05 2002

We assume the top left point gets color 1 (or, in other words, take the total number of colorings and divide by 3). The rule for coloring is that horizontally or vertically adjacent points must have different colors. - N. J. A. Sloane, Feb 12 2013
Equals half the number of m X n binary matrices with no 2 X 2 circuit having the pattern 0011 in any orientation. - R. H. Hardin, Oct 06 2010
Also the number of Miura-ori foldings [Ginepro-Hull]. - N. J. A. Sloane, Aug 05 2015

			Array begins:
1       2       4       8       16      32      64      128     256     512 ...
2       6       18      54      162     486     1458    4374    13122 ...
4       18      82      374     1706    7782    35498   161926 ...
8       54      374     2604    18150   126534  882180 ...
16      162     1706    18150   193662 ...
32      486     7782    126534 ...
For the 1 X n case: the first point gets color 1, thereafter there are 2 choices for each color, so T(1,n) = 2^(n-1).
For the 2 X 2 case, the colorings are
12 12 12 13 13 13
21 23 31 31 32 21

Thomas C. Hull, Coloring Connections with Counting Mountain-Valley Assignments in (book) Origami^6: I. Mathematics, 2015, ed. Koryo Miura, Toshikazu Kawasaki, Tomohiro Tachi, Ryuhei Uehara, Robert J. Lang, Patsy Wang-Iverson, American Mathematical Soc., Dec 18, 2015, 368 pages
Michael S. Paterson (Warwick), personal communication.

Andrew Howroyd, Table of n, a(n) for n = 1..1128 (terms 1..120 from R. J. Mathar)
J. Ginepro, T. C. Hull, Counting Miura-ori Foldings, Journal of Integer Sequences, Vol. 17, 2014, #14.10.8
R. J. Mathar, Counting 2-way monotonic terrace forms..., vixra 1511.0225 (2015), Table T_{n x m}
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Vertex Coloring
Wikipedia, Graph Coloring

Cf. A207997, A020698, A078100. Main diagonal is A068253. Other diagonals produce A078101 and A078102.

Cf. A222444 (4 colorings), A222144 (5 colorings), A222281 (6 colorings), A222340 (7 colorings), A222462 (8 colorings).

with(linalg); t := transpose; M[1] := matrix(1,1,[1]); Z[1] := matrix(1,1,0); W[1] := evalm(M[1]+t(M[1])); v[1] := matrix(1,1,1);
for n from 2 to 6 do t1 := stackmatrix(M[n-1],Z[n-1]); t2 := stackmatrix(t(M[n-1]),M[n-1]); M[n] := t(stackmatrix(t(t1),t(t2))); Z[n] := matrix(2^(n-1),2^(n-1),0); W[n] := evalm(M[n]+t(M[n])); v[n] := matrix(1,2^(n-1),1); od:
T := proc(m,n) evalm( v[m] &* W[m]^(n-1) &* t(v[m]) ); end;

mmax = 10; M[1] = {{1}}; M[m_] := M[m] = {{M[m-1], Transpose[M[m-1]]}, {Array[0&, {2^(m-2), 2^(m-2)}], M[m-1]}} // ArrayFlatten; W[m_] := M[m] + Transpose[M[m]]; T[m_, 1] := 2^(m-1); T[1, n_] := 2^(n-1); T[m_, n_] := MatrixPower[W[m], n-1] // Flatten // Total; Table[T[m-n+1, n], {m, 1, mmax}, {n, 1, m}] // Flatten (* Jean-François Alcover, Feb 13 2016 *)

Let M[1] = [1], M[m+1] = the block matrix [ [ M[m], M[m]' ], [ 0, M[m] ] ], W[m] = M[m] + M[m]', then T(m, n) = sum of entries of W[m]^(n-1) (the prime denotes transpose).
T(3,n) = A052913(n). T(4,n) = 2*A078100(n).
T(n,m) = T(m,n). T(1,n)= A000079(n-1). T(2,n)=A025192(n). T(5,n) = 2*A207994(n). T(6,n) = 2*A207995(n). - R. J. Mathar, Nov 23 2015

More terms from Alois P. Heinz, Mar 23 2009

A052913 a(n+2) = 5a(n+1) - 2a(n), with a(0) = 1, a(1) = 4.

Original entry on oeis.org

1, 4, 18, 82, 374, 1706, 7782, 35498, 161926, 738634, 3369318, 15369322, 70107974, 319801226, 1458790182, 6654348458, 30354161926, 138462112714, 631602239718, 2881086973162, 13142230386374, 59948977985546, 273460429154982, 1247404189803818, 5690100090709126

Offset: 0

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

Main diagonal of the array: m(1,j)=3^(j-1), m(i,1)=1; m(i,j) = m(i-1,j) + m(i,j-1): 1 3 9 27 81 ... / 1 4 13 40 ... / 1 5 18 58 ... / 1 6 24 82 ... - Benoit Cloitre, Aug 05 2002
a(n) is also the number of 3 X n matrices of integers for which the upper-left hand corner is a 1, the rows and columns are weakly increasing, and two adjacent entries differ by at most 1. - Richard Stanley, Jun 06 2010
a(n) is the number of compositions of n when there are 4 types of 1 and 2 types of other natural numbers. - Milan Janjic, Aug 13 2010
If a Stern's sequence based enumeration system of positive irreducible fractions is considered (for example, A007305/A047679, or A162909/A162910, or A071766/A229742, or A245325/A245326, ...), and if it is organized by blocks or levels (n) with 2^n terms (n>=0), and the products numerator*denominator, term by term, are summed at each level n, then the resulting sequence of integers is a(n). - Yosu Yurramendi, May 23 2015
Number of 1’s in the substitution system {0 -> 110, 1 -> 11110} at step n from initial string "1" (1 -> 11110 -> 11110111101111011110110 -> ...) . - Ilya Gutkovskiy, Apr 10 2017

G. C. Greubel, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 894
J.-C. Novelli, J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
Index entries for linear recurrences with constant coefficients, signature (5,-2).

Cf. A007482 (inverse binomial transform).

a:=[1,4];; for n in [3..30] do a[n]:=5*a[n-1]-2*a[n-2]; od; a; # G. C. Greubel, Oct 16 2019

I:=[1,4]; [n le 2 select I[n] else 5*Self(n-1)-2*Self(n-2): n in [1..35]]; // Vincenzo Librandi, May 24 2015

R:=PowerSeriesRing(Integers(), 25); Coefficients(R!((1-x)/(1-5*x+2*x^2))); // Marius A. Burtea, Oct 16 2019

spec := [S,{S=Sequence(Union(Prod(Sequence(Z),Union(Z,Z)),Z,Z))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);
seq(coeff(series((1-x)/(1-5*x+2*x^2), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 16 2019

Transpose[NestList[{Last[#],5Last[#]-2First[#]}&, {1,4},20]][[1]] (* Harvey P. Dale, Mar 12 2011 *)
LinearRecurrence[{5, -2}, {1, 4}, 25] (* Jean-François Alcover, Jan 08 2019 *)

Vec((1-x)/(1-5*x+2*x^2) + O(x^30)) \\ Michel Marcus, Mar 05 2015

def A052913_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-x)/(1-5*x+2*x^2)).list()
A052913_list(30) # G. C. Greubel, Oct 16 2019

G.f.: (1-x)/(1-5*x+2*x^2).
a(n) = Sum_{alpha=RootOf(1 - 5*z + 2*z^2)} (1/17)*(3+alpha)*alpha^(-1-n).
a(n) = ((17+3*sqrt(17))/34)*((5+sqrt(17))/2)^n + ((17-3*sqrt(17))/34)*((5-sqrt(17))/2)^n. - N. J. A. Sloane, Jun 03 2002
a(n) = A107839(n) - A107839(n-1). - R. J. Mathar, May 21 2015
a(n) = 2*A020698(n-1), n>1. - R. J. Mathar, Nov 23 2015
E.g.f.: (1/17)*exp(5*x/2)*(17*cosh(sqrt(17)*x/2) + 3*sqrt(17)*sinh(sqrt(17)*x/2)). - Stefano Spezia, Oct 16 2019
a(n) = 3*A107839(n-1) + (-1)^n*A152594(n) with A107839(-1) = 0. - Klaus Purath, Jul 29 2020

Typo in definition corrected by Bruno Berselli, Jun 07 2010

A355881 Table read by descending antidiagonals: T(k,n) (k >= 0, n>= 1) is number of ways to (k+2)-color a 3 X n grid ignoring the variations of two colors.

Original entry on oeis.org

1, 1, 2, 1, 9, 3, 1, 41, 49, 4, 1, 187, 801, 169, 5, 1, 853, 13095, 7141, 441, 6, 1, 3891, 214083, 301741, 38897, 961, 7, 1, 17749, 3499929, 12749989, 3430789, 153921, 1849, 8, 1, 80963, 57218481, 538747549, 302602093, 24653151, 488401, 3249, 9

Offset: 0

Gerhard Kirchner, Jul 24 2022

With variations, the number of ways to color a 3 X 1 grid is (k+2)*(k+1)^2. The number of variations of two colors is (k+2)*(k+1). Therefore, T(k,1) = k+1. Only for k=1, the number of variations of two colors equals the number of permutations of all colors, see A020698.
 T(0,n) = A000012(n) = constant 1
T(1,n) = A020698(n-1)
T(2,n) = A355882(n)
T(3,n) = A355883(n)

			Table begins:
k\n_1____2______3_________4___________5_____________6________________7
0:  1    1      1         1           1             1                1
1:  2    9     41       187         853          3891            17749
2:  3   49    801     13095      214083       3499929         57218481
3:  4  169   7141    301741    12749989     538747549      22764640981
4:  5  441  38897   3430789   302602093   26690078241    2354115497017
5:  6  961 153921  24653151  3948635061  632443246191  101296892084301
6:  7 1849 488401 129007867 34076567743 9001098120361 2377580042199049

Gerhard Kirchner, Derivation of the recurrence

Cf. A000012, A020698, A355882, A355883.

T(k,n) = k*(k^2 + k + 3) * T(k,n-1) - (k^4 + k^3 + k^2-1) * T(k,n-2)
with T(k,1) = k+1, T(k,2) = (k^2+k+1)^2.
G.f.: x*(k + 1 - (k^2 + k - 1)*x) / (1 - k*(k^2 + k + 3)*x + (k^4 + k^3 + k^2 - 1)*x^2).

cp's OEIS Frontend

A107839 a(n) = 5*a(n-1) - 2*a(n-2); a(0)=1, a(1)=5.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A207997 T(n,k) = number of n X k 0..2 arrays with new values 0..2 introduced in row major order and no element equal to any horizontal or vertical neighbor (colorings ignoring permutations of colors).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A052984 a(n) = 5*a(n-1) - 2*a(n-2) for n>1, with a(0) = 1, a(1) = 3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A078099 Array T(m,n) read by antidiagonals: T(m,n) = number of ways of 3-coloring an m X n grid (m >= 1, n >= 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A052913 a(n+2) = 5*a(n+1) - 2*a(n), with a(0) = 1, a(1) = 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A355881 Table read by descending antidiagonals: T(k,n) (k >= 0, n>= 1) is number of ways to (k+2)-color a 3 X n grid ignoring the variations of two colors.

Views

Author

Keywords

Comments

Examples

A107839 a(n) = 5a(n-1) - 2a(n-2); a(0)=1, a(1)=5.

A052984 a(n) = 5a(n-1) - 2a(n-2) for n>1, with a(0) = 1, a(1) = 3.

A052913 a(n+2) = 5a(n+1) - 2a(n), with a(0) = 1, a(1) = 4.