Minimal Partition lines

[Ed Pegg]

If we reorder the partitions of 5, the minimal number of vertical lines is 4.  

{{5}, {4, 1}, {3, 1, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}, {2, 1, 2}, {3, 2}}

┃━━━━━━━━━┃
┃━━━━━━━┃━┃
┃━━━━━┃━┃━┃
┃━━━┃━┃━┃━┃
┃━┃━┃━┃━┃━┃
┃━━━┃━┃━━━┃
┃━━━━━┃━━━┃

{{6}, {5, 1}, {4, 1, 1}, {4, 2}, {2, 2, 2}, {2, 2, 1, 1}, {2, 1, 1,1, 1}, {1, 1, 1, 1, 1, 1}, {3, 1, 1, 1}, {3, 2, 1}, {3, 3}}  needs 6 vertical lines. 
┃━━━━━━━━━━━┃
┃━━━━━━━━━┃━┃
┃━━━━━━━┃━┃━┃
┃━━━━━━━┃━━━┃
┃━━━┃━━━┃━━━┃
┃━━━┃━━━┃━┃━┃
┃━━━┃━┃━┃━┃━┃
┃━┃━┃━┃━┃━┃━┃
┃━━━━━┃━┃━┃━┃
┃━━━━━┃━━━┃━┃
┃━━━━━┃━━━━━┃ 

  {{7}, {5, 2}, {5, 1, 1}, {4, 1, 1, 1}, {4, 2, 1}, {6, 1}, {3, 3, 1}, {3, 2, 1, 1}, {3, 1, 1, 1, 1}, {2, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1}, {2, 2, 1, 1, 1}, {2, 2, 2, 1}, {2, 2, 3}, {4, 3}}  needs 8 vertical lines. 

┃━━━━━━━━━━━━━┃
┃━━━━━━━━━┃━━━┃
┃━━━━━━━━━┃━┃━┃
┃━━━━━━━┃━┃━┃━┃
┃━━━━━━━┃━━━┃━┃
┃━━━━━━━━━━━┃━┃
┃━━━━━┃━━━━━┃━┃
┃━━━━━┃━━━┃━┃━┃
┃━━━━━┃━┃━┃━┃━┃
┃━━━┃━┃━┃━┃━┃━┃
┃━┃━┃━┃━┃━┃━┃━┃
┃━━━┃━━━┃━┃━┃━┃
┃━━━┃━━━┃━━━┃━┃
┃━━━┃━━━┃━━━━━┃
┃━━━━━━━┃━━━━━┃   

I'm not sure how to extend this.     

[Ed Pegg]

My current bests for 8 and 9.  

┃━━━━━━━┃━━━━━━━┃
┃━━━━━━━━━━━━━━━┃
┃━━━━━┃━━━━━━━━━┃
┃━┃━━━┃━━━━━━━━━┃
┃━┃━┃━┃━━━━━━━━━┃
┃━┃━┃━┃━┃━━━━━━━┃
┃━┃━┃━┃━┃━━━┃━━━┃
┃━┃━┃━┃━┃━┃━┃━━━┃
┃━┃━┃━┃━┃━┃━┃━┃━┃
┃━┃━┃━┃━┃━┃━━━━━┃
┃━┃━┃━┃━━━┃━━━━━┃
┃━━━┃━┃━━━┃━━━━━┃
┃━━━┃━━━━━┃━━━━━┃
┃━┃━┃━━━━━┃━━━━━┃
┃━┃━┃━━━━━━━━━━━┃
┃━━━┃━━━━━━━━━━━┃
┃━━━┃━━━┃━━━━━━━┃
┃━━━┃━━━┃━━━┃━━━┃
┃━┃━┃━━━┃━━━┃━━━┃
┃━┃━┃━━━┃━━━━━━━┃
┃━┃━━━━━┃━━━━━━━┃
┃━┃━━━━━━━━━━━━━┃


