Can a pair consist of the same number? For example (1,1).
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?
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: .
Example: .
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 .
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?
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.
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...
which can be written neater if you let k represent the number of terms instead of pairs.
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!)