http://i220.photobucket.com/albums/d...rb599/help.jpg

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.

Printable View

- Jan 29th 2008, 12:49 PMJrb599Party Question
http://i220.photobucket.com/albums/d...rb599/help.jpg

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. - Jan 29th 2008, 01:37 PMPlato
The number of ways to arrange 2n people into n

**named**groups of two is $\displaystyle

\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!):

$\displaystyle \frac{{\left( {2n} \right)!}}{{2^n \left( {n!} \right)}}$. - Jan 29th 2008, 01:42 PMangel.white
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:

$\displaystyle 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:

$\displaystyle 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 $\displaystyle 2^4$ I would have the denominator. Basically I made it look like this: $\displaystyle 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:

$\displaystyle 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

$\displaystyle 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 $\displaystyle 2^{n-1}$ and you get $\displaystyle 2^n$ and multiply the n by the $\displaystyle (n-1)!$ and because it is the next consecutive integer in the factorial, it will become $\displaystyle n*(n-1)! = n!$ so:

modify the formula

$\displaystyle f(n) = \frac{(2n-1)!}{(n-1)!*2^{n-1}}*\frac{2n}{2n} = \frac{(2n)!}{(n)!*2^{n}}$

final formula

$\displaystyle f(n) = \frac{(2n)!}{(n)!*2^{n}}$ - Jan 29th 2008, 02:18 PMJrb599
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:

$\displaystyle

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

$

Technically

$\displaystyle

f(n) = (2n-1) * f(n-1)

$

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. - Jan 29th 2008, 07:32 PMangel.white
I think the answer will be

$\displaystyle 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:

$\displaystyle \bigcirc_1$

$\displaystyle \bigcirc_2 \bigcirc_3$

$\displaystyle \bigcirc_4 \bigcirc_5$

Lets choose circle1 to be the lonely person, then we have 4 circles left, which we can use our formula$\displaystyle 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:

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

And because (2n)! * (2n+1) = (2n+1)!

$\displaystyle 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 ^_^ - Jan 30th 2008, 04:03 AMJrb599
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.