Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What happened with the answers to this question, and to this other one? –  Did Feb 14 '12 at 19:10
add comment

1 Answer 1

up vote 3 down vote accepted

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...

share|improve this answer
    
These are sets of sets, so order doesn't matter. –  Robert S. Barnes Feb 14 '12 at 17:55
    
I'm not sure, but on the exam they said explicitly to use inclusion exclusion. Maybe I'm missing something in the wording... –  Robert S. Barnes Feb 14 '12 at 18:24
    
Let me edit. Please note that first problem is done best this way. –  user21436 Feb 14 '12 at 18:27
    
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. –  Robert S. Barnes Feb 14 '12 at 18:33
1  
@Robert You have made my life a bit complicated. Let me edit. Please wait. –  user21436 Feb 14 '12 at 18:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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