1
$\begingroup$

How many $n\times n$ binary matrices (values are only $0'$s and $1'$s) are there, such that at least one row is filled by only $0'$s?

How to approach this problem?

Improve this question
$\endgroup$
  • $\begingroup$ This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc. $\endgroup$ – Did Dec 23 '18 at 21:35
5
$\begingroup$

The number of binary matrices with at-least one "zero" row $=$ Total no. of binary matrices $-$ No. of binary matrices with no "zero" row

Total no. of binary matrices $=2^{n^2}\because$ the matrix contains $n^2$ entries each of which can be $0,1$.

For the second part, observe each row of the binary matrix can be set up in $2^n$ ways by virtue of having $n$ entries that may be $0,1$. Each row is a non-"zero" row, so out of the $2^n$ possibilities for a given row, all but one (that is the the "zero" row) are admissible. So, each row can be set up in $2^n-1$ ways. Since there are $n$ rows, no. of binary matrices with no "zero" row $=(2^n-1)^n$.

This answer is equal to $2^{n^2}-(2^n-1)^n$.

Improve this answer
$\endgroup$

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