5
$\begingroup$

In a course, there are $3n$ male students, $3n$ female students and $2n$ lecturers:

  • The task is to distribute the students among the lecturers, such that in every lecturer's class there are exactly $3$ students, at least one is a male and one is a female.
  • In how many ways can we distribute the students ?.

My approach:

  • First choose $2n$ males and $2n$ females to make sure every lecturer has one male and one female - ${3n\choose 2n}\cdot {3n\choose 2n}$.
  • Then, freely distribute the remaning ones - $(2n)!$.
  • Finally, cancel the order of choosing by dividing by $3!$ for each triplet - so $(3!)^n\ldots$
  • The final result is ${3n\choose 2n}\cdot {3n\choose 2n}\cdot (2n)!\cdot \frac{1}{(3!)^n}$.
  • I know this is wrong because if $n=1$ we get $3$ which is obviously incorrect.
  • But I need some help understanding the incorrect combinatorical arguments I used, and how to solve this correctly.

Cheers !.

$\endgroup$
1
  • 3
    $\begingroup$ In problems like this you overcount if you distribute the students necessary to meet the one of each requirement, then freely distribute the rest because A can be in one class to meet the requirement, then again as one of the freely distributed students. First choose the professors that get $2$ male students, then distribute the students to the right classes. $\endgroup$ Commented Jun 11 at 12:14

3 Answers 3

3
$\begingroup$

We can begin by selecting the lecturers who will be assigned 2 males (and 1 female). Let’s say there are $k$ of them. So they will account for $2k$ of the males, and the other instructors will account for a further $2n-k$ of the males. Thus, $2k+2n-k=3n$, so $k=n$. (A symmetry argument (male-female) would suggest as much, but now we know for sure.) So there are $2n\choose n$ ways to select these male-heavy instructors.

Now let’s start assigning the males. Line up the instructors, male-heavy first, with each group sorted in order by, say, height. Then permute the males (in any of the $(3n)!$ possible ways) and pair up the first $2n$ of them. So for $1 \leq i \leq n$, males $m_{2i-1}$ and $m_{2i}$ both get assigned to instructor $t_i$, and the remaining $n$ males get assigned in order to the remaining $n$ instructors. But each pair could have appeared in the permutation in either order, so we have to divide by $2^n$.

And the females can be handled in the same way. Permute them all, and then account for having double-counted each of the $n$ pairs (which are paired at the other end of the row of instructors) .

So the total number of distributions is $$N(n) = {{2n}\choose n} \frac{((3n)!)^2}{2^{2n}} . $$

$\endgroup$
5
  • $\begingroup$ I don't think I get how you arrived at the conclusion that there should be exactly $n$ "male heavy" instructors. Can I look at it like this?: If we first choose $2n$ males and then $2n$ females, say, with respect to order (although I'm not sure about that), we get $\frac{(3n)!}{(2n!)}\frac{(3n)!}{(2n!)}$. Then we have $n$ males and $n$ females left to distribute, so we choose the instructors that get the males - $2n\choose n$, and that's it? We get the total result of $(\frac{(3n)!}{(2n)!})^2{2n\choose n}$. I know it's wrong since for $n=2$ I get a different answer than you,But why? $\endgroup$
    – natitati
    Commented Jun 13 at 1:11
  • $\begingroup$ Also, I'm actually quite interested in knowing where I am wrong, in addition to hearing the correct solution. Because these problems are so confusing... maybe it's because I'm just starting out, but I never actually know if I am choosing the right tool for a problem like this. $\endgroup$
    – natitati
    Commented Jun 13 at 1:25
  • $\begingroup$ If $k$ of the $2n$ instructors are male heavy, then the $3n$ males get assigned to the instructors thus: the $k$ that are male-heavy (so getting 2 males each) get a total of $2k$ of the males. And the remaining $2n-k$ instructors, who are the female-heavy ones, get 1 male each, or a total of $2n-k$ males. But together, those two groups of instructors get all the males, so $2k+(2n-k)=3n$. And that’s why $k=n$. $\endgroup$ Commented Jun 13 at 3:15
  • $\begingroup$ One mistake in your approach is that ${{3n}\choose{2n}}^2$ counts only the number of ways you can select the first males and females whom you want to distribute. It doesn’t count the number of ways you can then assign those selected students to the instructors. $\endgroup$ Commented Jun 13 at 3:34
  • $\begingroup$ Hmm I see. So that's the mistake in my original question. And how about the answer I posted in the first comment? It's still wrong... and I understand why for the last step $2n \choose n$ is wrong - it doesn't count for example the ways to shuffle the remaining females. One alternative I came up with is to instead multiply by $(2n)!$ to count all the ways I can shuffle the remaining students, regardless of their gender. But that's still too low. $\endgroup$
    – natitati
    Commented Jun 13 at 11:34
