Perms and combs question (1 Viewer)

tsoliman1 · Sep 4, 2016

Hi guys i tried to do this question but didnt work out.

http://prnt.sc/cdwvth

I tried doing (2nC2) where u choose 2 people out of 2n people for Pn but didnt know how to get Pn-1

thanks

InteGrand · Sep 4, 2016

tsoliman1 said:
Hi guys i tried to do this question but didnt work out.

http://prnt.sc/cdwvth

I tried doing (2nC2) where u choose 2 people out of 2n people for Pn but didnt know how to get Pn-1

thanks

$\noindent Note that $P_n$ is the no. of ways to assign two-player teams when there are a total of $2n$ people, for $n \geq 1$. So to form the recurrence, note that for a particular person in the group of $2n$ people (say Alice), there's $2n-1$ ways to assign their partner, and once this is assigned, there are (by definition) $P_{n-1}$ ways to assign partners for the remaining people (for $n\geq 2$). So by the multiplication rule of counting, the total no. of ways to assign pairs for the $2n$ people is $(2n-1)P_{n-1}$, so $P_n = (2n-1) P_{n-1}$, for $n\geq 2$.$

pikachu975 · Sep 4, 2016

InteGrand said:
$\noindent Note that $P_n$ is the no. of ways to assign two-player teams when there are a total of $2n$ people, for $n \geq 1$. So to form the recurrence, note that for a particular person in the group of $2n$ people (say Alice), there's $2n-1$ ways to assign their partner, and once this is assigned, there are (by definition) $P_{n-1}$ ways to assign partners for the remaining people (for $n\geq 2$). So by the multiplication rule of counting, the total no. of ways to assign pairs for the $2n$ people is $(2n-1)P_{n-1}$, so $P_n = (2n-1) P_{n-1}$, for $n\geq 2$.$

What about part b?

tsoliman1 · Sep 4, 2016

i dont get the Pn-1 way of assigning people. what do u mean by that?

tsoliman1 · Sep 4, 2016

nvm. what about part B??

InteGrand · Sep 4, 2016

pikachu975 said:
What about part b?

tsoliman1 said:
nvm. what about part B??

$\noindent Note that clearly $P_1 = 1$ (only one way to form the two-player team if there's only one pair to begin with). Now, we know $P_n = (2n-1)P_{n-1}$ for $n\geq 2$. Just keep plugging back into the recurrence, so $P_n = (2n-1)(2n-3)P_{n-2}$, since $P_{n-1} = (2n-3) P_{n-2}$. So $P_n = (2n-1)(2n-3)(2n-5)P_{n-3}$. Keep going back till you get to $P_{1} = P_{n-(n-1)}$. So that gives us $P_n = (2n-1)(2n-3)(2n-5)\ldots (2n-(2(n-1)-1))P_1 \Rightarrow P_n = (2n-1)(2n-3)(2n-5)\ldots 3 \cdot 1$ (as $P_1 = 1$).$

$\noindent To see that this is the same as the desired answer, insert a $2n$, a $2n-2 = 2(n-1)$, a $2n-4 = 2(n-2),\ldots$, a $4 = 2\times 2$ and a $2 = 2\times 1$ in each gap between the odd numbers (and starting from the left of the first number $(2n-1)$). This makes the number become $(2n)!$, but we have to of course divide by these terms we multiplied in, which was clearly $2n \times (2n-2)\times (2n-4)\times \cdots \times 4 \times 2 = 2^n (n\times (n-1)\times (n-2)\times \cdots \times 2\times 1) = 2^n \cdot n!$. So the answer is $P_n = \frac{(2n)!}{2^n n!}$.$

InteGrand · Sep 4, 2016

Perms and combs question (1 Viewer)

tsoliman1

Member

InteGrand

Well-Known Member

pikachu975

Premium Member

tsoliman1

Member

tsoliman1

Member

InteGrand

Well-Known Member

InteGrand

Well-Known Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)