1
$\begingroup$

Given the following matrix:

$$\begin{bmatrix} a & b & c & d\\ e & f & g & h\\ i & j & k & l \end{bmatrix}$$

how many sets of 3 letter sets using all the letters once can be made if:

  1. Letters in the same row can't be in the same 3 set.
  2. As in 1 plus not all 3 letters can be from the same col ( but 2 can ).

For example: $$\{ \{a , g , k \} , \{ b, f , j \} , \{ c, e, l \} , \{ d , h, i‬‬ \} \}$$ meets the first condition but not the second.

I started out on the first part by choosing pairs for each letter in the first row disregarding order: $$\frac{\binom{8}{2}\binom{6}{2}\binom{4}{2}}{4!}$$

I know I need to use inclusion exclusion for the second half, but I'm not sure how to proceed.

  • 0
    What happened with the answers to [this question](http://math.stackexchange.com/q/97351), and to [this other one](http://math.stackexchange.com/q/100414)?2012-02-14

1 Answers 1

3

This partly answers this question and partly the previous version. I will fix this answer in may be a day's time. Please bear with me!


Am I missing something obvious?

For the first problem: To construct a set: you need to choose a letter from each row. This can be done in $\binom 4 1^3$ ways. The second set can be obtained in $\binom 31^3$ ways and so on.And, these are considered as a set. Hence there is no notion of order of an element in a set unless we define one. Hence the number is $\dfrac{\binom 4 1^3 \binom 3 1^3 \binom 2 1^3 }{4!}=16 \cdot 9 \cdot 4=576 $ ways.

$$$$

For the next problem:

  • The first set can be formed as follows: by choosing the first element in $\binom 4 1$ ways. Now, for the second element note that, you can take the element below the first choice, whence you'll have $\binom 3 1$ ways for the third element or some other element in $\binom 3 1$ ways, whence for the third element you're left with $\binom 2 1$ choices. Briefly summarised, we can have first sets in $\binom 4 1 \left(\binom 3 1+\binom 2 1 \binom 3 1 \right)=4(3+6)=36 $ ways.
  • The second set can be chosen in $3+(2+3)+(3+2+2)$ ways
  • The third set can be chosen in $1$ way.

So...

  • 0
    These are sets of sets, so order doesn't matter.2012-02-14
  • 0
    I'm not sure, but on the exam they said explicitly to use inclusion exclusion. Maybe I'm missing something in the wording...2012-02-14
  • 0
    Let me edit. Please note that first problem is done best this way.2012-02-14
  • 0
    I apoligize, I misread the second part of the question. Not all 3 letters can be from the same col, but 2 of them can be.2012-02-14
  • 1
    @Robert You have made my life a bit complicated. Let me edit. Please wait.2012-02-14