[seqfan] Re: A264041

[Martin Fuller]

Proof that a(n even)=n(n+1)/2:

Lower bound by the obvious construction in the PDF, namely a(n) = (two full sides meeting at a corner) + a(n-2) = 2n-1 + (n-2)(n-1)/2
Upper bound is from Michael's answer in http://math.stackexchange.com/questions/339387/
* Between two adjacent rows of squares is a row of n+1 corners. Each diagonal uses up one of them, so at most n+1 diagonals in two adjacent rows.
* Therefore the total is at most (n+1) * (#pairs of rows) = (n+1) * (n/2)

Martin Fuller

----Original message----
>From : Rob.Pratt at sas.com
Date : 10/11/2015 - 02:04 (GMTST)
To : seqfan at list.seqfan.eu
Subject : [seqfan] Re: A264041

382 <= a(27) <= 383

a(29) = 440

For n in {2,4,...,100}, a(n) = n(n+1)/2

Let b(n) denote the number of optimal solutions.  Then b(1) = 2, b(2) = 4, b(3) = 28, b(4) = 108, b(5) = 2, b(6) = 13968, b(7) = 480, b(8) > 14000, b(9) > 5000.

-----Original Message-----
From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Neil Sloane
Sent: Saturday, November 07, 2015 3:54 PM
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Subject: [seqfan] Re: A264041

Robert, A264041 is indeed a lovely sequence.

When n is odd, you say there can be more than one solution.

For odd n >= 7, there is quite a contrast between the pictures on the left (for n odd) and on the right (for n even).

On the left the examples you give have no symmetry at all. If there are a lot of solutions, is it possible that there are symmetric solutions that you didn't see? For small odd n, 5, 7, 9, say, do you have a feeling for how big the solution space is?

If it is the case that for some odd n the solution is unique AND ugly, that would be an interesting fact

[This is of course a question that often arises in packing problems. Are optimal solutions necessarily beautiful? But it is rare to see a problem where half the time the solution is beautiful, half the time not.]

Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com


On Thu, Nov 5, 2015 at 8:11 PM, <israel at math.ubc.ca> wrote:

> Thanks, Rob. That seems like a good idea: this problem has maximal 
> 4-cliques (corresponding to slashes meeting at an interior vertex) as 
> well as 2-cliques. However, it still doesn't look like Cplex is going 
> to manage to compute a(27) on my computer.
>
> Cheers,
> Robert
>
> On Nov 4 2015, Rob Pratt wrote:
>
> If you used an edge-based formulation with constraints of the form x_i 
> +
>> x_j <= 1 for edge (i,j), you might be able to squeeze out a few more 
>> terms by instead using a clique-based formulation. Explicitly, 
>> precompute all
>> (maximal) cliques and then use constraints sum {i in C} x_i <= 1 for 
>> each clique C. This formulation has a tighter linear programming relaxation.
>>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/