For a set $A$ with $n$ members, so that $A = \{1,2,3,...,n\}$. How can I group all subsets with two members, so that the intersection between any two subsets in the same group is an empty set and no subsets are used more than once?
For example if $n=4$, the six subsets with $2$ members, can be arranged like this:
Group-$1: (\{1,2\},\{3,4\})$
Group-$2: (\{1,3\},\{2,4\})$
Group-$3: (\{1,4\},\{2,3\})$
The other way of formating this problem, (That is if I have understood the concept correctly) Is to find a Perfect matching for a complete Graph and then removing the edges in the matching from the graph, and repeating the process until no edges are left.
Thanks
Here's one way to do it:
You need all the groups with doublets such that the intersection between any two subsets in the same group is an empty set.
So, let's choose any $4$ elements from the set $A$ that would belong to a group. This can be done in $^nC_4$ ways.
But, as you can notice from the example that you have given, that for each of these 4 elements, you not just get $1$ group but $3$ groups.
So, total number of groups is given by: $\bf3$ $\bf^nC_4$ $\bf \ \text{[or }3\binom n4]$.
Example: For $n=5$,
We'll get $3\binom 54=15\text { groups.}$ These are as follows:
$G_1=(\{1,2\},\{3,4\})$
$G_2=(\{1,2\},\{3,5\})$
$G_3=(\{1,2\},\{4,5\})$
$G_4=(\{1,3\},\{2,4\})$
$G_5=(\{1,3\},\{2,5\})$
$G_6=(\{1,3\},\{4,5\})$
$G_7=(\{1,4\},\{2,3\})$
$G_8=(\{1,4\},\{2,5\})$
$G_9=(\{1,4\},\{3,5\})$
$G_{10}=(\{1,5\},\{2,3\})$
$G_{11}=(\{1,5\},\{2,4\})$
$G_{12}=(\{1,5\},\{3,4\})$
$G_{13}=(\{2,3\},\{4,5\})$
$G_{14}=(\{2,4\},\{3,5\})$
$G_{15}=(\{2,5\},\{3,4\})$