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
    Wha$t$ 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...

  • 1
    @Robert You have made my life a bit complicated. Let me edit. Please wait. – 2012-02-14