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

[franktaw at netscape.net]

-----Original Message-----
   From: rhhardin at att.net

>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)

This is A089006, with a matching description.

>  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)

This is A000984, central binomial coefficients.  A quick scan found no 
comment relating to this property.

>  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)

Not in the database.

>  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)

Obviously n+1.

>  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)

A162100, just added by the author of the note I am responding to.

>  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)

Obviously all 2's.

>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.

Reversing the bits in the rows has the effect of reversing the 
significance of the columns.  So flip the columns, and now you  have 
them sorted in the other order.

Franklin T. Adams-Watters