Results 1 to 6 of 6

Math Help - Ordered Pairings

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    23

    Ordered Pairings

    How many ordered pairs (A,B), where A,B are subsets of {1, 2, . . . , n}, are there such that |A \cap B| = 1?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2009
    Posts
    4

    Solution

    We can prove this via straightforward counting techniques and some elementary algebra. You want to first count all the A sets and then for each of those A sets you want to count all possible B sets such that their intersection comes out to be exactly equal to 1. So first we choose A set from n elements. Then we choose the element we want to be common in the both sets. Then from the remaining elements we just choose the B set. So from this we get the following summation.

    \sum_{k=1}^{n}\binom{n}{k}\cdot\binom{k}{1} \cdot 2^{n-k-1}

    = \sum_{k=1}^{n}\frac{n!}{k!\cdot(n-k)!} \cdot k \cdot2^{n-k-1}

    = 2^{n-1}\cdot \sum_{k=1}^{n}\frac{n!}{(k-1)!\cdot(n-k)!} \cdot2^{-k}

    = 2^{n-1}\cdot n\cdot \sum_{k=1}^{n}\frac{(n-1)!}{(k-1)!\cdot(n-k)!} \cdot2^{-k}


    = 2^{n-1}\cdot n\cdot \sum_{k=1}^{n}\binom{n-1}{k-1} \cdot2^{-k}

    = 2^{n-1}\cdot n\cdot \sum_{k=0}^{n-1}\binom{n-1}{k} \cdot2^{-k}

    We can now observe that the formula for the binomial theorem can be used to simplify the summation with  a = 1 and b = \frac{1}{2}

    = 2^{n-1}\cdot n\cdot \left( 1+\frac{1}{2}   \right)^{n-1}

    = 2^{n-1}\cdot n\cdot \left(\frac{3}{2}   \right)^{n-1}

    = n\cdot 3^{n-1}

    Hence Proved.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by hans.kruger11 View Post
    We can prove this via straightforward counting techniques and some elementary algebra. You want to first count all the A sets and then for each of those A sets you want to count all possible B sets such that their intersection comes out to be exactly equal to 1. So first we choose A set from n elements. Then we choose the element we want to be common in the both sets. Then from the remaining elements we just choose the B set. So from this we get the following summation.
    \sum_{k=1}^{n}\binom{n}{k}\cdot\binom{k}{1} \cdot \color{red}2^{n-k-1}
    Surely it should be \sum_{k=1}^{n}\binom{n}{k}\cdot\binom{k}{1} \cdot \color{blue}2^{n-k}
    In the sum what happens if k=n?
    The A set is the whole set while the B set is a singleton. Hence there n of those.
    Last edited by Plato; October 12th 2009 at 07:44 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2009
    Posts
    4
    Indeed. I guess that was a typo-error.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by hans.kruger11 View Post
    We can prove this via straightforward counting techniques and some elementary algebra. You want to first count all the A sets and then for each of those A sets you want to count all possible B sets such that their intersection comes out to be exactly equal to 1. So first we choose A set from n elements. Then we choose the element we want to be common in the both sets. Then from the remaining elements we just choose the B set. So from this we get the following summation.

    ...

    = n\cdot 3^{n-1}
    Once you have seen the answer, it's easy to derive it more quickly. There are n possibilities for the one element that is in A\cap B. For each of the other n–1 elements, there are three possibilities: (i) the element belongs to A, (ii) the element belongs to B, (iii) the element belongs to neither A nor B. Total number of choices is therefore n\cdot 3^{n-1}. (I would not have noticed that without seeing hans.kruger11's solution!)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2009
    Posts
    4
    That is a much clearer way to put it and makes much more intuitive sense. Good work opalg
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of different pairings of 2n objects.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 21st 2011, 10:33 AM
  2. Probability pairings
    Posted in the Statistics Forum
    Replies: 3
    Last Post: October 29th 2009, 07:08 AM
  3. Set ordered
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: November 23rd 2008, 12:43 PM
  4. Marriage Pairings
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: June 16th 2008, 06:26 PM
  5. Pairings problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 17th 2007, 06:36 AM

Search Tags


/mathhelpforum @mathhelpforum