Displaying 1-10 of 15 results found.
Number of 2 X n checkerboards (with at least one red square) in which the set of red squares is edge connected.
+10
21
0, 3, 13, 40, 108, 275, 681, 1664, 4040, 9779, 23637, 57096, 137876, 332899, 803729, 1940416, 4684624, 11309731, 27304157, 65918120, 159140476, 384199155, 927538873, 2239276992, 5406092952, 13051462995, 31509019045, 76069501192, 183648021540, 443365544387
COMMENTS
In other words, the number of connected (non-null) induced subgraphs in the n-ladder graph P_2 X P_n. - Eric W. Weisstein, May 02 2017 Also, the number of cycles in the grid graph P_3 X P_{n+1}. - Andrew Howroyd, Jun 12 2017
FORMULA
a(n) = 2*a(n-1) + a(n-2) + 4*n - 1.
a(n) = 3*a(n-1) - a(n-2) - a(n-3) + 4;
a(n) = 4*a(n-1) - 4*a(n-2) + a(n-4). (End)
Empirical observations (from Superseeker):
(1) if b(n) = a(n) + n then {b(n)} is A048777; (2) if b(n) = a(n+3) - 3*a(n+2) - 3*a(n+1) + a(n) then {b(n)} is A052542; (3) if b(n) = a(n+2) - 2*a(n+1) + a(n) then {b(n)} is A001333. E.g.f.: (1/2)*exp(x)*(-7-4*x+7*cosh(sqrt(2)*x)+5*sqrt(2)*sinh(sqrt(2)*x)). - Stefano Spezia, Aug 25 2019
MATHEMATICA
Join[{0}, LinearRecurrence[{4, -4, 0, 1}, {3, 13, 40, 108}, 20]] (* Eric W. Weisstein, May 02 2017 *) (* adapted by Vincenzo Librandi, May 09 2017 *) Table[(LucasL[n + 3, 2] - 8 n - 14)/4, {n, 0, 20}] (* Eric W. Weisstein, May 02 2017 *)
PROG
(Magma) I:=[0, 3, 13, 40]; [n le 4 select I[n] else 4*Self(n-1) - 4*Self(n-2) + Self(n-4):n in [1..30]]; // Marius A. Burtea, Aug 25 2019
CROSSREFS
Other sequences counting connected induced subgraphs: A020873, A059525, A286139, A286182, A286183, A286184, A286185, A286186, A286187, A286188, A286189, A286191, A285765, A285934, A286304.
Number of cycles in an n X n grid.
+10
18
0, 1, 13, 213, 9349, 1222363, 487150371, 603841648931, 2318527339461265, 27359264067916806101, 988808811046283595068099, 109331355810135629946698361371, 36954917962039884953387868334644457
COMMENTS
Or, number of simply connected and rookwise connected regions of an (n-1) X (n-1) grid.
REFERENCES
D. E. Knuth, The Art of Computer Programming, Volume 4A, Section 7.1.4.
LINKS
Fawaz Alazemi, Arash Azizimazreah, Bella Bose, and Lizhong Chen, Routerless Networks-on-Chip, U.S. Patent Application No. 15,445,736, 2017. H. Iwashita, Y. Nakazawa, J. Kawahara, T. Uno, and S. Minato, Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions, TCS Technical Report, TCS -TR-A-13-64, Division of Computer Science, Hokkaido University, Report Series A, April 26 2013. Kimberly Villalobos, Vilim Štih, Amineh Ahmadinejad, Shobhita Sundaram, Jamell Dozier, Andrew Francl, Frederico Azevedo, Tomotake Sasaki, and Xavier Boix, Do Neural Networks for Segmentation Understand Insideness?, MIT Center for Brains, Minds + Machines, CBMM Memo (2020) No. 105.
MATHEMATICA
Table[Length[FindCycle[GridGraph[{n, n}], Infinity, All]], {n, 6}] (* Eric W. Weisstein, Mar 07 2023 *)
PROG
(Python)
# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
if n == 0: return 0
universe = tl.grid(n, n)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles()
return cycles.len()
CROSSREFS
Corner-to-corner paths in this grid are enumerated in A007764.
EXTENSIONS
a(9) calculated using the ZDD technique described in Knuth's The Art of Computer Programming, Exercises 7.1.4, by Ashutosh Mehra, Dec 19 2008 a(10)-a(19) calculated using a transfer matrix method by Artem M. Karavaev, Jun 03 2009, Oct 20 2009
Array read by antidiagonals: T(m,n) = number of (undirected) paths in the grid graph P_m X P_n.
+10
12
0, 1, 1, 3, 12, 3, 6, 49, 49, 6, 10, 146, 322, 146, 10, 15, 373, 1618, 1618, 373, 15, 21, 872, 7119, 14248, 7119, 872, 21, 28, 1929, 28917, 111030, 111030, 28917, 1929, 28, 36, 4118, 111360, 801756, 1530196, 801756, 111360, 4118, 36
COMMENTS
Paths of length zero are not counted here.
EXAMPLE
Table starts:
=================================================================
m\n| 1 2 3 4 5 6 7
---|-------------------------------------------------------------
1 | 0 1 3 6 10 15 21 ...
2 | 1 12 49 146 373 872 1929 ...
3 | 3 49 322 1618 7119 28917 111360 ...
4 | 6 146 1618 14248 111030 801756 5493524 ...
5 | 10 373 7119 111030 1530196 19506257 235936139 ...
6 | 15 872 28917 801756 19506257 436619868 9260866349 ...
7 | 21 1929 111360 5493524 235936139 9260866349 343715004510 ...
...
Array read by antidiagonals: T(m,n) is the number of (undirected) Hamiltonian paths in the m X n grid graph.
+10
12
1, 1, 1, 1, 4, 1, 1, 8, 8, 1, 1, 14, 20, 14, 1, 1, 22, 62, 62, 22, 1, 1, 32, 132, 276, 132, 32, 1, 1, 44, 336, 1006, 1006, 336, 44, 1, 1, 58, 688, 3610, 4324, 3610, 688, 58, 1, 1, 74, 1578, 12010, 26996, 26996, 12010, 1578, 74, 1, 1, 92, 3190, 38984, 109722, 229348, 109722, 38984, 3190, 92, 1
EXAMPLE
Array begins:
================================================
m\n | 1 2 3 4 5 6 7
----+-------------------------------------------
1 | 1 1 1 1 1 1 1 ...
2 | 1 4 8 14 22 32 44 ...
3 | 1 8 20 62 132 336 688 ...
4 | 1 14 62 276 1006 3610 12010 ...
5 | 1 22 132 1006 4324 26996 109722 ...
6 | 1 32 336 3610 26996 229348 1620034 ...
7 | 1 44 688 12010 109722 1620034 13535280 ...
...
Array read by antidiagonals: T(m,n) is the number of induced cycles in the grid graph P_m X P_n.
+10
9
1, 2, 2, 3, 5, 3, 4, 9, 9, 4, 5, 14, 24, 14, 5, 6, 20, 58, 58, 20, 6, 7, 27, 125, 229, 125, 27, 7, 8, 35, 251, 749, 749, 251, 35, 8, 9, 44, 490, 2180, 3436, 2180, 490, 44, 9, 10, 54, 948, 6188, 13350, 13350, 6188, 948, 54, 10, 11, 65, 1823, 17912, 50203, 65772, 50203, 17912, 1823, 65, 11
COMMENTS
Induced cycles are sometimes called chordless cycles (but some definitions require chordless cycles to have a cycle length of at least 4).
LINKS
Eric Weisstein's World of Mathematics, Grid Graph.
EXAMPLE
Array begins:
========================================================
m\n| 2 3 4 5 6 7 8 9 ...
---+----------------------------------------------------
2 | 1 2 3 4 5 6 7 8 ...
3 | 2 5 9 14 20 27 35 44 ...
4 | 3 9 24 58 125 251 490 948 ...
5 | 4 14 58 229 749 2180 6188 17912 ...
6 | 5 20 125 749 3436 13350 50203 196918 ...
7 | 6 27 251 2180 13350 65772 308212 1535427 ...
8 | 7 35 490 6188 50203 308212 1743247 10614143 ...
9 | 8 44 948 17912 196918 1535427 10614143 78586742 ...
...
Square array T(n,k), n >= 2, k >= 2, read by antidiagonals, where T(n,k) is the number of (undirected) cycles on the n X k king graph.
+10
7
7, 30, 30, 85, 348, 85, 204, 3459, 3459, 204, 451, 33145, 136597, 33145, 451, 954, 316164, 4847163, 4847163, 316164, 954, 1969, 3013590, 171903334, 545217435, 171903334, 3013590, 1969, 4008, 28722567, 6109759868, 61575093671, 61575093671, 6109759868, 28722567, 4008
EXAMPLE
Square array T(n,k) begins:
7, 30, 85, 204, 451, ...
30, 348, 3459, 33145, 316164, ...
85, 3459, 136597, 4847163, 171903334, ...
204, 33145, 4847163, 545217435, 61575093671, ...
451, 316164, 171903334, 61575093671, 21964731190911, ...
PROG
(Python)
# Using graphillion
from graphillion import GraphSet
def make_nXk_king_graph(n, k):
grids = []
for i in range(1, k + 1):
for j in range(1, n):
grids.append((i + (j - 1) * k, i + j * k))
if i < k:
grids.append((i + (j - 1) * k, i + j * k + 1))
if i > 1:
grids.append((i + (j - 1) * k, i + j * k - 1))
for i in range(1, k * n, k):
for j in range(1, k):
grids.append((i + j - 1, i + j))
return grids
universe = make_nXk_king_graph(n, k)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles()
return cycles.len()
print([ A339098(j + 2, i - j + 2) for i in range(9 - 1) for j in range(i + 1)])
Square array read by antidiagonals: T(m,n) = number of ways of drawing a simple loop on an m x n rectangular lattice of dots in such a way that it touches each edge.
+10
4
1, 1, 1, 1, 5, 1, 1, 15, 15, 1, 1, 39, 106, 39, 1, 1, 97, 582, 582, 97, 1, 1, 237, 2952, 6074, 2952, 237, 1, 1, 575, 14488, 56778, 56778, 14488, 575, 1, 1, 1391, 69982, 510600, 943340, 510600, 69982, 1391, 1, 1, 3361, 335356, 4502836, 15009212, 15009212
COMMENTS
This sequence is to be read as a table:
1, 1, 1, 1, 1, ...
1, 5, 15, 39, ...
1, 15, 106, ...
1, 39, ...
1, ...
...
This represents the number of simple, closed loops that can be formed on an m x n lattice of dots in such a way that it touches each edge.
This sequence is related to A231829, called b(i,j) by a(i,j) = b(i,j) - 2 * b(i,j-1) + b(i,j-2) - 2 * b(i-1,j) + 4 * b(i-1,j-1) - 2 * b(j-1,j-2) + b(i-2,j) - 2 * b(i-2,j-1) + b(i-2,j-2). Equivalently, the number of fixed polyominoes without holes that have a width of m and height of n. - Andrew Howroyd, Oct 04 2017
FORMULA
T(m, n) = U(m, n) - 2*U(m, n-1) + U(m, n-2) where U(m, n) = V(m, n) - 2*V(m-1, n) + V(m-2, n) and V(m, n) = A231829(m, n). - Andrew Howroyd, Oct 04 2017
EXAMPLE
Array begins:
==============================================================
m\n| 1 2 3 4 5 6 7
---|----------------------------------------------------------
1 | 1 1 1 1 1 1 1...
2 | 1 5 15 39 97 237 575...
3 | 1 15 106 582 2952 14488 69982...
4 | 1 39 582 6074 56778 510600 4502836...
5 | 1 97 2952 56778 943340 15009212 234411981...
6 | 1 237 14488 510600 15009212 419355340 11509163051...
7 | 1 575 69982 4502836 234411981 11509163051 554485727288...
a(3,2) is 15, thus:
1) 2) 3) 4) 5)
+-+-+-+ +-+-+-+ + +-+-+ +-+-+-+ +-+-+-+
| | | | | | | | | |
+ +-+-+ +-+ +-+ +-+ +-+ + + +-+ +-+-+ +
| | | | | | | | | |
+-+ + + + +-+ + +-+-+ + +-+-+ + + + +-+
6) 7) 8) 9) 10)
+-+-+-+ +-+-+ + +-+-+-+ +-+ + + + +-+ +
| | | | | | | | | |
+ +-+ + +-+ +-+ +-+ + + + +-+-+ +-+ +-+
| | | | | | | | | | | |
+-+ +-+ + +-+-+ + +-+-+ +-+-+-+ +-+-+-+
11) 12) 13) 14) 15)
+-+-+ + + + +-+ +-+ +-+ + +-+-+ +-+-+-+
| | | | | | | | | | | |
+ +-+ +-+-+ + + +-+ + +-+ + + + + + +
| | | | | | | | | |
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
Number of cycles in the grid graph P_4 X P_{n+1}.
+10
3
6, 40, 213, 1049, 5034, 23984, 114069, 542295, 2577870, 12253948, 58249011, 276885683, 1316170990, 6256394122, 29739651711, 141366874247, 671984773580, 3194266961582, 15183887824311, 72176324719925, 343088799809408, 1630866146364842, 7752291502484181
FORMULA
Empirical: a(n) = 9*a(n-1)-27*a(n-2)+38*a(n-3)-29*a(n-4)+11*a(n-5)+a(n-6)-2*a(n-7) for n>7.
Empirical g.f.: x*(6 - 14*x + 15*x^2 - 16*x^3 - 2*x^4 + x^5) / ((1 - x)^2*(1 - 7*x + 12*x^2 - 7*x^3 + 3*x^4 + 2*x^5)). - Colin Barker, Jun 12 2017
Number of cycles in the grid graph P_5 X P_n.
+10
3
10, 108, 1049, 9349, 80626, 692194, 5948291, 51139577, 439673502, 3779989098, 32497334055, 279386435639, 2401945965628, 20650054358200, 177533025653767, 1526290165248783, 13121849649571820, 112811405309454694, 969864273118112913, 8338134834111643373, 71684765011673779732
COMMENTS
a(n+1) / a(n) tends to 8.597218255461742020947886618374491114891840151635008721734194641555448999... - Vaclav Kotesovec, Nov 24 2020
FORMULA
Empirical g.f.: -x^2*(10 - 42*x + 149*x^2 - 300*x^3 - 393*x^4 + 693*x^5 + 230*x^6 - 473*x^7 - 72*x^8 + 202*x^9 + 84*x^10) / ((1 - x)^2 * (-1 + 13*x - 45*x^2 + 66*x^3 - 17*x^4 - 209*x^5 + 151*x^6 + 140*x^7 - 112*x^8 - 48*x^9 + 50*x^10 + 28*x^11)). - Vaclav Kotesovec, Nov 24 2020
PROG
(Python)
# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A(n, k):
universe = tl.grid(n - 1, k - 1)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles()
return cycles.len()
return A(n, 5)
print([ A339117(n) for n in range(2, 15)])
Number of cycles in the grid graph P_6 X P_n.
+10
3
15, 275, 5034, 80626, 1222363, 18438929, 279285399, 4237530095, 64300829449, 975566486675, 14800469958185, 224540402345213, 3406558215857382, 51681816786790684, 784078741397570677, 11895467318139343215, 180469294422664219486, 2737947622842077799930
FORMULA
Empirical g.f.: -x^2 * (15 - 325*x + 3889*x^2 - 32204*x^3 + 166496*x^4 - 439661*x^5 + 117553*x^6 + 2506529*x^7 - 5691052*x^8 - 128310*x^9 + 16209330*x^10 - 15148184*x^11 - 17089827*x^12 + 28709449*x^13 + 11141815*x^14 - 27136640*x^15 - 13792528*x^16 + 20876587*x^17 + 15963209*x^18 - 11646759*x^19 - 10681356*x^20 + 3192142*x^21 + 3419602*x^22 - 252986*x^23 - 401310*x^24 - 43774*x^25 + 13852*x^26 + 2950*x^27 - 278*x^28 - 48*x^29 + 4*x^30) / ((-1 + x)^2 * (-1 + 38*x - 580*x^2 + 4945*x^3 - 26274*x^4 + 84913*x^5 - 122213*x^6 - 183068*x^7 + 1124479*x^8 - 1544617*x^9 - 1129508*x^10 + 5346947*x^11 - 3023145*x^12 - 6147688*x^13 + 6904233*x^14 + 3952819*x^15 - 5690282*x^16 - 4144167*x^17 + 3164355*x^18 + 4915006*x^19 - 1267655*x^20 - 3336331*x^21 + 82962*x^22 + 1051157*x^23 + 93428*x^24 - 119962*x^25 - 23089*x^26 + 2688*x^27 + 1368*x^28 - 34*x^29 - 30*x^30 + 2*x^31)). - Vaclav Kotesovec, Dec 09 2020
PROG
(Python)
# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A(n, k):
universe = tl.grid(n - 1, k - 1)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles()
return cycles.len()
return A(6, n)
print([ A339118(n) for n in range(2, 13)])
Search completed in 0.009 seconds
|