Can a pair consist of the same number? For example (1,1).
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.
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 that is correct the answer is: .
If that is not what you are asking, please explain.
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 .
The answer to “If we have eight items, how many ways can we divide the items into 4 distinct pairs”? is
Is that the correct reading?
you'll see a pattern from which you can derive a formula.
(1,2) one pair
(1,2) and the other pair
(1,3) and the other pair
(1,4) and the other pair
That's 3 "sets of pairs"
(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"
(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...
which can be written neater if you let k represent the number of terms instead of pairs.
Another way to look at it
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!)