OFFSET
1,4
COMMENTS
Also weight A_10 of the weight distribution for a square n X n Single Parity Check Product (SPCP) code when the 1's represent bit errors, and 0's represent unchanged data bits. For a SPCP code, A_odd = 0, A_4 = C(n,2)^2 = A000537(n-1), A_6 = 3!*C(n,3) = A179058(n), A_8 = A396317(n). See the rectangular formula for other message data formats.
REFERENCES
E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968, pp. 397-400.
R. E. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley, 1983, p. 431.
C. Leung, Evaluation of the Error Probability of Single Parity-Check Codes, IEEE Transactions on Communications Vol. COM-31, NO. 2, Feb 1983, pp. 250-253.
F. J. MacWilliams, and N. J. A. Sloane The Theory of Error Correcting Codes, Elsevier/North Holland 1977, p. 21.
W. W. Peterson, and E. J. Weldon, Error Correcting Codes, MIT Press, 1994, pp. 64-70, pp. 131-132.
LINKS
G. Gordon Thompson, Table of n, a(n) for n = 1..100
A. M. Patel, Optimal Rectangular Code for High Density Magnetic Tapes.
G. Gordon Thompson, Probability of Undetected Error for Some Simple Product Codes, MS Thesis, UT Arlington TX, May 1984, pp. 35-37.
FORMULA
a(n) = 2040*C(n,5)^2 + 1440*C(n,5)*C(n,4) + 120*C(n,5)*C(n,3) + 96*C(n,4)^2.
a(n) = 1/120*(n - 3)*(n - 2)^2 * (n - 1)^2 * n^2 * (17*n^3 - 127*n^2 + 300*n - 236).
The rectangular formula for the n X k matrices is a(n,k) = 2040*C(n,5)*C(k,5) + 720*C(n,5)*C(k,4) + 720*C(n,4)*C(k,5) + 60*C(n,3)*C(k,5) + 60*C(n,5)*C(k,3) + 96*C(n,4)*C(k,4). This is shown in table form below, where each entry is multiplied by its column header and left row header, then all entries are summed for a(n,k). The square case n X n, is when k = n.
A_10 C(k,2) C(k,3) C(k,4) C(k,5)
C(n,2) 0 0 0 0
C(n,3) 0 0 0 60
C(n,4) 0 0 96 720
C(n,5) 0 60 720 2040
EXAMPLE
The first formula given above adds the counts of 4 subsets that are categorized by the same number of 1's in rows and columns (with transpositions in the same category).
For n=4, a(4) = 90*0 + 1440*0 + 120*0 + 96 = 96 by the formula. See also the figures below, showing an example for each subset:
.
Subset 1, 5 X 5 exactly 2 1's per row and 2 1's per column.
1 1 0 0 0
0 1 1 0 0 The number of patterns of 2 1's per row and column
0 0 1 1 0 is 2040, see A001499(5).
0 0 0 1 1
1 0 0 0 1
.
Subset 2, 5 X 4, one row with 4 1's. We count the number of patterns in nonzero rows.
1 1 1 1 0 The number of patterns in the first row is 5. The 0 in the first row
0 0 0 1 1 requires a pair of 1's in that column and there are C(3,2) = 3 choices of
0 0 1 0 1 those. The second 0 down from the top in the last right column requires two
1 1 0 0 0 1's in that row, there are C(4,2) = 6 patterns of those. That same row has
0 0 0 0 0 two 0's that have 2 remaining choices in respective columns to add 1's.
The row of 4 can be placed in 4 ways. Finally, a doubling of choices comes
from transposition. Total choices = 5*3*6*2*4*2 = 1440.
.
Subset 3, 5 X 3, two rows with 4 1's. We count the number of patterns in nonzero rows.
1 1 0 0 0 Number of patterns of 2 1's in the first row is C(5,2) = 10.
1 0 1 1 1 The next row of 4 requires a 0 in a shared column of 1 from first row.
0 1 1 1 1 The last row requires a 0 in the shared column of the other 1 from the
0 0 0 0 0 first row. The number of row selections is 3! Finally, a doubling of
0 0 0 0 0 choices comes from transposition. Total choices = 2*3!*C(5,2) = 120.
.
Subset 4, 4 X 4, one row of 4 1's and one column of 4 1's. We count the nonzero row
1 1 1 1 0 and nonzero columns. There are 4 choices for row of 4, and 4 choices for
1 1 0 0 0 column of 4. The remaining part has 6 patterns. Total choices = 4*4*6 = 96.
1 0 1 0 0
1 0 0 1 0
0 0 0 0 0
.
For n=5, a(5) = 2040*1 + 1440*5 + 120*10 + 96*25 = 12840.
KEYWORD
nonn,easy,new
AUTHOR
G. Gordon Thompson, May 21 2026
STATUS
approved