Number of possible pair sets

**Glyper** · August 3rd 2010, 05:34 AM

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?

**quiney** · August 3rd 2010, 05:48 AM

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

**Plato** · August 3rd 2010, 06:17 AM

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

If that is not what you are asking, please explain.

Post Script.
I have been thinking about this problem.
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$ .

Is that the correct reading?

**Glyper** · August 3rd 2010, 11:06 AM

Originally Posted by Plato

Post Script.
I have been thinking about this problem.
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$ .

Is that the correct reading?

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.

**Archie Meade** · August 3rd 2010, 01:22 PM

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.

**aman_cc** · August 3rd 2010, 10:18 PM

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!)

Originally Posted by Archie Meade

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.

**Glyper** · August 4th 2010, 11:27 PM

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

Thread: Number of possible pair sets

LinkBack

Thread Tools

Display

Number of possible pair sets

question

Similar Math Help Forum Discussions

Proving a pair of integers are not prime in a particular number system

Closest pair of sets

Number of ways to pair up group

Voronoi tesselation for a pair of convex sets

number of pair of integers (x,y) satisying an equation

Search Tags