the number of $m \times n$ matrices with entries $a$, $b$, or $c$ such that each column and each row contains at least one $a$ or one $b$.

Question

Let $a$, $b$, $c$ be real numbers and $f(m, n)$ be the number of $m \times n$ matrices with entries $a$, $b$, or $c$ such that each column and each row contains at least one $a$ or one $b$. Find a formula for $f(m, n)$.

My try: If it is $m \times n$, then there are $3^{m\times n}$ different placement, but i do not know how to extract the cases where each columns and rows contain at least one $a$ or one $b$. Any help?

Answer 1

Realize that because of the fact that it is said at least one "a" or one "b" , placing one of them will satify the condition.What i meant is that one column can consist of only $a$ and $c$ , not any $b's$ , so let say that the cells that contain "a" or "b" denoted by $d$. Now , the question turn out to be :

Let $a,d$ be real numbers and $f(m,n)$ be the number of m×n matrices with entries $a,d$ such that each column and each row contains at least one $d$. Find a formula for $f(m,n)$

I thought that the best way is to use P.I.E such that assume that each rows contains at least one $d$ , we can handle it by just placing at least one $d$ to each of $m$ rows. However , we should also place them such that each columns contains at least one $d$. We can do it such that

All placements - (first column does not contain any $d's$ or second column does not contain any $d's$ or ... or nth column does not contain any $d's$

Now , it is time for P.I.E such that if the first column does not have any $d's$ , then any row can be constructed such that

Select cells among $(n-1)$ columns to place $d's$ ,but realize that because of each row contain at least one $d$ , so the empty set is not allowed. Then , we can select one cell or two etc such that $$\binom{n-1}{1}+\binom{n-1}{2}+...+\binom{n-1}{n-1}=2^{n-1}-1$$

We placed the $d's$ into a row using the way above. However , realize that we have $m$ rows and the places where $d's$ placed will take either $a$ or $b$. Then , the real calculation is

$$2^1\binom{n-1}{1}+2^2\binom{n-1}{2}+...+2^{n-1}\binom{n-1}{n-1}$$

As you see , the foregoing formula can be seen as the sum of the coefficients in the expansion of $$2^1\binom{n-1}{1}+2^2\binom{n-1}{2}+...+2^{n-1}\binom{n-1}{n-1}=(1+2x)^{n-1}-1=3^{n-1}-1$$

Because , if we let $x=1$ , then we can find sum of the coefficients in the binomial expression.

Hence ,If we generalize the situation from the first colum to all matrix by P.I.E: $$\sum_{k=0}^n\binom{n}{k}(-1)^k(3^{n-k}-1)^m$$