0
$\begingroup$

I have a question very similar to the post in the link below.

But, what do we do when we are given a variable for the total number of students, not a constant number?

Here is the modified version of the question. "There are n students in a class. In how many ways can the teacher select groups of two to work on an exercise."

Problem : Permutation and Combination : In how many ways can we divide 12 students in groups of fours.

$\endgroup$
  • $\begingroup$ Related: math.stackexchange.com/questions/868099/… $\endgroup$ – NoName Oct 11 '14 at 5:37
  • $\begingroup$ Well, if $n$ is odd, we cannot do it. If $n$ is even, let $n=2m$. after studying a few concrete cases, you will probably be able to use the same method to find a general formula. $\endgroup$ – André Nicolas Oct 11 '14 at 5:39
1
$\begingroup$

There are many approaches to an answer. Note that the job cannot be done if $n$ is odd. So let $n$ be even, say $n=2m$.

For concreteness, let $n=10$.

Line up the students in increasing order of student number. The first person in the list can choose her study partner in $9$ ways. For every such choice, the so far unpartnered student with smallest student number can choose her study partner in $7$ ways.

For every such choice, the so far unpartnered student with smallest student number can choose her study partner in $5$ ways. For every such choice, the so far unpartnered student with smallest student number can choose her study partner in $3$ ways. That gives a total of $(9)(7)(5)(3)$ ways.

The answer looks a little nicer if we write instead $(9)(7)(5)(3)(1)$. Maybe to make things look even nicer, we can multiply top, and missing bottom, by $(10)(8)(6)(4)(2)$. We get $$\frac{10!}{(10)(8)(6)(4)(2)},\quad\text{which is} \frac{10!}{2^5 \cdot 5!}.$$

Now that we have gone through the reasoning got $n=10$, the general case is straightforward. Suppose there are $2m$ students.

The student with lowest student number can choose her partner in $2m-1$ ways. For every such way, the so far unpartnered student with lowest student number can choose her partner in $2m-3$ ways. And then the so far unpartnered student with lowest student number can choose her partner in $2m-5$ ways, and so on, for a total of $$(2m-1)(2m-3)(2m-5)\cdots(3)(1).$$ The same manipulation as before gives the more compact expression $$\frac{(2m)!}{2^m \cdot m!}.$$

$\endgroup$
  • $\begingroup$ Andre' Nicolas, off-topic but why haven't you posted any questions? $\endgroup$ – Joao Oct 11 '14 at 6:45
  • $\begingroup$ There are many questions I have worked on with no success or very incomplete success. Have not yet given up on any of them! $\endgroup$ – André Nicolas Oct 11 '14 at 6:51
  • $\begingroup$ Oh cool! Be sure to post your questions on mse if you ever (although you will succeed in solving whatever question your working on) need help! You probably have some really awesome questions to share. Cheers! $\endgroup$ – Joao Oct 12 '14 at 5:46
0
$\begingroup$

Ok thank you very much for this explanation. However, in the denominator, the factorial would be the number of groups we have which is actually (n divided by k)! not just n! because n is the total number of students in the class… right?

Let’s say the question asks how to split the class into groups of k. Would this formula be correct?

Total number of students in the class = n Size of groups we are choosing = k *Note: n must be divisible by k

$\frac{\binom{n}{k}\binom{n-k}{k}\binom{n-2k}{k}\binom{n-3k}{k}\cdot\cdot\cdot\binom{k}{k}}{(n/k)!}$

Example: Number of students in the class n = 12 Size of groups we are choosing k = 3

$\frac{\binom{12}{3}\binom{9}{3} \binom{6}{3} \binom{3}{3}}{4!}$

Is my formula correct? Particularly would the denominator be correct (n / k)!

Thank you for your help!

$\endgroup$
  • $\begingroup$ The formula you give is correct. If you expand, you get the simpler expression $\dfrac{12!}{(3!)^4\cdot 4!}$. $\endgroup$ – André Nicolas Oct 11 '14 at 18:59
0
$\begingroup$

n must be even as if it is odd the problem does not work. We choose 2 people from the n original ones for the one pair. from the n-2 people left, we choose another 2. etc.

So it appears to be: $\binom{n}{2}\binom{n-2}{2} \cdot \cdot \cdot\binom{2}{2}$ ways.

However, consider this: if we have {A,B} as the first pair, and {C,D} as the second pair, is this not identical to having {C,D} as the first pair, and {A,B} as the second pair instead, assuming ceteris paribus?

So we have in fact overcounted, by a factor of $(\frac{n}{2})!$, the number of ways in which we can arrange these groups among themselves.

So the answer is $\frac{\binom{n}{2}\binom{n-2}{2} \cdot \cdot \cdot \binom{2}{2}}{(\frac{n}{2})!}$

$\endgroup$
  • $\begingroup$ Hey sherlock, thank you for your response. I have a question that was too long to place in a comment if you can take a look at my latest "answer" below. Thank you very much again. $\endgroup$ – Ocean123 Oct 11 '14 at 18:38

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.