Results 1 to 6 of 6

Thread: 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
    21,374
    Thanks
    2689
    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; Oct 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
    10
    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: Nov 21st 2011, 10:33 AM
  2. Probability pairings
    Posted in the Statistics Forum
    Replies: 3
    Last Post: Oct 29th 2009, 07:08 AM
  3. Set ordered
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Nov 23rd 2008, 12:43 PM
  4. Marriage Pairings
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Jun 16th 2008, 06:26 PM
  5. Pairings problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 17th 2007, 06:36 AM

Search Tags


/mathhelpforum @mathhelpforum