|
|
A264041
|
|
a(n) is the maximum number of diagonals that can be placed in an n X n grid made up of 1 X 1 unit squares when diagonals are placed in the unit squares in such a way that no two diagonals may cross or intersect at an endpoint.
|
|
8
|
|
|
1, 3, 6, 10, 16, 21, 29, 36, 46, 55, 68, 78, 93, 105, 122, 136, 156, 171, 193, 210, 234, 253, 280, 300, 329, 351
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
In other words, largest number of nonintersecting vertex-disjoint diagonals / and \ that can be packed in an n X n grid.
/ and \ cannot be adjacent horizontally or vertically.
Two \ cannot be adjacent on a northwest-to-southeast diagonal, two / cannot be adjacent on a southwest-to-northeast diagonal.
We also extended this to m X n grids, and have some limited results.
a(n) is the size of a maximum independent set in a graph with vertices (x,y,z), x=1..n, y=1..n, z=1..2, with edges joining (x,y,z) to (x,y,3-z), (x+1,y,3-z), and (x,y+1,3-z), (x,y,1) to (x+1,y-1,1) and (x,y,2) to (x+1,y+1,2). - Robert Israel, Nov 01 2015
382 <= a(27) <= 383.
a(29) = 440.
For the number of optimal solutions see A264667. (End)
|
|
LINKS
|
|
|
FORMULA
|
Theorem: a(2*n) = n*(2n+1) (the even-indexed terms among the triangular numbers A000217). More generally, for the 2k X m case, the optimal solution is k*(m+1). See third Pinter link for proof.
Theorem: a(6*n-1) >= n + 3*n*(6*n-1). See second Pinter link for proof.
Theorem: a(n) <= a(n-2) + 2*n.
Empirical g.f.: x*(1 + 2*x + 2*x^2 + 2*x^3 + 3*x^4 + x^5 + x^6) / ((1 - x)^3*(1 + x)^2*(1 - x + x^2)*(1 + x + x^2)). - Robert Israel, Nov 01 2015. Corrected by Colin Barker, Jan 31 2018
a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-6) - a(n-7) - a(n-8) + a(n-9) for n>9 (conjectured). - Colin Barker, Jan 31 2018
|
|
EXAMPLE
|
For a(2) = 3, an optimal configuration is
//
./
(This is best seen using a fixed-width font. It is better to use "." instead of " " for blank squares, because " " tends to disappear.)
Note that the bottom left square can't have / because that would conflict with the / at top right, or \ because that would conflict with its horizontal and vertical neighbors.
For a(3) = 6, an optimal configuration is
///
../
/./
For a(4) = 10, an optimal configuration may be depicted, with the grid lines explicitly drawn, as
+-+-+-+-+
|/| |\|\|
+-+-+-+-+
|/| |\| |
+-+-+-+-+
|/| | | |
+-+-+-+-+
|/|/|/|/|
+-+-+-+-+
or, using "o" and "." to represent used and unused vertices, as
.-o-o-o-.
|/| |\|\|
o-o-o-o-o
|/| |\| |
o-o-.-o-.
|/| | | |
o-o-o-o-o
|/|/|/|/|
o-o-o-o-.
For a(5) = 16, an optimal configuration is
///.\
../.\
\\.\\
\./..
\.///
For more examples, see the link "Optimal configurations for n=1..26".
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more,nice
|
|
AUTHOR
|
Gabriella Pinter, Stephen Wasielewski, Peter Boyland, Ivan Roth, G. Christopher Hruska, Jeb Willenbring, Oct 22 2015
|
|
EXTENSIONS
|
Additional comments and terms a(9)-a(26) from Robert Israel, Nov 01 2015
This entry is the result of merging two independent submissions, merged by N. J. A. Sloane, Nov 11 2015
|
|
STATUS
|
approved
|
|
|
|