# Thread: Number of possible pair sets

1. ## Number of possible pair sets

Hello,
let's say we have k numbers from 1 to k and k is even. We want to know how many sets of pairs we are able to create with them. By a "pair set" we understand such a set that covers pairs created from all the k numbers given. (x, y) and (y, x) are treated as the same pair.
Example:
If k=2 then the answer is 1 since we can create only one pair which is (1,2).
If k=4 the answer is 3 since we can create 3 sets: ((1,2) and (3,4)) OR ((1,3) and (2,4)) OR ((1,4) and (2,3)).
If k=6 the answer is 15 since we can create 15 sets: ((1,2) and (3,4) and (5,6)) OR ((1,2) and (3,5) and (4,6)) OR ((1,2) and (3,6) and (4,5)) and so on.

I'm seeking a formula which would help me to calculate how many pair sets I am able to create with a given k numbers. Is there any?

2. ## question

Can a pair consist of the same number? For example (1,1).

3. Originally Posted by Glyper
Hello,
let's say we have k numbers from 1 to k and k is even. We want to know how many sets of pairs we are able to create with them. By a "pair set" we understand such a set that covers pairs created from all the k numbers given. (x, y) and (y, x) are treated as the same pair.
From your description and three examples, it appears that you asking ‘how many subsets of two are there?’

If that is correct the answer is: $\dbinom{k}{2}=\dfrac{k!}{2(k-2)!}$.

Example: $\dbinom{12}{2}=\dfrac{12!}{2(10!)}=\dfrac{12\cdot 11}{2}=66$.

Post Script.
Does it mean: “How many ways can we divide 2k items into k distinct pairs”?
Example; If we have eight items, how many ways can we divide the items into 4 distinct pairs?

If that is the question then the answer is different. It is $\dfrac{(2k)!}{2^k\cdot k!}$.

The answer to “If we have eight items, how many ways can we divide the items into 4 distinct pairs”? is
$\dfrac{8!}{2^4\cdot 4!}=105$.

4. Originally Posted by Plato
Post Script.
Does it mean: “How many ways can we divide 2k items into k distinct pairs”?
Example; If we have eight items, how many ways can we divide the items into 4 distinct pairs?

If that is the question then the answer is different. It is $\dfrac{(2k)!}{2^k\cdot k!}$.

The answer to “If we have eight items, how many ways can we divide the items into 4 distinct pairs”? is
$\dfrac{8!}{2^4\cdot 4!}=105$.

That's EXACTLY what I was looking for. Thank you very much, I couldn't have found it anywhere Excuse me for not clear enough explanation of the problem but I'm not very familiar with discrete mathematics vocabulary neither in my language nor in English Thank you very much once again.

5. Originally Posted by Glyper
Hello,
let's say we have k numbers from 1 to k and k is even. We want to know how many sets of pairs we are able to create with them. By a "pair set" we understand such a set that covers pairs created from all the k numbers given. (x, y) and (y, x) are treated as the same pair.
Example:
If k=2 then the answer is 1 since we can create only one pair which is (1,2).
If k=4 the answer is 3 since we can create 3 sets: ((1,2) and (3,4)) OR ((1,3) and (2,4)) OR ((1,4) and (2,3)).
If k=6 the answer is 15 since we can create 15 sets: ((1,2) and (3,4) and (5,6)) OR ((1,2) and (3,5) and (4,6)) OR ((1,2) and (3,6) and (4,5)) and so on.

I'm seeking a formula which would help me to calculate how many pair sets I am able to create with a given k numbers. Is there any?
If you observe your work more closely,
you'll see a pattern from which you can derive a formula.

k=2

(1,2) one pair

k=4

(1,2) and the other pair
(1,3) and the other pair
(1,4) and the other pair

That's 3 "sets of pairs"

k=6

(1,2) + (3,4) and the other pair
(1,2) + (3,5) and the other pair
(1,2) + (3,6) and the other pair

Repeat this for (1,3), (1,4), (1,5) and (1,6)

That's 5(3) "sets of pairs"

k=8

(1,2) + (3,4) + (5,6) and the other pair
(1,2) + (3,4) + (5,7) and the other pair
(1,2) + (3,4) + (5,8) and the other pair

In this sequence, beginning with (1,2).....5 can be paired with the three numbers 6, 7, 8

..... 3 can be paired with five others, 4, 5, 6, 7, 8.

1 can be paired with 7 others, 2, 3, 4, 5, 6, 7, 8.

Therefore the number of possible sets of pairs is 7(5)3.

For k=8, 10, 12 etc, the number of sets of pairs is (k-1)(k-3)(k-5)...5(3)1
which is the product of the odd numbers below k,
which is even.

To express this as a formula...

$\displaystyle\huge\frac{k(k-1)(k-2)(k-3)(k-4)(k-5)...5(4)3(2)1}{k(k-2)(k-4)..4(2)1}$

$=\displaystyle\huge\frac{k!}{2\left(\frac{k}{2}\ri ght)2\left(\frac{k-2}{2}\right)...2(3)2(2)2(1)}$

$=\displaystyle\huge\frac{k!}{2^{\frac{k}{2}}\left( \frac{k}{2}\right)!}$

which can be written neater if you let k represent the number of terms instead of pairs.

6. Another way to look at it

let m=k/2

consider two rows with 'm' seats one below the other.

consider a pairing arrangement for 'k' elements'.

fill the two rows with the pairs such that paired items sit in diffrent rows and are aligned.

once this is done - you can swap seats for the two elements in any of the 'm' pairs but still get the same pairing. so 2^m ways.
also you can permute 'm' pairs and still end up getting same pairing. so m! ways

in all we can arrange k elements in those seats in k! ways.

so required number of pairing arrangements is
k! / (2^m * m!)

If you observe your work more closely,
you'll see a pattern from which you can derive a formula.

k=2

(1,2) one pair

k=4

(1,2) and the other pair
(1,3) and the other pair
(1,4) and the other pair

That's 3 pairs

k=6

(1,2) + (3,4) and the other pair
(1,2) + (3,5) and the other pair
(1,2) + (3,6) and the other pair

Repeat this for (1,3), (1,4), (1,5) and (1,6)

That's 5(3) pairs

k=8

(1,2) + (3,4) + (5,6) and the other pair
(1,2) + (3,4) + (5,7) and the other pair
(1,2) + (3,4) + (5,8) and the other pair

In this sequence, beginning with (1,2).....5 can be paired with the three numbers 6, 7, 8

..... 3 can be paired with five others, 4, 5, 6, 7, 8.

1 can be paired with 7 others, 2, 3, 4, 5, 6, 7.

Therefore the number of possible sets of pairs is 7(5)3.

For k=8, 10, 12 etc, the number of sets of pairs is (k-1)(k-3)(k-5)...5(3)1

To express this as a formula...

$\displaystyle\huge\frac{k(k-1)(k-2)(k-3)(k-4)(k-5)...5(4)3(2)1}{k(k-2)(k-4)..4(2)1}$

$=\displaystyle\huge\frac{k!}{2\left(\frac{k}{2}\ri ght)2\left(\frac{k-2}{2}\right)...2(3)2(2)2(1)}$

$=\displaystyle\huge\frac{k!}{2^{\frac{k}{2}}\left( \frac{k}{2}\right)!}$

which can be written neater if you let k represent the number of terms instead of pairs.

7. OK, thank you very much. It seems that now I understand why the formula should look as it does

,
,

,

,

,

,

,

,

,

,

,

,

,

,

# distict pair in set

Click on a term to search for related topics.