┃━━━━━━━━━━━━━━━━━┃
┃━━━━━┃━━━━━┃━━━━━┃
┃━━━━━┃━━━━━━━━━━━┃
┃━━━━━┃━━━┃━━━━━━━┃
┃━━━━━━━━━┃━━━━━━━┃
┃━┃━━━━━━━┃━━━━━━━┃
┃━┃━━━━━━━━━━━━━━━┃
┃━┃━━━━━━━━━┃━━━━━┃
┃━┃━┃━━━━━━━┃━━━━━┃
┃━┃━┃━━━━━━━━━━━━━┃
┃━┃━┃━━━━━━━━━┃━━━┃
┃━┃━┃━━━━━┃━━━┃━━━┃
┃━┃━┃━┃━━━┃━━━┃━━━┃
┃━┃━┃━┃━━━┃━━━━━━━┃
┃━┃━┃━┃━━━━━━━━━━━┃
┃━┃━┃━┃━┃━━━━━━━━━┃
┃━┃━┃━┃━┃━┃━━━━━━━┃
┃━┃━┃━┃━┃━┃━━━┃━━━┃
┃━┃━┃━┃━┃━┃━┃━┃━┃━┃
┃━┃━┃━┃━┃━━━┃━┃━┃━┃
┃━┃━┃━┃━━━━━┃━┃━┃━┃
┃━┃━━━┃━━━━━┃━┃━┃━┃
┃━━━━━┃━━━━━┃━┃━┃━┃
┃━━━━━┃━━━━━┃━┃━━━┃
┃━━━━━━━━━━━┃━┃━━━┃
┃━━━┃━━━━━━━┃━┃━━━┃
┃━━━┃━━━┃━━━┃━┃━━━┃
┃━━━┃━━━┃━━━┃━━━━━┃
┃━━━┃━━━┃━━━━━━━━━┃
┃━━━┃━━━━━━━━━━━━━┃

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/d019c1c1-5b60-4d78-b9a5-70f78435fa64n%40googlegroups.com.

[M. F. Hasler]

Ed,

That's a very nice problem!

I can confirm your results up to n=9,

i.e., a(n) = n-1 inner bars (=vertical lines) for 0 < n < 6, then 

a(n=6) = 6, a(7) = 8, a(8) = 12, a(9) = 16 inner bars.

I also know that a(n=10) >= 22, because I could quickly test that there's no solution with 21.

Up to n=7, a DP approach gave me the result in < 1 sec,

but for n >= 8 I changed to solving it as generalized TSP with the ILP solver PuLP

(with a first version that needed only a few seconds for n = 8, 

but for n = 9 I had to make some further improvements,

switching to Cluster-Level DFJ Subtour Elimination, to get down to a few minutes).

I found different solutions from yours, listed below.

We can represent the solutions compactly through a sequence of integers
whose k-th bit is set if there's a vertical bar after the k-th column. For example,

Solution(0, 8, 12, 14, 15, 10, 2) for n = 5 with 4 + 2 bars:

|=========| -> (5,)

|=======|=| -> (4, 1) |=====|=|=| -> (3, 1, 1) |===|=|=|=| -> (2, 1, 1, 1) |=|=|=|=|=| -> (1, 1, 1, 1, 1) |===|===|=| -> (2, 2, 1) |===|=====| -> (2, 3)

(Here 4+2 bars means 4 inner + 2 outer vertical lines... Maybe we should just count the lines 

in excess of / in addition to the 2 outer and n-1 inner lines?)  

- Maximilian

Optimal Solution(0, 4, 5, 7, 23, 31, 11, 10, 2, 3, 1) for n = 6 with 6 + 2 bars:

|===========| -> (6,) |=====|=====| -> (3, 3) |=|===|=====| -> (1, 2, 3) |=|=|=|=====| -> (1, 1, 1, 3) |=|=|=|===|=| -> (1, 1, 1, 2, 1) |=|=|=|=|=|=| -> (1, 1, 1, 1, 1, 1) |=|=|===|===| -> (1, 1, 2, 2) |===|===|===| -> (2, 2, 2) |===|=======| -> (2, 4) |=|=|=======| -> (1, 1, 4)

