Enumeration of block codes

# Enumeration of block codes

Usually when enumerating or constructing under the action in form of the exponentiation we can apply Lehmann's Lemma ([14],[15]) which reduces the action of a wreath product H wr XG on YX to the action of the group G on the set of all functions from X into the set of all orbits of H on Y. As a matter of fact it can't be applied in this situation since SA wr Sn acts on the set of all m-subsets or more generally on the powerset
2(An)
of An. For enumerating the isometry classes of block codes each [n,m] code C can be identified with its characteristic function
cC:An -> {0,1}
cC(f)=1 if fÎC,        cC(f)=0 if f not ÎC,
which fulfils |f-1({1} )|=m. The other way round, each function f from An to {0,1} with |f-1({1} )|=m is the characteristic function of an [n,m] block code over A. Using Pólya's Theorem [18] we can determine the number of classes of block codes:
Theorem: The number of classes of [n,m] block codes over the alphabet A is the coefficient of xm in the expansion of the substitution xi:=1+xi into the cycle index of the exponentiation SA wr Sn. In short it is the coefficient of xm in
Z(SA wr Sn,An | xi:=1+xi).
It is well known how to compute the cycle index of the exponentiation from the cycle indices of SA and Sn. See [11][17][16]. Using the computer algebra system SYMMETRICA [22] the following tables were computed:

Number of classes of [n,m] block codes over an alphabet of size 2.
 n\m 0 1 2 3 4 5 6 7 8 9 10 1 1 1 1 2 1 1 2 1 1 3 1 1 3 3 6 3 3 1 1 4 1 1 4 6 19 27 50 56 74 56 50 5 1 1 5 10 47 131 472 1326 3779 9013 19963 6 1 1 6 16 103 497 3253 19735 120843 681474 3.561696 7 1 1 7 23 203 1606 18435 221778 2773763 33.297380 375.158732 8 1 1 8 32 373 4647 91028 2074059 51.107344 1245.930065 28900.653074 9 1 1 9 43 649 12320 404154 16.957301 805.174011 38921.113842 1.816451.773537 10 1 1 10 56 1079 30493 1646000 124.727148 11244.522420 1.063289.204514 98.630203.059528

Number of classes of [n,m] block codes over an alphabet of size 3.
 n\m 0 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 2 1 1 2 4 5 5 4 2 1 1 3 1 1 3 10 34 105 321 846 1984 4023 7074 4 1 1 4 20 144 1245 12473 120213 1067757 8.508432 60.801152 5 1 1 5 35 490 11075 334678 10.274578 293.142769 7563.157341 176207.637611 6 1 1 6 57 1470 82918 7.194272 664.545445 57778.060974 4.570181.600483 327.615878.641570

Number of classes of [n,m] block codes over an alphabet of size 4.
 n\m 0 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 2 1 1 2 4 10 13 23 26 32 26 23 3 1 1 3 10 55 254 1643 10164 63488 364843 1930906 4 1 1 4 20 223 3227 77194 2097080 57.796870 1502.295684 36065.804158 5 1 1 5 35 759 32970 2877651 311.400852 34630.385050 3.667889.498353 360.865277.628727 6 1 1 6 57 2309 292103 90.647411 37593.032352 16.429342.163157 6925.787777.638463 2.729333.815881.686935

harald.fripertinger@kfunigraz.ac.at,
last changed: January 23, 2001

 Enumeration of block codes