1
$\begingroup$

I'm trying to figure out how to do the following question, but I got stuck. I just don't see how they are counting these people.

In a student council consisting of 16 persons there are mathematics- and computer science students, freshmen as well as sophomores. Every group has four representatives in the council. The council appoints a committee, consisting of 6 council members.

(a) In how many ways can this be done, if every group has to have at least one representative in the committee? (Ans.: 4480)

I would say we first select a representative of each of the $4$ groups of $4$ people (maths freshmen, maths sophomore, comp sci freshmen, comp sci sophomore). We can do this in 4 ways each, and we need to make four decisions, so $4^4$ we then need to choose amongst the remaining people, so $\binom{12}{2}$. My final answer would be: $$4^4 \cdot \binom{12}{2} =16896$$ this number is way too big, what is the error in my reasoning here?

(b) And in how many ways if every group has at most two representatives in the committee? (Ans.: 4320) At most two means we combine all possible ways to have precisely $0$, $1$ and $2$ representatives per group, we sum these up. I am also not quite sure how to obtain the precisely a certain amount of representatives.

$\endgroup$
1
$\begingroup$

In how many ways can a committee with six members be selected if each of the four groups of four people has to have at least one representative on the committee?

There are two cases: One group has three representatives and each of the others has one or two groups each have two representatives and each of the others has one.

Case 1: One group has three representatives and each of the others has one.

Choose the group that has three representatives. Choose three of its four members. Choose one of the four members of each of the other three groups. There are $$\binom{4}{1}\binom{4}{3}\binom{4}{1}\binom{4}{1}\binom{4}{1}$$ such selections.

Case 2: Two groups each have two representatives and each of the others each has one.

Choose which two of the four groups have two representatives. Choose two of the four members from each of these two groups. Choose one of the four members of each of the remaining two groups. There are $$\binom{4}{2}\binom{4}{2}\binom{4}{2}\binom{4}{1}\binom{4}{1}$$ such selections.

Total: There are $$\binom{4}{1}\binom{4}{3}\binom{4}{1}\binom{4}{1}\binom{4}{1} + \binom{4}{2}\binom{4}{2}\binom{4}{2}\binom{4}{1}\binom{4}{1} = 1024 + 3456 = 4480$$ admissible committees.

What was your mistake?

By designating a representative from each group, you counted each case in which a group has $k$ representatives $k$ times, once for each way you could have designated a representative of that group. Notice that $$\color{red}{\binom{3}{1}}\binom{4}{1}\binom{4}{3}\binom{4}{1}\binom{4}{1}\binom{4}{1} + \binom{4}{2}\color{red}{\binom{2}{1}}\binom{4}{2}\color{red}{\binom{2}{1}}\binom{4}{2}\binom{4}{1}\binom{4}{1} = 3072 + 13824 = 16896$$

To illustrate, let's label the groups $A$, $B$, $C$, and $D$. If you reserve one spot for the members of each group on the committee, you count the selection in which three members of group $A$ are selected and one member of each of the other groups is selected three times, once for each way of designating one of the members of group $A$ as the designated representative of group $A$.

\begin{array}{c c} \text{reserved spots} & \text{additional members}\\ \hline A_1, B_1, C_1, D_1 & A_2, A_3\\ A_2, B_1, C_1, D_1 & A_1, A_3\\ A_3, B_1, C_1, D_1 & A_1, A_2 \end{array}

If you reserve one spot for a representative of each group, you count each selection with two members each of groups $A$ and $B$ and one member each of groups $C$ and $D$ four times, twice each for each of the two ways you could designate a representative to fill the reserved spot for a member of groups $A$ and $B$.

\begin{array} \text{reserved spots} & \text{additional members}\\ \hline A_1, B_1, C_1, D_1 & A_2, B_2\\ A_1, B_2, C_1, D_1 & A_2, B_1\\ A_2, B_1, C_1, D_1 & A_1, B_2\\ A_2, B_2, C_1, D_1 & A_1, B_1 \end{array}

In how many ways can the committee be selected if every group has at most two representatives on the committee?

There are two cases: Two groups each have two members and the other two groups have one or three groups each have two members.

We discussed the case in which two groups each have two members above.

Three groups each have two members: Select which three of the four groups each have two members. Choose two members from each of these four groups.

This can be done in $$\binom{4}{3}\binom{4}{2}\binom{4}{2}\binom{4}{2} = 864$$ ways, giving a total of $$\binom{4}{2}\binom{4}{2}\binom{4}{2}\binom{4}{1}\binom{4}{1} + \binom{4}{3}\binom{4}{2}\binom{4}{2}\binom{4}{2} = 3456 + 864 = 4320$$ admissible committees.

$\endgroup$
  • 1
    $\begingroup$ Thank you, this helped me a lot :) especially that I could first try out the second question myself after your explanation, really cool how you made the box show text if you float over it. I didn't know that option was available. $\endgroup$ – Wesley Strik Dec 8 '18 at 10:33
  • 1
    $\begingroup$ I have added two tables to illustrate why the method you used in your attempt counts each committee with three members of one group and one member from each of the other groups three times and counts each committee with two members each from two groups and one member each from the other two groups four times. $\endgroup$ – N. F. Taussig Dec 9 '18 at 10:51
  • 1
    $\begingroup$ Very nice indeed. I am delighted by your effort :) $\endgroup$ – Wesley Strik Dec 9 '18 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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