I think I have a formula for the labeled (tabtot) count: For a partition of n=1*a_1+2*a_2+3*a_3+...+j*a_j into k parts k=a_1+a_2+...+a_j we have PROD {i=1 to j} j^a_j * n^(k*(k-1)/2) * n! / PROD {i=1 to j} ((j!)^a_j * a_j!) To get a_labeled(n) sum these products for each partition of n. I get: 1: Total 1 Idem 0 1 2: Total 4 Idem 0 2 2 3: Total 48 Idem 0 3 18 27 4: Total 4964 Idem 0 4 96 768 4096 5: Total 10089780 Idem 0 5 400 11250 312500 9765625 6: Total 472010285382 Idem 0 6 1440 116640 11197440 1813985280 470184984576 7: Total 558745410230718214 Idem 0 7 4704 972405 263533760 148299505725 199397583417606 558545864083284007 The unlabeled (dist) version I'm sure can be done through Polya enumeration, but I doubt I have the patience to work out the formula. I'm wondering about the associative version of this. If we added associativity to the requirements, I suspect what we get could be described as a meet semilattice of pointed sets, but I will need to do more investigation to verify that. Certainly it would be dominated by the commutative idempotent semigroups which are just meet semilattices. Christian ------ Original Message ------ Received: Tue, 14 Feb 2006 12:49:42 PM PST From: "Schroeppel, Richard" <rschroe@sandia.gov> To: math-fun@mailman.xmission.comCc: rcs@cs.arizona.edu Subject: [math-fun] AB=B.AA; Gosper's packing problem
Good work on the AB=B.AA problem! This might even lead to a formula for the number of tables of each size. My data for N=2,3,4,5 is 2: dist 2 tabtot 4 idemspec 0 1 1 isospec 1.2 3: dist 11 tabtot 48 idemspec 0 1 3 7 isospec 1.6 2.3 3 6 4: dist 234 tabtot 4964 idemspec 0 1 5 36 192 isospec 1.185 2.38 3.6 6.5 5: dist 85196 tabtot 10089780 idemspec 0 1 7 108 2725 82355 isospec 1.83035 2.2023 3.57 4.34 5.6 24.3 6.36 8 20
Dist is the number of distinct, non-isomorphic tables; Tabtot is the number of tables with isomorphic tables counted. Idemspec is the number of (non-isomorphic) tables with each number of idempotents -- the "all elements are idempotent" class seems dominant. Isospec reports on the number of tbales with each (size of) automorphism group: For the 85196 tables with five elements, 83035 have no automorphisms (group size =1, self), while three tables have a size-24 group, and there's one table each for group sizes 8 and 20.
The observations that squares (AA) are idempotent, and that an element and its square have identical rows and columns, constrains the table structure quite a bit.