|=|=========| -> (1, 5)

Alternate Solution(0, 4, 6, 7, 15, 31, 14, 10, 8, 24, 16) for n = 6 with 6 + 2 bars:

|===========| -> (6,)

|=====|=====| -> (3, 3) |===|=|=====| -> (2, 1, 3) |=|=|=|=====| -> (1, 1, 1, 3) |=|=|=|=|===| -> (1, 1, 1, 1, 2) |=|=|=|=|=|=| -> (1, 1, 1, 1, 1, 1) |===|=|=|===| -> (2, 1, 1, 2) |===|===|===| -> (2, 2, 2) |=======|===| -> (4, 2) |=======|=|=| -> (4, 1, 1) |=========|=| -> (5, 1)

yet another Solution(0, 16, 24, 8, 10, 26, 30, 31, 28, 20, 4) for n = 6 with 6 + 2 bars:

|===========| -> (6,)

|=========|=| -> (5, 1) |=======|=|=| -> (4, 1, 1) |=======|===| -> (4, 2) |===|===|===| -> (2, 2, 2) |===|===|=|=| -> (2, 2, 1, 1) |===|=|=|=|=| -> (2, 1, 1, 1, 1) |=|=|=|=|=|=| -> (1, 1, 1, 1, 1, 1) |=====|=|=|=| -> (3, 1, 1, 1) |=====|===|=| -> (3, 2, 1) |=====|=====| -> (3, 3) 

Solution([0, 1, 3, 7, 6, 2, 18, 26, 58, 62, 63, 57, 25, 9, 8]) for n = 7 with 8 + 2 bars:

|=============| -> (7,)

|=|===========| -> (1, 6) |=|=|=========| -> (1, 1, 5) |=|=|=|=======| -> (1, 1, 1, 4) |===|=|=======| -> (2, 1, 4) |===|=========| -> (2, 5) |===|=====|===| -> (2, 3, 2) |===|===|=|===| -> (2, 2, 1, 2) |===|===|=|=|=| -> (2, 2, 1, 1, 1) |===|=|=|=|=|=| -> (2, 1, 1, 1, 1, 1) |=|=|=|=|=|=|=| -> (1, 1, 1, 1, 1, 1, 1) |=|=====|=|=|=| -> (1, 3, 1, 1, 1) |=|=====|=|===| -> (1, 3, 1, 2) |=|=====|=====| -> (1, 3, 3) |=======|=====| -> (4, 3) 

Solution(0, 2, 10, 42, 58, 62, 63, 60, 52, 36, 32, 48, 56, 40, 8) for n = 7 with 8 + 2 bars:

|=============| -> (7,) |===|=========| -> (2, 5) |===|===|=====| -> (2, 2, 3) |===|===|===|=| -> (2, 2, 2, 1) |===|===|=|=|=| -> (2, 2, 1, 1, 1) |===|=|=|=|=|=| -> (2, 1, 1, 1, 1, 1) |=|=|=|=|=|=|=| -> (1, 1, 1, 1, 1, 1, 1) |=====|=|=|=|=| -> (3, 1, 1, 1, 1) |=====|===|=|=| -> (3, 2, 1, 1) |=====|=====|=| -> (3, 3, 1) |===========|=| -> (6, 1) |=========|=|=| -> (5, 1, 1) |=======|=|=|=| -> (4, 1, 1, 1) |=======|===|=| -> (4, 2, 1) |=======|=====| -> (4, 3) 

 

Solution(0, 16, 18, 50, 48, 56, 60, 63, 62, 58, 42, 40, 8, 9, 1) for n = 7 with 8 + 2 bars:

