# [seqfan] Binary arrays with both rows and cols sorted, symmetries?

rhhardin at att.net rhhardin at att.net
Mon Jun 29 18:12:21 CEST 2009

```Running through a(n) = the number of nXn binary arrays a(i,j) with both rows and
columns sorted as binary numbers, you can

1.  consider rows as numbers left to right (2^-j), or right to left (2^+j)
2.  consider cols as numbers top to bottom (2^-i), or bottom to top (2^+i)
3.  sort rows by < <= >= or >
4.  sort cols by < <= >= or >

so there are 64 cases, with some obvious equivalencies.

It turns out though, if you run through them, there are only six a(n) series.

[implied sum over repeated index]  [n=1..9 for all]

(Question at the bottom.)

Sequence 2 7 45 650 24520 2625117 836488618 818230288201 2513135860300849
a(i,j)*2^(+j) <= a(i-1,j)*2^(+j) and a(i,j)*2^(+i) <= a(i,j-1)*2^(+i)
a(i,j)*2^(+j) <= a(i-1,j)*2^(+j) and a(i,j)*2^(-i) >= a(i,j-1)*2^(-i)
a(i,j)*2^(+j) >= a(i-1,j)*2^(+j) and a(i,j)*2^(+i) >= a(i,j-1)*2^(+i)
a(i,j)*2^(+j) >= a(i-1,j)*2^(+j) and a(i,j)*2^(-i) <= a(i,j-1)*2^(-i)
a(i,j)*2^(-j) <= a(i-1,j)*2^(-j) and a(i,j)*2^(+i) >= a(i,j-1)*2^(+i)
a(i,j)*2^(-j) <= a(i-1,j)*2^(-j) and a(i,j)*2^(-i) <= a(i,j-1)*2^(-i)
a(i,j)*2^(-j) >= a(i-1,j)*2^(-j) and a(i,j)*2^(+i) <= a(i,j-1)*2^(+i)
a(i,j)*2^(-j) >= a(i-1,j)*2^(-j) and a(i,j)*2^(-i) >= a(i,j-1)*2^(-i)

Sequence 2 6 20 70 252 924 3432 12870 48620
a(i,j)*2^(+j) <= a(i-1,j)*2^(+j) and a(i,j)*2^(+i) >= a(i,j-1)*2^(+i)
a(i,j)*2^(+j) <= a(i-1,j)*2^(+j) and a(i,j)*2^(-i) <= a(i,j-1)*2^(-i)
a(i,j)*2^(+j) >= a(i-1,j)*2^(+j) and a(i,j)*2^(+i) <= a(i,j-1)*2^(+i)
a(i,j)*2^(+j) >= a(i-1,j)*2^(+j) and a(i,j)*2^(-i) >= a(i,j-1)*2^(-i)
a(i,j)*2^(-j) <= a(i-1,j)*2^(-j) and a(i,j)*2^(+i) <= a(i,j-1)*2^(+i)
a(i,j)*2^(-j) <= a(i-1,j)*2^(-j) and a(i,j)*2^(-i) >= a(i,j-1)*2^(-i)
a(i,j)*2^(-j) >= a(i-1,j)*2^(-j) and a(i,j)*2^(+i) >= a(i,j-1)*2^(+i)
a(i,j)*2^(-j) >= a(i-1,j)*2^(-j) and a(i,j)*2^(-i) <= a(i,j-1)*2^(-i)

Sequence 2 4 21 330 14610 1820715 653629616 696496706166 2267861968974085
a(i,j)*2^(+j) <  a(i-1,j)*2^(+j) and a(i,j)*2^(+i) <= a(i,j-1)*2^(+i)
a(i,j)*2^(+j) <  a(i-1,j)*2^(+j) and a(i,j)*2^(-i) >= a(i,j-1)*2^(-i)
a(i,j)*2^(+j) <= a(i-1,j)*2^(+j) and a(i,j)*2^(+i) <  a(i,j-1)*2^(+i)
a(i,j)*2^(+j) <= a(i-1,j)*2^(+j) and a(i,j)*2^(-i) >  a(i,j-1)*2^(-i)
a(i,j)*2^(+j) >  a(i-1,j)*2^(+j) and a(i,j)*2^(+i) >= a(i,j-1)*2^(+i)
a(i,j)*2^(+j) >  a(i-1,j)*2^(+j) and a(i,j)*2^(-i) <= a(i,j-1)*2^(-i)
a(i,j)*2^(+j) >= a(i-1,j)*2^(+j) and a(i,j)*2^(+i) >  a(i,j-1)*2^(+i)
a(i,j)*2^(+j) >= a(i-1,j)*2^(+j) and a(i,j)*2^(-i) <  a(i,j-1)*2^(-i)
a(i,j)*2^(-j) <  a(i-1,j)*2^(-j) and a(i,j)*2^(+i) >= a(i,j-1)*2^(+i)
a(i,j)*2^(-j) <  a(i-1,j)*2^(-j) and a(i,j)*2^(-i) <= a(i,j-1)*2^(-i)
a(i,j)*2^(-j) <= a(i-1,j)*2^(-j) and a(i,j)*2^(+i) >  a(i,j-1)*2^(+i)
a(i,j)*2^(-j) <= a(i-1,j)*2^(-j) and a(i,j)*2^(-i) <  a(i,j-1)*2^(-i)
a(i,j)*2^(-j) >  a(i-1,j)*2^(-j) and a(i,j)*2^(+i) <= a(i,j-1)*2^(+i)
a(i,j)*2^(-j) >  a(i-1,j)*2^(-j) and a(i,j)*2^(-i) >= a(i,j-1)*2^(-i)
a(i,j)*2^(-j) >= a(i-1,j)*2^(-j) and a(i,j)*2^(+i) <  a(i,j-1)*2^(+i)
a(i,j)*2^(-j) >= a(i-1,j)*2^(-j) and a(i,j)*2^(-i) >  a(i,j-1)*2^(-i)

Sequence 2 3 4 5 6 7 8 9 10
a(i,j)*2^(+j) <  a(i-1,j)*2^(+j) and a(i,j)*2^(+i) >= a(i,j-1)*2^(+i)
a(i,j)*2^(+j) <  a(i-1,j)*2^(+j) and a(i,j)*2^(-i) <= a(i,j-1)*2^(-i)
a(i,j)*2^(+j) <= a(i-1,j)*2^(+j) and a(i,j)*2^(+i) >  a(i,j-1)*2^(+i)
a(i,j)*2^(+j) <= a(i-1,j)*2^(+j) and a(i,j)*2^(-i) <  a(i,j-1)*2^(-i)
a(i,j)*2^(+j) >  a(i-1,j)*2^(+j) and a(i,j)*2^(+i) <= a(i,j-1)*2^(+i)
a(i,j)*2^(+j) >  a(i-1,j)*2^(+j) and a(i,j)*2^(-i) >= a(i,j-1)*2^(-i)
a(i,j)*2^(+j) >= a(i-1,j)*2^(+j) and a(i,j)*2^(+i) <  a(i,j-1)*2^(+i)
a(i,j)*2^(+j) >= a(i-1,j)*2^(+j) and a(i,j)*2^(-i) >  a(i,j-1)*2^(-i)
a(i,j)*2^(-j) <  a(i-1,j)*2^(-j) and a(i,j)*2^(+i) <= a(i,j-1)*2^(+i)
a(i,j)*2^(-j) <  a(i-1,j)*2^(-j) and a(i,j)*2^(-i) >= a(i,j-1)*2^(-i)
a(i,j)*2^(-j) <= a(i-1,j)*2^(-j) and a(i,j)*2^(+i) <  a(i,j-1)*2^(+i)
a(i,j)*2^(-j) <= a(i-1,j)*2^(-j) and a(i,j)*2^(-i) >  a(i,j-1)*2^(-i)
a(i,j)*2^(-j) >  a(i-1,j)*2^(-j) and a(i,j)*2^(+i) >= a(i,j-1)*2^(+i)
a(i,j)*2^(-j) >  a(i-1,j)*2^(-j) and a(i,j)*2^(-i) <= a(i,j-1)*2^(-i)
a(i,j)*2^(-j) >= a(i-1,j)*2^(-j) and a(i,j)*2^(+i) >  a(i,j-1)*2^(+i)
a(i,j)*2^(-j) >= a(i-1,j)*2^(-j) and a(i,j)*2^(-i) <  a(i,j-1)*2^(-i)

Sequence 2 3 15 234 10706 1411450 539124281 607445721710 2067567866431155
a(i,j)*2^(+j) <  a(i-1,j)*2^(+j) and a(i,j)*2^(+i) <  a(i,j-1)*2^(+i)
a(i,j)*2^(+j) <  a(i-1,j)*2^(+j) and a(i,j)*2^(-i) >  a(i,j-1)*2^(-i)
a(i,j)*2^(+j) >  a(i-1,j)*2^(+j) and a(i,j)*2^(+i) >  a(i,j-1)*2^(+i)
a(i,j)*2^(+j) >  a(i-1,j)*2^(+j) and a(i,j)*2^(-i) <  a(i,j-1)*2^(-i)
a(i,j)*2^(-j) <  a(i-1,j)*2^(-j) and a(i,j)*2^(+i) >  a(i,j-1)*2^(+i)
a(i,j)*2^(-j) <  a(i-1,j)*2^(-j) and a(i,j)*2^(-i) <  a(i,j-1)*2^(-i)
a(i,j)*2^(-j) >  a(i-1,j)*2^(-j) and a(i,j)*2^(+i) <  a(i,j-1)*2^(+i)
a(i,j)*2^(-j) >  a(i-1,j)*2^(-j) and a(i,j)*2^(-i) >  a(i,j-1)*2^(-i)

Sequence 2 2 2 2 2 2 2 2 2
a(i,j)*2^(+j) <  a(i-1,j)*2^(+j) and a(i,j)*2^(+i) >  a(i,j-1)*2^(+i)
a(i,j)*2^(+j) <  a(i-1,j)*2^(+j) and a(i,j)*2^(-i) <  a(i,j-1)*2^(-i)
a(i,j)*2^(+j) >  a(i-1,j)*2^(+j) and a(i,j)*2^(+i) <  a(i,j-1)*2^(+i)
a(i,j)*2^(+j) >  a(i-1,j)*2^(+j) and a(i,j)*2^(-i) >  a(i,j-1)*2^(-i)
a(i,j)*2^(-j) <  a(i-1,j)*2^(-j) and a(i,j)*2^(+i) <  a(i,j-1)*2^(+i)
a(i,j)*2^(-j) <  a(i-1,j)*2^(-j) and a(i,j)*2^(-i) >  a(i,j-1)*2^(-i)
a(i,j)*2^(-j) >  a(i-1,j)*2^(-j) and a(i,j)*2^(+i) >  a(i,j-1)*2^(+i)
a(i,j)*2^(-j) >  a(i-1,j)*2^(-j) and a(i,j)*2^(-i) <  a(i,j-1)*2^(-i)

After thinking about it, I can't account why reversing the bits
(-i to +i, or -j to +j) has the effect of just reversing < and >.  You don't
in fact get the same solutions, just the same number of them.

--
rhhardin at mindspring.com
rhhardin at att.net (either)

```