A138979 -id:A138979 - cp's OEIS frontend

A138977 Number of 2 X n matrices containing a 1 in the top left entry, all entries are integer values and adjacent entries differ by at most 1.

3, 19, 121, 771, 4913, 31307, 199497, 1271251, 8100769, 51620379, 328939577, 2096095523, 13356910353, 85113990379, 542370291241, 3456136077171, 22023471375233, 140339755317947, 894284401724697, 5698631790801091, 36313284928708849, 231398467337757579

Offset: 1

Wayne VanWeerthuizen, Apr 05 2008

Horizontally or vertically adjacent entries can differ by at most 1. Diagonally adjacent entries thus differ by at most 2.

			a(1) = 3:
|1|1|1|
|0|1|2|
a(2) = 19:
|10|11|12| |10|11|12| |10|11|12|
|0*|0*|01| |1*|1*|1*| |21|2*|2*|
(3) (2)(1) (2) (3)(2) (1) (2)(3), total 19.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Michael Han, Sycamore Herlihy, Kirsti Kuenzel, Daniel Martin, and Rachel Schmidt, The number of independent sets in bipartite graphs and benzenoids, arXiv:2311.15334 [math.CO], 2023. See p. 13.
Index entries for linear recurrences with constant coefficients, signature (7,-4).

Cf. A138978, A138979.

a:= LREtools[REtoproc](a(n+3)=7*a(n+2)-4*a(n+1),a(n),{a(0)=0,a(1)=3,a(2)=19}):
seq(a(n),n=1..100); # Robert Israel, Sep 02 2014

LinearRecurrence[{7, -4}, {3, 19}, 22] (* Jean-François Alcover, Apr 30 2019 *)

Vec(x*(3 - 2*x) / (1 - 7*x + 4*x^2) + O(x^30)) \\ Colin Barker, Jan 31 2018

a(n)=b(n)+c(n), where b(1)=2, c(1)=1, b(n+1)=4*b(n)+4*c(n), c(n+1)=2*b(n)+3*c(n).
G.f.: x*(3 - 2*x) / (1 - 7*x + 4*x^2). - N. J. A. Sloane, Apr 06 2008
a(n+2) = 7*a(n+1) - 4*a(n) for n >= 2. - Robert Israel, Sep 02 2014
a(n) = (2^(-2-n)*((7-sqrt(33))^n*(-5+sqrt(33)) + (5+sqrt(33))*(7+sqrt(33))^n)) / sqrt(33). - Colin Barker, Jan 31 2018

A209517 T(n,k) = Number of (n+1) X (k+1) 0..2 arrays with the number of clockwise edge increases in every 2 X 2 subblock equal to the number of counterclockwise edge increases.

Original entry on oeis.org

57, 363, 363, 2313, 4995, 2313, 14739, 68937, 68937, 14739, 93921, 951777, 2071311, 951777, 93921, 598491, 13141335, 62340543, 62340543, 13141335, 598491, 3813753, 181445643, 1876947141, 4099186545, 1876947141, 181445643, 3813753, 24302307

Offset: 1

R. H. Hardin, Mar 09 2012

Table starts
.......57.........363...........2313.............14739.................93921
......363........4995..........68937............951777..............13141335
.....2313.......68937........2071311..........62340543............1876947141
....14739......951777.......62340543........4099186545..........269845393359
....93921....13141335.....1876947141......269845393359........38883961392081
...598491...181445643....56515446141....17769569448759......5607670578249789
..3813753..2505266673..1701725703867..1170258116647953....808953988260058047
.24302307.34590865185.51240520677831.77072446894479573.116711118063701004591

			Some solutions for n=4, k=3:
..0..0..2..1....0..1..0..2....1..2..2..1....2..2..1..2....2..1..0..2
..2..0..2..2....2..0..0..2....2..0..2..1....2..2..1..1....1..1..1..0
..0..2..2..0....2..0..1..0....2..2..1..0....0..2..2..1....1..1..2..1
..2..2..0..1....2..2..0..1....1..2..1..1....0..2..0..2....1..1..1..1
..2..1..2..0....1..2..2..0....1..2..1..2....2..2..0..0....2..2..1..2

R. H. Hardin, Table of n, a(n) for n = 1..220

Column 1 is 3*A138977(n+1).
Column 2 is 3*A138978(n+1).
Column 3 is 3*A138979(n+1).

A138978 Number of 3 X n matrices containing a 1 in the top left entry, all entries are integer values and adjacent entries differ by at most 1.

