Combinatorics type

Question

I have this problem: From a set of numbers, such as $\{1,2,3,4,5,6\}$, a new set is created containing all the possible single pairs. ie. $\{12,13,14,15,16,\ldots\}$.

Another set contains all the dual pairs, such as $\{${12,34},{12,35},{12,36}$\ldots\}$. Note that each pair does not contain the same number.

The final triple pair set is, as $\{${12,34,56},{12,34,57}$,\ldots\}$.

I have constructed a program in C to do this, but I don't know what combinatorics type gives me the maximum number of the possible pairs in each stage for the dual and triple pairs.

Answer 1

I believe you are asking the following: Out of your set of $n$ elements, you want to pick $k$ pairs (subsets of size $2$), such that every two pairs are disjoint. You want to count the total number of ways you can do this.

So there are ${n\choose 2}$ ways to pick the first pair. There are $n-2$ elements remaining so there are ${n-2\choose 2}$ ways to pick the next pair. There are $n-4$ elements remaining, so there are ${n-4\choose 2}$ ways to pick the next pair, etc.

This gives ${n\choose 2}{n-2\choose 2}\cdots {n-2k\choose 2}$ sequences consisting of $k$ pairs, any two of which are disjoint. But you have counted too much. For example, if $k=2$, then $(\{1,2\},\{3,4\})$ and $(\{3,4\},\{1,2\})$ have each contributed one to that number. In fact, for any given $\{\{i_1,j_1\},\{i_2,j_2\},\ldots,\{i_k,j_k\}\}$, you have counted it $k!$ times (every arrangement of the pairs gives you a difference sequence). So the total number of possible sets consisting of $k$ pairs, any two disjoint, is $$\frac{{n\choose 2}{n-2\choose 2}\cdots {n-2k\choose 2}}{k!}.$$

Answer 2

Note that every dual pair shares an interesting property: it contains $4$ unique digits and a unique (relative to the rest of the set) ordering of said digits. Thus the number of dual pairs is the number of ways to choose $4$ digits from your starting set, multiplied by the number of ways to order said digits (because every four digit number can be split into two two-digit numbers, thus giving us the dual pair), divided by $2$ since every ordering can be flipped (e.g $12,36$ and $36,12$ are the same). Here the number of dual pairs (based on {$1,2,3,4,5,6$}) is $_6C_4*4!*\frac{1}{2}=\frac{_6P_4}{2}=180$. The same holds true for the triples pairs, only this time the three two-digit number units can be ordered in $3!=6$ ways, so simply substitute $6$ for $2$ in the above expression. Thus the number of triple pairs is $\frac{_6P_6}{6}=120$. If you want a general formula, the number of elements in an $n$-pair set, drawn from a set of $m$ unique digits, is $$\frac{_mP_{2n}}{m!}$$ with $m\geq2n$.