9
$\begingroup$

A combinatorial problem arising with certain checksums: When sending messages, the user data are protected by adding a parity bit for bit positions $1\dots8$ and a parity bit for each byte. So, the checksum protected messages have both even parity bitwise (columns) and even parity bytewise (rows). Now, bit failures will not be detected on the receiver side, if they occur on an even number of positions in rows and on an even number of positions in columns. I have to figure out the undetected error probability of this checksum for certain user message lengths ($1$ byte up to $15$ bytes). As a consequence, assuming equally distributed bit failure probability, I have to find out for each even number $K$ of bit failures, a (closed) formula for:

How many $M\times N$ binary matrices are there having even row sums and even column sums, whereby the number of $1s$ is $K$, $K$ even?

It's relatively easy to answer this question, if there is no restriction to a specific value of $K$. This is stated e.g. as exercise $20$ in Richard P. Stanleys "Enumerative Combinatorics, Vol I, 2nd Edition" (see also the answer to question 329932).

I tried to solve this problem with generating functions. In order to do so, I was looking for a proper decomposition similar to the examples e.g. in "Combinatorial Enumeration, ch. 3", especially section 3.4 "2-covers of a set and homeomorphically irreducible labeled graphs" from Goulden and Jackson. I'm thinking a lot about symbolic equations describing this type of matrices giving me proper decompositions, so that it can be translated into generating functions, but I was not successful so far.

A relatively simple one-dimensional example of decomposition is the essence of my answer to question 713409.

Another idea was to apply some two-fold variations of the inclusion-exclusion principle similar to the one-dimensional example which answers question 439596, regrettably without success so far.

Any helpful hints are welcome. Thanks.

$\endgroup$
3
  • $\begingroup$ What chapter are you referring to with regards to Exercise 20 in Stanley? I can't find anything similar to your question as "Exercise 20" in the copy I have (nor in Volume II). I'm not sure which edition I have though. $\endgroup$ – Casteels Mar 3 '14 at 12:23
  • $\begingroup$ I'm referring to the 2nd edition of Volume I. And it's exercise 20 of ch.1: "How many m x n matrices of 0's and 1's are there, such that every row and column contains an even number of 1's? An odd number of 1's?" I have both editions and the second is about twice as big. Btw: He ranked it as [2]*, which means "relatively easy" :-) $\endgroup$ – Markus Scheuer Mar 3 '14 at 19:39
  • $\begingroup$ Oh I see now that I have an old edition. I didn't realize a significantly expanded second edition was only recently published! It's available here: www-math.mit.edu/~rstan/ec/ec1.pdf $\endgroup$ – Casteels Mar 4 '14 at 9:54
4
+100
$\begingroup$

Here is a recursive formula: Let $A_M(N,L,K)$ be the number of matrices with $N$ columns and $M$ rows such that

  • all columns have an even number of ones
  • there are a total of $2K$ ones
  • the number of rows with an odd number of ones is $2L$.

Then $A_M(N,0,K)$ is the number we want to compute and for $N>0$: $$A_M(N,L,K) = \sum_{k=0}^K \sum_{l=0}^K A_M(N-1,l,k) {2l \choose K-k-L+l} {M-2l\choose K-k+L-l}.$$

From the definition we can see that $A_M(0,0,0) = 1$ and $A_M(0,L,K)=0$ for $L>0$ or $K>0$.

Reasoning is: We enumerating all matrices that can appear if we delete the last column. Assume we obtain a matrix with $2k$ ones and $2l$ rows with an odd number of ones. Then in the last column we add $2(K-k)$ ones of which $l_1$ are written in rows where there have been an odd number of ones before, and $l_2$ where the number of ones was even. Then $$2(K-k) = l_1+l_2 \\ 2L = 2l-l_1+l_2$$ from which we conclude $$l_1 = K-k-L+l \\l_2 = K-k+L-l.$$ Therefore, there are ${2l \choose l_1} {M-2l\choose l_2}$ ways to obtain the desired matrix.

$\endgroup$
3
  • $\begingroup$ Thank you, benh. I find your answer interesting, but I'm not sure how to start a computation. Could you please also provide some starting value conditions in order to complete the recursive formula? $\endgroup$ – Markus Scheuer Mar 22 '14 at 22:34
  • $\begingroup$ @MarkusScheuer I added the recursion start. I have also implemented a computation of $A$ to check whether the formula is correct. You can use it, if you like: github.com/bheuer/MSE/blob/master/MSE693366.py $\endgroup$ – benh Mar 23 '14 at 0:56
  • $\begingroup$ You've made a good job! The reasoning of your solution is clear and clever. Thanks for your python code. I've already did it with some R code and it works fine. :-) $\endgroup$ – Markus Scheuer Mar 23 '14 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.