Displaying 1-10 of 10 results found.
page
1
Length of the longest induced cycle in the n X n grid graph.
+10
8
0, 4, 8, 12, 16, 20, 32, 40, 50, 62, 76, 90, 104, 120, 140, 160, 180
LINKS
Eric Weisstein's World of Mathematics, Grid Graph.
EXAMPLE
For 2 <= n <= 6, a longest induced cycle is the one going around the border of the grid, so a(n) = 4*(n-1).
Longest induced cycles for 6 <= n <= 8:
X X X X X X X X X X X X X X X X X X X X X
X . . . . X X . . . . . X X . . . . . . X
X . . . . X X . X X X . X X . X X X . X X
X . . . . X X . X . X . X X . X . X . X .
X . . . . X X . X . X . X X . X . X . X X
X X X X X X X . X . X . X X . X . X . . X
X X X . X X X X . X . X . . X
X X X . X X X X
Number of snake-like polyominoes with the maximum possible number of unit squares in an n X n square.
+10
6
1, 4, 8, 84, 56, 136, 52, 216, 16, 1504, 2352, 1152, 1344, 123216, 82432, 11008, 308992
COMMENTS
The maximum possible number of unit squares is given by A331968(n).
Equivalently, a(n) is the number of maximum length paths without chords in the n X n grid graph. A path without chords is an induced subgraph that is a path.
For n > 1, a(n) is a multiple of 4 since a solution can have at most one symmetry considering rotations and reflections. - Andrew Howroyd, Feb 04 2020
EXAMPLE
For n = 4 the number of snake-like polyominoes with 11 cells is 84.
EXTENSIONS
a(16)-a(17) from Yi Yang, Oct 03 2022
a(n) is the maximum length of a snake-like polyomino in an n X n square that starts and ends at opposite corners.
+10
5
1, 3, 5, 7, 17, 23, 31, 39, 51, 63, 75, 89, 105, 121, 139, 159
COMMENTS
Snake-like polyominoes have all cells with at most two neighbor cells, and have at least one cell that has only one neighbor cell, where neighbors are horizontal or vertical (not diagonal).
Lower bounds for a(10)-a(22) are 63, 75, 89, 105, 121, 139, 159, 179, 201, 225, 249, 275, 303. Is it true that a(n) = round((2*n*n-4*n+28)/3) for n >= 9?
EXAMPLE
Longest snakes for 5 <= n <= 8:
X X X X X X X X X X X X X X . X X X X . X X X X X X
. . . . X . . . . . X . . X . X . X X . X . . . . X
X X X X X X X X X X X X X X . X . X X . X X X X . X
X . . . . X . . . . . X . . X X . X X X . . . X . X
X X X X X X . X X X X X . . X . X X . X . X X X . X
X X X . . X X . . X . X . X X . X . . X X
X X X X . X X X . . X . . X .
X X X X . . X X
Array read by antidiagonals: T(m,n) is the number of vertices in the longest induced path in the grid graph P_m X P_n.
+10
5
1, 2, 2, 3, 3, 3, 4, 5, 5, 4, 5, 6, 7, 6, 5, 6, 8, 9, 9, 8, 6, 7, 9, 11, 11, 11, 9, 7, 8, 11, 14, 14, 14, 14, 11, 8, 9, 12, 16, 17, 17, 17, 16, 12, 9, 10, 14, 18, 20, 21, 21, 20, 18, 14, 10, 11, 15, 20, 22, 24, 24, 24, 22, 20, 15, 11, 12, 17, 22, 25, 27, 29, 29, 27, 25, 22, 17, 12
COMMENTS
Equivalently, T(m,n) is the maximum number of unit squares of a snake-like polyomino in an m X n rectangle.
LINKS
Eric Weisstein's World of Mathematics, Grid Graph.
EXAMPLE
Array begins:
==============================================
m\n| 1 2 3 4 5 6 7 8 9 10 11 12 ...
-----+----------------------------------------
1 | 1 2 3 4 5 6 7 8 9 10 11 12 ...
2 | 2 3 5 6 8 9 11 12 14 15 17 18 ...
3 | 3 5 7 9 11 14 16 18 20 22 24 26 ...
4 | 4 6 9 11 14 17 20 22 25 28 30 33 ...
5 | 5 8 11 14 17 21 24 27 30 34 37 40 ...
6 | 6 9 14 17 21 24 29 32 36 40 44 47 ...
7 | 7 11 16 20 24 29 33 38 42 46 50 55 ...
8 | 8 12 18 22 27 32 38 42 48 52 57 62 ...
9 | 9 14 20 25 30 36 42 48 53 58 64 70 ...
10 | 10 15 22 28 34 40 46 52 58 64 71 77 ...
11 | 11 17 24 30 37 44 50 57 64 71 77 86 ...
12 | 12 18 26 33 40 47 55 62 70 77 86 92 ...
...
Number of non-isomorphic free unrooted snake-shaped polyominoes of maximum length on a quadratic board of n X n squares.
+10
3
1, 1, 2, 12, 8, 17, 8, 27, 3, 188
COMMENTS
Polyominoes only differing by any combination of translation, rotation and reflection are counted only once.
EXAMPLE
. X O . . X O O . X O O X . X O X . X . X . X O
X . O O X . . O X . . O O . . O O . O O O . . O
O O . O O . . O O . O O O . . O O . . O O . O O
. O O O O O O O O O O . O O O O O O O O O O O .
.
X . X O X . X . X . X O . X O . . O O O . O O O
O . . O O . O O O O . O X . O O . X . O . X . O
O O . O O O . O . O . O O . . O X . . O X . O O
. O O O . O O O . O O O O O O O O O O O O O O .
.
a(5) = 8 (L = 17)
O O O O X O O O O O O O O O O X . O O X
O . . . . O . . . O O . . . O O . O . .
O O O O O O O . O O O O X . O O . O O O
. . . . O . O . O . . . . . O O . . . O
X O O O O X O . O X X O O O O O O O O O
.
O O O O . O O O O O X . O O X O O O O .
O . . O O O . . . O O . O . . O . . O O
O O X . O O O X . O O . O O O O O X . O
. . . . O . . . O O O O . . O . . . O O
X O O O O X O O O . . O O O O X O O O .
CROSSREFS
Cf. A331968 (maximum length), A331986 (counts including isomorphisms), A332921 (subset of symmetric snakes).
Number of symmetric non-isomorphic free unrooted snake-shaped polyominoes of maximum length on a quadratic board of n X n squares.
+10
3
1, 1, 2, 3, 2, 0, 3, 0, 2, 0
COMMENTS
Polyominoes only differing by any combination of translation, rotation and reflection are counted only once.
EXAMPLE
X
.
a(2) = 1 (L = 3):
X O
. X
.
a(3) = 2 (L = 7):
X O O . X O
. . O X . O
X O O O O O
.
a(4) = 3 (L = 11)
. X O . . X O O . X O O
X . O O X . . O X . . O
O O . O O . . O O . O O
. O O O O O O O O O O .
.
a(5) = 2 (L = 17)
O O O O X O O O O O
O . . . . O . . . O
O O O O O O O . O O
. . . . O . O . O .
X O O O O X O . O X
.
a(7) = 3 (L = 33)
O O O . O O O O O X . O O O O O O . O O O
O . O . O . O O . . O O . O O . O O O . O
O . O O O . O O O . O . O O O O . . . O O
O O . . . O O . O . O . O . . O O . O O .
. O O . O O . O O . O . O O X . O . O . x
X . O . O . X O . O O . . O O . O . O . O
O O O . O O O O O O . X O O O O O . O O O
.
a(9) = 2 (L = 53)
. O X . O O O O O O O X . O O O O O
O O . O O . . . O O . . O O . . . O
O . O O . O O O O O . O O . O O O O
O . O . O O . . . O . O . O O . . .
O O O . O . O O O O O O . O . O O O
. . . O O . O . O . . . O O . O . O
O O O O . O O . O O O O O . O O . O
O . . . O O . O O O . . . O O . . O
O O O O O . X O . O O O O O . X O O
.
Number of induced paths in the n X n grid graph.
+10
3
0, 8, 94, 1004, 14864, 334536, 11546874, 629381852, 56094263348, 8343512638896, 2074276200162230, 853966325494701152, 578432462293854136504, 646135466408339553958096, 1200595044818176185884236342
COMMENTS
Paths of length zero are not counted here.
Equivalently, a(n) is the number of snake-like polyominoes in an n X n square. Rotations, reflections and translations are counted separately.
EXAMPLE
The a(2) = 8 induced paths are:
O O O . . . . O O O O . . O O O
. . O . O O . O O . O O O O . O
Maximum number of nodes in an induced path (or chordless path or snake path) in the n X n torus grid graph.
+10
2
COMMENTS
It is somewhat unclear how a(n) should be defined for n <= 2. If the 1 X 1 and 2 X 2 torus grid graphs are considered to have loops and multiple edges, respectively, we have a(1) = 0 and a(2) = 1 (unless loops and multiple edges are allowed in a path), otherwise a(1) = 1 and a(2) = 3.
FORMULA
a(n) ~ 2*n^2/3.
a(n) <= (2*n^2-1)/3.
EXAMPLE
Longest induced paths (with one end in the lower left corner) for 3 <= n <= 7:
. X X . X X . . X X . X . X X . X . . . . X . X X
X X . X X . . . X . X X X X . X X . X X . X X . X
X . . X . X . X X . X . X . X X . X . X X . X X .
X . X . X . X X . . X X . X X X . X X . X X
X . X . . X X . . X . X X . X . . .
X . X . X . . X . X . X X
X X . X . X .
Maximum number of vertices in an induced tree in the n X n grid graph.
+10
2
1, 3, 7, 12, 19, 26, 36, 46, 59, 72, 87, 102, 120, 138, 159
LINKS
Eric Weisstein's World of Mathematics, Grid Graph.
EXAMPLE
a(4) = 12:
O O O O
O O
O O O
O O O
Largest number of nodes of an induced path in the n X n knight graph.
+10
1
1, 1, 7, 9, 15, 21, 24, 34
REFERENCES
Thomas Dawson, Échecs Féeriques, L'Échiquier, volume 2, issue 2, 1930; issue 3, 1931.
Donald E. Knuth, The Art of Computer Programming, Volume 4B, Combinatorial Algorithms, Part 2, Addison-Wesley, 2023. See exercise 7.2.2.1-172 and its solution.
EXAMPLE
Longest paths for 3 <= n <= 7:
X . X . . . . . X . X . . X X X . . X . X X X . .
X . X X . X X X X . X X X . . X X X X . X . . X .
X X X . X X . X . . . X X . . . X X . X X . . X .
X X X X X X . X X X X . . . X . . X . . X X
. X X X . . X X . X X . . . . . . X
. X X X X . . X X X X X X
X X . X X . .
Search completed in 0.007 seconds
|