0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't understand the question. What do you mean by "type"? And if you want all the "dual pairs", then what do you mean by "maximum number" of possible pairs? And what do you mean by "in each stage"? I don't see any stages. Question needs a lot of rewording. $\endgroup$ – Gerry Myerson Nov 7 '14 at 11:51
  • $\begingroup$ This is a combinataric problem like the problem with the cards which gives the combinations without repetition and there is an equation like (nk)=n!k!/(n−k)!,if 0≤k≤n.For the first single pairs i calculate with this type how many combinations can be made from this set of number.But for the next stage of the dual and triple and so on pairs i cant find the equation to calculate how many combinations will be made. $\endgroup$ – Merk Oner Nov 7 '14 at 12:06
1
$\begingroup$

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!}.$$

$\endgroup$
  • $\begingroup$ Thanks this is the answer.I have written a code in c and the following results are exact with the last equation.I have a set of 20 elements and the number of single disjoint pairs are 190,then the number of double disjoint pairs are 14535 and then the number of triple dishoint pairs are 581400.So the problem solved $\endgroup$ – Merk Oner Nov 7 '14 at 14:21
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ The problem is solved in the next answer.Thanks a lot for the support. $\endgroup$ – Merk Oner Nov 7 '14 at 14:21

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.