|=============| -> (7,) |=========|===| -> (5, 2) |===|=====|===| -> (2, 3, 2) |===|=====|=|=| -> (2, 3, 1, 1) |=========|=|=| -> (5, 1, 1) |=======|=|=|=| -> (4, 1, 1, 1) |=====|=|=|=|=| -> (3, 1, 1, 1, 1) |=|=|=|=|=|=|=| -> (1, 1, 1, 1, 1, 1, 1) |===|=|=|=|=|=| -> (2, 1, 1, 1, 1, 1) |===|===|=|=|=| -> (2, 2, 1, 1, 1) |===|===|===|=| -> (2, 2, 2, 1) |=======|===|=| -> (4, 2, 1) |=======|=====| -> (4, 3) |=|=====|=====| -> (1, 3, 3) |=|===========| -> (1, 6)  

Solution(0, 32, 48, 16, 24, 56, 60, 62, 63, 58, 42, 10, 14, 12, 8)  for n = 7 with 8 + 2 bars:

|=============| -> (7,)

|===========|=| -> (6, 1) |=========|=|=| -> (5, 1, 1) |=========|===| -> (5, 2) |=======|=|===| -> (4, 1, 2) |=======|=|=|=| -> (4, 1, 1, 1) |=====|=|=|=|=| -> (3, 1, 1, 1, 1) |===|=|=|=|=|=| -> (2, 1, 1, 1, 1, 1) |=|=|=|=|=|=|=| -> (1, 1, 1, 1, 1, 1, 1) |===|===|=|=|=| -> (2, 2, 1, 1, 1) |===|===|===|=| -> (2, 2, 2, 1) |===|===|=====| -> (2, 2, 3) |===|=|=|=====| -> (2, 1, 1, 3) |=====|=|=====| -> (3, 1, 3) |=======|=====| -> (4, 3)

Solution([0, 16, 80, 112, 120, 122, 126, 127, 124, 108, 100, 36, 32, 96, 104, 72, 8, 40, 42, 43, 41, 1])

for n = 8 with 12 + 2 bars: |===============| -> (8,) |=========|=====| -> (5, 3) |=========|===|=| -> (5, 2, 1) |=========|=|=|=| -> (5, 1, 1, 1) |=======|=|=|=|=| -> (4, 1, 1, 1, 1) |===|===|=|=|=|=| -> (2, 2, 1, 1, 1, 1) |===|=|=|=|=|=|=| -> (2, 1, 1, 1, 1, 1, 1) |=|=|=|=|=|=|=|=| -> (1, 1, 1, 1, 1, 1, 1, 1) |=====|=|=|=|=|=| -> (3, 1, 1, 1, 1, 1) |=====|=|===|=|=| -> (3, 1, 2, 1, 1) |=====|=====|=|=| -> (3, 3, 1, 1) |=====|=====|===| -> (3, 3, 2) |===========|===| -> (6, 2) |===========|=|=| -> (6, 1, 1) |=======|===|=|=| -> (4, 2, 1, 1) |=======|=====|=| -> (4, 3, 1) |=======|=======| -> (4, 4) |=======|===|===| -> (4, 2, 2) |===|===|===|===| -> (2, 2, 2, 2) |=|=|===|===|===| -> (1, 1, 2, 2, 2) |=|=====|===|===| -> (1, 3, 2, 2) |=|=============| -> (1, 7)

Solution(0, 64, 80, 16, 24, 8, 10, 42, 26, 58, 122, 127, 126, 124, 92, 88, 120, 112, 96, 100, 36, 32) for n = 8 with 12 + 2 bars:

|===============| -> (8,)
|=============|=| -> (7, 1)
|=========|===|=| -> (5, 2, 1)
|=========|=====| -> (5, 3)
|=======|=|=====| -> (4, 1, 3)
|=======|=======| -> (4, 4)
|===|===|=======| -> (2, 2, 4)
|===|===|===|===| -> (2, 2, 2, 2)
|===|===|=|=====| -> (2, 2, 1, 3)
|===|===|=|=|===| -> (2, 2, 1, 1, 2)
|===|===|=|=|=|=| -> (2, 2, 1, 1, 1, 1)
|=|=|=|=|=|=|=|=| -> (1, 1, 1, 1, 1, 1, 1, 1)
|===|=|=|=|=|=|=| -> (2, 1, 1, 1, 1, 1, 1)
|=====|=|=|=|=|=| -> (3, 1, 1, 1, 1, 1)
|=====|=|=|===|=| -> (3, 1, 1, 2, 1)
|=======|=|===|=| -> (4, 1, 2, 1)
|=======|=|=|=|=| -> (4, 1, 1, 1, 1)
|=========|=|=|=| -> (5, 1, 1, 1)
|===========|=|=| -> (6, 1, 1)
|=====|=====|=|=| -> (3, 3, 1, 1)
|=====|=====|===| -> (3, 3, 2)
|===========|===| -> (6, 2)

