[seqfan] A264041

[israel at math.ubc.ca]

You may find this sequence, which I've just contributed, to be interesting. 
The Name is "Largest number of vertex-disjoint / and \ that can be packed 
in an n x n grid". Here we think of / and \ as forming diagonals of grid 
squares; we don't allow / and \ to be adjacent horizontally or vertically, 
because they would have a vertex in common (/\ or \/ or \ / or / \) or two 
/ to be diagonally adjacent northeast to southwest, or two \ to be 
diagonally adjacent northwest to southeast: ./ / or \ .\

This is equivalent to a Maximum Independent Set problem on a graph with 
2*n^2 vertices. The best way I've found to solve it is using Cplex on the 
corresponding binary linear programming problem: in this way I've obtained 
a(n) for n up to 26. Optimal solutions for even n have a very regular 
structure, e.g. for n=4

////
.../
//./
././

For odd n>=5, patterns similar to that are suboptimal, and the optimal 
solutions don't seem to have a simple pattern. Strangely enough, however, 
there is a rather simple empirical generating function (found using Maple's 
"guessgf") that fits all the data I have:
 (1+2*x+2*x^2+2*x^3+3*x^4+x^5+x^6)*x/(1-x-x^2+x^3-x^6+x^7+x^8-x^9)

A proof of correctness of this g.f. (or even that it provides a bound) 
would be welcome. Also welcome would be more terms, or programs to produce 
them in a reasonable time.
 
Cheers,
Robert