[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)
More information about the SeqFan
mailing list