Original entry on oeis.org

9, 121, 1665, 22979, 317259, 4380445, 60481881, 835088891, 11530288395, 159201677509, 2198138788809, 30350271502115, 419054058355851, 5785987905016141, 79888633386248025, 1103043049708026539, 15230001039404897259, 210284568423392013685, 2903453493049800669321

Offset: 1

Wayne VanWeerthuizen, Apr 05 2008

Horizontally or vertically adjacent entries can differ by at most 1. Diagonally adjacent entries thus differ by at most 2.

Alois P. Heinz, Table of n, a(n) for n = 1..800
Index entries for linear recurrences with constant coefficients, signature (16,-31,10).

Cf. A138977, A138979.

a:= n-> (Matrix([1,6,2]). Matrix([[3,12,2], [2,10,2], [1,6,3]])^(n-1) .Matrix([[1],[1],[1]]))[1,1]: seq(a(n), n=1..20); # Alois P. Heinz, Aug 28 2008

LinearRecurrence[{16, -31, 10}, {9, 121, 1665}, 25] (* Paolo Xausa, Mar 17 2024 *)

a(n) = b(n)+c(n)+d(n), where b(1)=1, c(1)=6, d(1)=2, with b(n+1)=3*b(n)+2*c(n)+1*d(n), c(n+1)=12*b(n)+10*c(n)+6*d(n), d(n+1)=2*b(n)+2*c(n)+3*d(n).

G.f.: -x*(8*x^2-23*x+9) / (10*x^3-31*x^2+16*x-1). - Colin Barker, Dec 03 2012

More terms from Alois P. Heinz, Aug 28 2008

A222169 T(n,k)=Number of nXk 0..4 arrays with entries increasing mod 5 by 0, 1 or 2 rightwards and downwards, starting with upper left zero.

Original entry on oeis.org

1, 3, 3, 9, 19, 9, 27, 121, 121, 27, 81, 771, 1665, 771, 81, 243, 4913, 22979, 22979, 4913, 243, 729, 31307, 317259, 690437, 317259, 31307, 729, 2187, 199497, 4380445, 20780181, 20780181, 4380445, 199497, 2187, 6561, 1271251, 60481881, 625649047

Offset: 1

R. H. Hardin Feb 10 2013

Table starts
......1..........3..............9.................27.....................81
......3.........19............121................771...................4913
......9........121...........1665..............22979.................317259
.....27........771..........22979.............690437...............20780181
.....81.......4913.........317259...........20780181.............1366395515
....243......31307........4380445..........625649047............89948464453
....729.....199497.......60481881........18838482047..........5923189816253
...2187....1271251......835088891.......567241901289........390086038882651
...6561....8100769....11530288395.....17080173559277......25690815631493191
..19683...51620379...159201677509....514300085627023....1691995329032459285
..59049..328939577..2198138788809..15486061794514775..111434983000652039093
.177147.2096095523.30350271502115.466299978310573033.7339124863989795685471

			Some solutions for n=3 k=4
..0..1..3..3....0..2..3..3....0..1..2..4....0..1..3..4....0..0..0..1
..2..3..0..0....0..2..4..4....1..2..3..4....1..3..4..1....0..2..2..2
..4..0..0..0....2..4..4..0....1..2..3..4....3..4..4..1....0..2..2..3

R. H. Hardin, Table of n, a(n) for n = 1..180

Diagonal is A068748
Column 1 is A000244(n-1)
Column 2 is A138977
Column 3 is A138978
Column 4 is A138979

Empirical for column k:
k=1: a(n) = 3*a(n-1)
k=2: a(n) = 7*a(n-1) -4*a(n-2)
k=3: a(n) = 16*a(n-1) -31*a(n-2) +10*a(n-3)
k=4: [order 10]
k=5: [order 25]
k=6: [order 70]

cp's OEIS Frontend

A138977 Number of 2 X n matrices containing a 1 in the top left entry, all entries are integer values and adjacent entries differ by at most 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A209517 T(n,k) = Number of (n+1) X (k+1) 0..2 arrays with the number of clockwise edge increases in every 2 X 2 subblock equal to the number of counterclockwise edge increases.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A138978 Number of 3 X n matrices containing a 1 in the top left entry, all entries are integer values and adjacent entries differ by at most 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A222169 T(n,k)=Number of nXk 0..4 arrays with entries increasing mod 5 by 0, 1 or 2 rightwards and downwards, starting with upper left zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula