Results 1 to 6 of 6

Math Help - Party Question

  1. #1
    Junior Member
    Joined
    Aug 2007
    Posts
    30

    Party Question




    I did this by hand

    for n =1, I get 1 way

    n=2, 3 ways

    n=3, 15 ways.

    Any help or advice on how to look at this problem.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,792
    Thanks
    1687
    Awards
    1
    The number of ways to arrange 2n people into n named groups of two is <br />
\left( {\begin{array}{c}   {2n}  \\  {\underbrace {2,2, \cdots ,2}_n}  \\ \end{array}} \right) = \frac{{\left( {2n} \right)!}}{{2^n }}

    But these are not named groups so divide by (n!):
    \frac{{\left( {2n} \right)!}}{{2^n \left( {n!} \right)}}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by Jrb599 View Post



    I did this by hand

    for n =1, I get 1 way

    n=2, 3 ways

    n=3, 15 ways.

    Any help or advice on how to look at this problem.
    I figured it out, but it's not easy to explain how, I just worked on it for a bit :/

    Lets assume all the people are males so I can call them "he" without feeling bad.

    First I came up with the recursive definition, which is relatively easy, you know that the first person can pair with any of the people except himself (2n-1 options) and that will occupy person1 and person1's partner, leaving 2 fewer people, which leaves n-1 pairs. And then you can do that same step again. Now you know they are multiplied, because for every option that any of them chooses, the others can choose every available option. (if you are hazy on this, maybe take a look at trees, or just think about it for a while, or graphically draw the first few pairs, I drew n=3 on my paper to make sure there were really 15 options and I wasn't getting confused)

    So my recursive formula looked like this:
    f(n) = (2n-1) * f(n-1)

    Then I did 5 iterations, and saw the pattern:
    f(1) = 1
    f(2) = 3*1 = 3
    f(3) = 5*3*1 = 15
    f(4) = 7*5*3*1 = 105
    f(5) = 9*7*5*3*1 = 945

    And so the pattern is that it multiplies by the next consecutive odd integer. I played around with this for a while, and saw that I could look at it like this:
    f(5)=\frac{9*8*7*6*5*4*3*2*1}{8*6*4*2}

    The numerator is simply 9! which is (2n-1)! and so I looked at the denominator for a while, and realized that if I divided those numbers by 2, I would have 4! Which means that if I multiplied 4! by 2^4 I would have the denominator. Basically I made it look like this: 8*6*4*2  =4(2)*3(2)*2(2)*1(2) = (4*3*2*1)(2*2*2*2) = 4!*2^4 = (n-1)!*2^{n-1}

    So now I had a formula for the numerator and the denominator, I put them together to get this:
    f(n) = \frac{(2n-1)!}{(n-1)!*2^{n-1}}

    Then I checked it and it worked. (I didn't prove it, though, so you might want to do that)

    ------------

    EDIT: After reviewing Plato's answer, I realized that you can modify our formula like this:

    initial formula
    f(n) = \frac{(2n-1)!}{(n-1)!*2^{n-1}}

    Now if we multiply by 2n on the top and bottom, we are multiplying by 1, and thus not changing the problem. This would cause the numerator to become 2n! instead of (2n-1)! because 2n is the next consecutive integer in the factorial. Then on the bottom, take the 2 and multiply it by the 2^{n-1} and you get 2^n and multiply the n by the (n-1)! and because it is the next consecutive integer in the factorial, it will become n*(n-1)! = n! so:

    modify the formula
    f(n) = \frac{(2n-1)!}{(n-1)!*2^{n-1}}*\frac{2n}{2n} = \frac{(2n)!}{(n)!*2^{n}}

    final formula
    f(n) = \frac{(2n)!}{(n)!*2^{n}}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Aug 2007
    Posts
    30
    Angel White... That was amazing help

    I actually had the formula

    1*3*5*---*n,

    couldn't think of how to write it.

    Thanks so much!

    Btw, your explanation was awesome

    If wanted to do this for 2n+1 people, and 1 person was left out, then I would get:

    <br /> <br />
f(n) = \frac{(2n+1)!}{(n)!*2^{n}}<br />

    Technically


    <br />
f(n) = (2n-1) * f(n-1)<br />

    Is a right answer to 2n people, correct?




    Also,

    Angel_white, I don't think your logic works for the 2n+1 case.

    f(n) = (2n+1 -2)*f(n-1) isn't right, also I did -2 cause you have to include he can't pair with the guy you excluded.
    Last edited by Jrb599; January 29th 2008 at 06:49 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by Jrb599 View Post
    Angel White... That was amazing help

    I actually had the formula

    1*3*5*---*n,

    couldn't think of how to write it.

    Thanks so much!

    Btw, your explanation was awesome

    If wanted to do this for 2n+1 people, and 1 person was left out, then I would get:

    <br /> <br />
f(n) = \frac{(2n+1)!}{(n)!*2^{n}}<br />

    Technically


    <br />
f(n) = (2n-1) * f(n-1)<br />

    Is a right answer to 2n people, correct?




    Also,

    Angel_white, I don't think your logic works for the 2n+1 case.

    f(n) = (2n+1 -2)*f(n-1) isn't right, also I did -2 cause you have to include he can't pair with the guy you excluded.
    I think the answer will be
    g(n) = \frac{(2n)!}{(n)!*2^{n}}(2n+1)

    It took me a while to see that, but here is why:
    Lets use n=2 for our example. We will have two pairs plus one person for 5 people total, lets represent them with circles like this:
    \bigcirc_1

    \bigcirc_2 \bigcirc_3

    \bigcirc_4 \bigcirc_5

    Lets choose circle1 to be the lonely person, then we have 4 circles left, which we can use our formula f(n) = \frac{(2n)!}{n!*2^{n}} to determine. So if circle1 is lonely, then there will be 3 possibilities because f(2)=3

    Now lets choose circle2 to be the lonely circle, there will again be 4 dots with 3 possible matchups.

    Now circle3,4, &5 will have the same pattern, so what we realize is that our previously discovered formula will be invoked once for every circle attending our party. Since there are (2n+1) circles, we can simply multiply the previous formula by (2n+1) to arrive at the correct answer. This gives us the new equation:

    g(n) = \frac{(2n+1)*(2n)!}{n!*2^{n}}

    And because (2n)! * (2n+1) = (2n+1)!
    g(n) = \frac{(2n+1)!}{n!*2^{n}}

    I am relatively confident that this is correct, but not 100% sure.

    EDIT: And upon looking back at your post, I realize that this is the same answer you gave. Good job, you found it much easier than I did ^_^
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Aug 2007
    Posts
    30
    Angel white, if you see my post early, that's what I got too so I would take it as right also. It took me a while to see why, but your post is much better at understanding the even way. Plato's posted helped me see it the odd way. The only reason why I asked for you to confirm is because I thought that you would offer a really good observation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. at the party
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 12th 2010, 09:54 AM
  2. A party was held..
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 20th 2010, 04:43 PM
  3. Represent a party using graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 30th 2009, 02:48 AM
  4. Near the end of a party, everyone shakes hands...
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: January 25th 2007, 03:19 PM
  5. Students At the Party
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: January 17th 2007, 06:08 PM

Search Tags


/mathhelpforum @mathhelpforum