5

I have a problem counting all the possible way of "pairing" 2 people in a group of N people (let's assume N is even). Example:

The professor wants the students to work in pairs (groups of two).

In how many ways the students could pairs ?

I have seen that the answer is $$\frac{N!}{2^{N/2}*\frac{N}{2}!} $$

So, the way i understand it: it is the way of all possible combination (N!) divided by $$2^{N/2}$$ because ... I don't know (that is the reason of the question) ... And divided by $$(N/2)!$$ because of the permutation.

So, could you explain me why this division by $$2^{N/2}$$ ?

Also, what are the probability for 2 people (let's say student1 and student 2), to be in the same group ?

Community
  • 1
azerty
  • 153
  • 1
  • 1
  • 5

3 Answers3

6

Since $N$, the number of students, is even, let's call it $2M$.

The formula you quote can be obtained using the following reasoning. First let us divide the set of people not into pairs, but into pairs with designated leader, who gets to wear a special leader shirt.

We can choose the set of leaders in $\dbinom{2M}{M}$ ways. Now assign a follower to each leader. This can be done in $M!$ ways.

So the number of pairings with designated leader is $\dbinom{2M}{M}M!$, which simplifies to $\dfrac{(2M)!}{M!}$.

But if we want to divide into plain groups of two, we have overcounted by a factor of $2^M$. For if $D$ is the number of democratic groups of $2$, then the number of groups-with-leader is $2^MD$. This is because for any division into democratic groups, there are $2^M$ ways to choose the persons in the democratic division who will wear the leader shirts. Thus $$2^M D=\frac{(2M)!}{M!},$$ and now solving for $D$ we have our count.

Remark: The following is another way to count the number of divisions into groups, this time directly. Line up the students in order of student number, or weight, or beauty.

For concreteness, assume there are $12$ people in the group. The first student in the list can select her partner in $11$ ways. For each such way, the first still unpartnered person in the lineup can select her partner in $9$ ways. Once this has been done, the first unpartnered person in the list can select her partner in $7$ ways. And so on. So the number of divisions into groups is $$(11)(9)(7)(5)(3)(1).$$

To get back to the formula of the OP, multiply top and bottom by the "missing" numbers, so by $(12)(10)(8)(6)(4)(2)$. On top, we get $12!$.

At the bottom, we get $(12)(10)(8)(6)(4)(2)$. Taking out the $2$'s, we get $(2^6)(6!)$.

The same idea works in general. The number of groups of $2$ when there are $2M$ students is $(2M-1)(2M-3)(2M-5)\cdots(5)(3)(1)$.

André Nicolas
  • 507,029
5

You need to define what $n$ is, which is $\frac N2$. There are many ways to see this. One is to imagine that you line up all $N$ students in a line, then take the first two to be the first pair, then next two for the second pair, and so on. You can make the line $N!$ ways. Unfortunately, we have counted the same arrangement many ways. If we swap the pairs around some other way, we get the same pairing: this is a factor $\frac N2!$ In addition, we can swap the first and second student in a pair, which is a factor $2^{\frac N2}$. The overall number is then $$\frac {N!}{2^{\frac N2}\frac N2!}$$ The probability for students 1 and 2 to be paired is just the chance that 2 is paired with 1, which is $\frac 1{N-1}$

Ross Millikan
  • 374,822
-1

If we have group from n students, the first has (n-1) possible partner, the second has (n-2) because we already accounted the possibility to be a partner with the first, and so on until the later one don't has any possibility because we already accounted all the possibilities to be a partner with all the group members, So the result of all possibilities is (n-1)+(n-2)+...+1 or 1+2+3+4+....+(n-1) which is a simple sum of terms of arithmetic serie: the first term + the later term cros the number of terms by two: ((n-1)+1)*(n-1)/2=n(n-1)/2 and the general case of k from n is n!/((n-k)!k!) note : here AA can't be a pair and AB can not be accounted if BA is accounted

Karim
  • 1