[go: up one dir, main page]

login
Search: a331968 -id:a331968
     Sort: relevance | references | number | modified | created      Format: long | short | data
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
OFFSET
1,2
LINKS
Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023.
Elijah Beregovsky, Illustration of initial terms.
Eric Weisstein's World of Mathematics, Grid Graph.
Wikipedia, Induced path.
FORMULA
a(n) <= A331968(n)+1.
a(n) = 2*n^2/3 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023
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
CROSSREFS
Main diagonal of A360915.
Cf. A000937, A297664, A331968, A357358, A360914 (number of longest induced cycles).
KEYWORD
nonn,more
AUTHOR
EXTENSIONS
a(9)-a(12) from Elijah Beregovsky, Nov 24 2022
a(13) from Elijah Beregovsky, Nov 25 2022
a(14)-a(17) from Andrew Howroyd, Feb 26 2023
STATUS
approved
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
OFFSET
1,2
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
LINKS
Eric Weisstein's World of Mathematics, Grid Graph
EXAMPLE
For n = 4 the number of snake-like polyominoes with 11 cells is 84.
CROSSREFS
Main diagonal of A360916.
Cf. A331968, A059525 (connected induced subgraphs), A099155.
Cf. A332920 (non-isomorphic snakes), A332921 (symmetric snakes).
KEYWORD
nonn,walk,hard,more
AUTHOR
Alain Goupil, Feb 03 2020
EXTENSIONS
a(15) from Andrew Howroyd, Feb 04 2020
a(16)-a(17) from Yi Yang, Oct 03 2022
STATUS
approved
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
OFFSET
1,2
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?
FORMULA
a(n) ~ 2*n^2/3. - Pontus von Brömssen, Sep 19 2022
a(n) <= A331968(n). - Pontus von Brömssen, Sep 21 2022
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
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Yi Yang, Sep 18 2022
EXTENSIONS
a(1)-a(9) confirmed by Pontus von Brömssen, Sep 21 2022. - N. J. A. Sloane, Sep 30 2022
a(10)-a(13) confirmed by Elijah Beregovsky, Nov 27 2022
a(14)-a(16) from Andrew Howroyd, Feb 28 2023
STATUS
approved
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
OFFSET
1,2
COMMENTS
Equivalently, T(m,n) is the maximum number of unit squares of a snake-like polyomino in an m X n rectangle.
LINKS
Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023.
Eric Weisstein's World of Mathematics, Grid Graph.
FORMULA
T(m,n) = T(n,m).
T(m,n) = 2*m*n/3 + O(m+n) (Beluhov 2023, Proposition 3). - Pontus von Brömssen, May 08 2023
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 ...
...
CROSSREFS
Main diagonal is A331968.
Cf. A360199, A360915, A360916 (maximum induced paths), A360920.
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Feb 26 2023
STATUS
approved
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
OFFSET
1,3
COMMENTS
Polyominoes only differing by any combination of translation, rotation and reflection are counted only once.
EXAMPLE
a(4) = 12 (L = A331968(4) = 11):
A332921(4) = 3 symmetric snakes
. 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)
A332921(5) = 2 symmetric snakes
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).
KEYWORD
nonn,hard,more
AUTHOR
Hugo Pfoertner, Mar 05 2020
STATUS
approved
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
OFFSET
1,3
COMMENTS
Polyominoes only differing by any combination of translation, rotation and reflection are counted only once.
EXAMPLE
a(1) = 1 (L = A331968(1) = 1):
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
.
Example for a(9) corrected by Luke Murphy, Oct 14 2024
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Hugo Pfoertner, Mar 05 2020
STATUS
approved
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
OFFSET
1,2
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.
LINKS
Eric Weisstein's World of Mathematics, Grid Graph
Wikipedia, Induced path
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
CROSSREFS
Main diagonal of A360199.
Cf. A059525, A297664 (induced cycles), A331968, A331986 (of maximum length), A357516.
KEYWORD
nonn,more
AUTHOR
Andrew Howroyd, Jan 29 2023
STATUS
approved
Maximum number of nodes in an induced path (or chordless path or snake path) in the n X n torus grid graph.
+10
2
5, 8, 14, 21, 28, 39, 50
OFFSET
3,1
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.
a(n) >= A357358(n) - 1.
a(n) >= A331968(n-1).
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 .
CROSSREFS
KEYWORD
nonn,more
AUTHOR
STATUS
approved
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
OFFSET
1,2
LINKS
Eric Weisstein's World of Mathematics, Grid Graph.
FORMULA
a(n) >= A331968(n).
EXAMPLE
a(4) = 12:
O O O O
O O
O O O
O O O
CROSSREFS
Main diagonal of A360920.
Cf. A331968, A357357, A360919 (maximum induced trees).
KEYWORD
nonn,more
AUTHOR
Andrew Howroyd, Feb 26 2023
STATUS
approved
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
OFFSET
1,3
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.
LINKS
Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023.
Eric Weisstein's World of Mathematics, Knight Graph.
Wikipedia, Induced path
FORMULA
a(n) >= A165143(n) - 1 for n >= 3.
a(n) <= (4*(n^2+3*n-2)-1)/7 for n >= 4. - Elijah Beregovsky, Dec 22 2022
a(n) = n^2/2 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023
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 . .
CROSSREFS
KEYWORD
nonn,more
AUTHOR
STATUS
approved

Search completed in 0.007 seconds