1
$\begingroup$

Let's say we have a 2 by 3 or a by b binary matrix. We want to determine the maximum number of matrices such that no matrix has all zeroes in one of its columns.

I started by counting the total number of matrices : 2^(axb). Then I tried counting the number of matrices that don't make the fit.
The case in which the first column is all 0 gives the following : 2^(a)(b-1) Then I multiplied it with the number of columns. The formula is : 2^(a)(b-1)b

It doesn't give me the correct answer, and I think it's a problem related to permutations. How do I approach this?

$\endgroup$
2
$\begingroup$

Each column in an $a\times b$ matrix has $a$ entries. There are $2^a$ distinct binary columns with $a$ entries, only one of which has all entries equal to $0$. It follows that there are $2^a-1$ valid choices for any given column.

Since there are $b$ columns, the number of binary matrices whose columns are all valid is

$$(2^a-1)^b$$

$\endgroup$
  • $\begingroup$ Very clear, thank you!! $\endgroup$ – Firdaws Mar 17 '18 at 6:49
  • $\begingroup$ You're welcome! Glad to help. $\endgroup$ – Fimpellizieri Mar 17 '18 at 6:59

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.