Minimum internal vertical bars for n=9: 16
Solution(0, 32, 36, 12, 8, 136, 128, 192, 224, 240, 208, 80, 84, 212, 244, 228, 164, 160, 
168, 170, 234, 250, 255, 254, 252, 248, 216, 200, 72, 64) for n = 9 with 16 + 2 bars:
|=================| -> (9,)
|===========|=====| -> (6, 3)
|=====|=====|=====| -> (3, 3, 3)
|=====|=|=========| -> (3, 1, 5)
|=======|=========| -> (4, 5)
|=======|=======|=| -> (4, 4, 1)
|===============|=| -> (8, 1)
|=============|=|=| -> (7, 1, 1)
|===========|=|=|=| -> (6, 1, 1, 1)
|=========|=|=|=|=| -> (5, 1, 1, 1, 1)
|=========|===|=|=| -> (5, 2, 1, 1)
|=========|===|===| -> (5, 2, 2)
|=====|===|===|===| -> (3, 2, 2, 2)
|=====|===|===|=|=| -> (3, 2, 2, 1, 1)
|=====|===|=|=|=|=| -> (3, 2, 1, 1, 1, 1)
|=====|=====|=|=|=| -> (3, 3, 1, 1, 1)
|=====|=====|===|=| -> (3, 3, 2, 1)
|===========|===|=| -> (6, 2, 1)
|=======|===|===|=| -> (4, 2, 2, 1)
|===|===|===|===|=| -> (2, 2, 2, 2, 1)
|===|===|===|=|=|=| -> (2, 2, 2, 1, 1, 1)
|===|===|=|=|=|=|=| -> (2, 2, 1, 1, 1, 1, 1)
|=|=|=|=|=|=|=|=|=| -> (1, 1, 1, 1, 1, 1, 1, 1, 1)
|===|=|=|=|=|=|=|=| -> (2, 1, 1, 1, 1, 1, 1, 1)
|=====|=|=|=|=|=|=| -> (3, 1, 1, 1, 1, 1, 1)
|=======|=|=|=|=|=| -> (4, 1, 1, 1, 1, 1)
|=======|=|===|=|=| -> (4, 1, 2, 1, 1)
|=======|=====|=|=| -> (4, 3, 1, 1)
|=======|=====|===| -> (4, 3, 2)
|=============|===| -> (7, 2)

[Joerg Arndt]

The listings are surprisingly similar to what is given in on page 21 (right column) in https://arxiv.org/abs/1405.6503
Section 5: "Partitions as weakly increasing lists of parts", pp. 20ff.
To play around with that ordering, see https://jjj.de/fxt/demo/comb/index.html#partition-asc-subset-lex

Apparently I have mostly resisted the urge to add anything from that paper to the OEIS:
https://oeis.org/search?q=subset-lex&fmt=short

If there is anything I should add, someone please holler.

Best regards,  jj

[Ed Pegg]

I get a "simple" lower bound of  Ceiling[(p(n) + 1)/2] because each permutation begins or ends a line. Also,  {n} contributes no internal cut, while {1,1,...,1} forces extra endpoints.  Can anyone verify this reasoning? 
One of A046682, A005987, A180652  may be related. 

I have solutions meeting this lower bound up to p(11). 

C. D. Savage, Gray code sequences of partitions, Journal of Algorithms 10 (1989) 577-595.    may be related.  

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/21fb4be3-b3b0-4ebd-b509-1695a7c8c6d5%40th-nuernberg.de.