Binary arrays with both rows and cols sorted, symmetries ======================================================== Ron H. Hardin, rhhardin(AT)att.net, Jun 29 2009 With a postscript from Franklin T. Adams-Watters (FrankTAW(AT)Netscape.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] Sequence 2 7 45 650 24520 2625117 836488618 818230288201 2513135860300849 (A089006) 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 (A000984) 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 (A151801) 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(n) = n+1, cf. A000027) 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 (A162100) 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 (A007395) 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 explain 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. Ron Hardin, Jun 29 2009 Postscript from Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net =================================================================== 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, Jun 29 2009