Show equality by combinational argument

M

Mahonroy

New member
Joined
Sep 4, 2009
Messages
16
Hello,
I came across a problem (its in a discrete structures class, but doing some probability now), and I was confused on how to go about doing it, so was seeing if I could get some advice. I guess I'm a little confused to whats going on with it, and not sure how to show by combinational arguments, and algebraic manipulation. Any help is greatly appreciated, thanks!
 

Attachments

  • 3problem2.jpg
    3problem2.jpg
    26.1 KB · Views: 102
For the algebraic manipulation part, use the definition of combinations. \(\displaystyle \frac{n!}{r!(n-r)!}\)

Therefore, for the left side, by subbing in 2n for n and 2 for r we arrive at \(\displaystyle n(2n-1)\)

Now, the right side should be the same. \(\displaystyle 2\binom{n}{2}=n(n-1)\)

Now, can you finish?. See what I mean?. Just add n^2 to the right side and you should get n(2n-1)
 
Hello, Mahonroy!

Here's part (b) . . .

If n is a positive integer, then the following equality holds:

. . \(\displaystyle {2n\choose n} \:=\:2{n\choose2} + n^2\)

Show it in two ways:
. . (a) by a combinatorial argument
. . (b) by an algebraic manipulation.
Click to expand...

\(\displaystyle {2n\choose2} \quad=\quad\frac{(2n)!}{2!(2n -2)!} \quad=\quad \frac{(2n)(2n-1)}{2} \quad=\quadn(2n-1)\)


\(\displaystyle 2{n\choose2} + n^2 \quad=\quad2\cdot\frac{n!}{2!(n-2)!} + n^2 \quad=\quad2\cdot\frac{n(n-1)}{2} + n^2\)

. . . . . . \(\displaystyle = \quad n(n-1)+n^2 \quad=\quad n^2 - n + n^2 \quad=\quad 2n^2 - n \quad=\quad n(2n-1)\)

 
Hello again, Mahonroy!

I think I have an argument for part (a) . . .


\(\displaystyle \text{We have }2n\text{ objects . . . an even number.}\)
\(\displaystyle \text{If we take them two-at-a-time, there are: }{2n\choose2} \text{ possible pairs.}\)



\(\displaystyle \text{Divide the }2n\text{ objects into two equal groups, }n\text{ in each group.}\)

\(\displaystyle \text{For convenience, let one group consist of A's . . . the other consist of B's.}\)

. . . \(\displaystyle \boxed{\begin{array}{c} \\ n\text{ A's} \\ \\ \end{array}} \qquad \boxed{\begin{array}{c}\\ n\text{ B's} \\ \\ \end{array}}\)

\(\displaystyle \text{How many pairs of objects can be chosen?}\)

\(\displaystyle \text{Two A's: }\:\text{Taking the A's two-at-a-time, there are: }{n\choose2}\text{ pairs.}\)

\(\displaystyle \text{Two B's: }\:\text{Taking the B's two-at-a-time, there are: }{n\choose2}\text{ pairs.}\)

\(\displaystyle \text{One A, one B: }\:\text{Taking one of the }n\text{ A's and one of the }n\text{ B's, there are: }n^2\text{ pairs.}\)


\(\displaystyle \text{Therefore, there are: }\:2{n\choose2} + n^2\text{ possible pairs.}\)

 
You must log in or register to reply here.
Top