0
$\begingroup$

Am answering as the two posted answers don't match each other.

Also, I am taking students to be distinct, otherwise the problem would be trivial. (It should have been mentioned, though, in mass distributions, often they are treated as just numbers)

We shall make use of the multinomial coefficient, which comes handy for such problems. Suppose $n$ distinct balls are to be distributed to $k$ distinct boxes, the multinomial coefficient does it as $\dbinom{n}{n_1, n_2, n_3, ... n_k},\Sigma{n_i}= n$

It has three equivalent forms, e.g. to take a simple example, $$\binom{8}{4,3,1} \equiv \binom84\binom43\binom11 \equiv \frac{8!}{4!3!1!}$$ and I shall use the permutation form here

Note particularly that it puts $n_1$ in Box $1$, not in any box, so it only lays down a pattern, if we want $n_1$ etc to be in any box, we will need to permute the pattern

In short, for this problem, we shall use the format

$\textbf{[Lay Down Pattern] x [Permute pattern]}$

To illustrate with a small concrete example,
with $n=2$, the pattern we want is

$F:\,2-2-1-1$
$M:1-1-2-2$

so the # of arrangements $= \left[\dfrac{6!}{2!2!1!1!}\times\dfrac{6!}{1!1!2!2!}\right]\times\dfrac{4!}{2!2!}$

[Lay down pattern for F][Lay down pattern for M][Permute Pattern]

It can easily be generalised, and of course it can be condensed, but the condensed form won't easily give an insight into the process followed.

Removing $1!s$, a condensed generalised formula that still gives some insight into the process I followed would be

$$\left[\frac{(3n)!}{(2!)^n}\times\frac{(3n)!}{(2!)^n}\right]\times\frac{(2n)!}{n!n!}$$

which is equivalent to @Paul answer

$\endgroup$
1
  • $\begingroup$ Do you have any questions on this approach ? $\endgroup$ Commented Jun 17 at 14:41
-1
$\begingroup$

Total students = $3n + 3n = 6n$

Number of trios that can be formed = $^{6n}C_3$

Number of all female trios = $^{3n}C_3$

Number of all male trios = $^{3n}C_3$

Number of at least $1$ male and at least $1$ female trios = $^{6n}C_3 - 2 \times ^{3n}C_3 = T$

How many ways to distribute $T$ among $2n$ lecturers?
$^TC_{2n}$

Correct/incorrect/both/neither?

$\endgroup$
10
  • $\begingroup$ What is $^{6n}C_3$? I'm not familiar with this notation. Btw I can't know if your answer is correct, I don't have the solution :( $\endgroup$
    – natitati
    Commented Jun 11 at 17:14
  • $\begingroup$ @natitati Sorry, old timer here. $^nC_r$ means n choose r. $\endgroup$
    – Hudjefa
    Commented Jun 12 at 1:09
  • $\begingroup$ Okay, thanks. Now, I get how you got $T$, but I dont understand the final step. Why is it $T\choose 2n$, when all we need is to decide how we order the trios among the lecturers? There are $2n$ lecturers and trios, so all we need is to decide how we "shuffle" the trios - number of ways to do it is $(2n)!$. So all in all we should get $T\cdot (2n)!$. What am I missing? $\endgroup$
    – natitati
    Commented Jun 12 at 15:06
  • 1
    $\begingroup$ The number of disjoint trios (regardless of gender) that can be formed is not $$\binom{6n}{3}$$, but $$\binom{6n}{3}\binom{6n-3}{3}\binom{6n-6}{3}....\binom33$$ $\endgroup$ Commented Jun 17 at 14:40
  • 2
    $\begingroup$ How do you form teams of $3,2,1$ from $6$ people ? $\binom63\binom32\binom11$, yes ? $\endgroup$ Commented Jun 17 at 16:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .