Results 1 to 7 of 7

Math Help - Number of possible pair sets

  1. #1
    Junior Member
    Joined
    Aug 2010
    Posts
    41

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Aug 2010
    Posts
    32

    question

    Can a pair consist of the same number? For example (1,1).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,824
    Thanks
    1717
    Awards
    1
    Quote Originally Posted by Glyper View Post
    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?
    Last edited by Plato; August 3rd 2010 at 08:10 AM. Reason: Post Script.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Aug 2010
    Posts
    41
    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by Glyper View Post
    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.
    Last edited by Archie Meade; August 5th 2010 at 02:36 AM. Reason: small typo
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    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!)

    Quote Originally Posted by Archie Meade View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Aug 2010
    Posts
    41
    OK, thank you very much. It seems that now I understand why the formula should look as it does
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: May 16th 2011, 07:54 PM
  2. Closest pair of sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 12th 2010, 11:14 AM
  3. Number of ways to pair up group
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: June 27th 2010, 07:52 PM
  4. Voronoi tesselation for a pair of convex sets
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: January 24th 2010, 11:28 AM
  5. Replies: 3
    Last Post: July 30th 2009, 12:19 AM

Search Tags


/mathhelpforum @mathhelpforum