cs150

Open full view…

I tried hard to do q4 from

Nayema Laboni
Sat, 07 Nov 2015 20:53:53 GMT

ex midterm but could not do it, can you please give me any hint?!

alexey
Sat, 07 Nov 2015 21:29:14 GMT

You are taliking about Example Midterm - Problem 4: Come up with a double counting argument for the identity: *( 2n )! = ( 2n choose n ) · n! · n!* Am I correct? Can you tell me what is the meaning of *( 2n )!* ? In terms of counting, what is the meaning of the factorial of a number _2n_? It is a the number of ways to arrange _2n_ distinct items. Can you come up with an argument, showing that the right-hand side of the identity, *(2n choose n) · n! · n!* also describes a procedure to do the same thing, it also arranges _2n_ items.

Nayema Laboni
Sat, 07 Nov 2015 22:20:31 GMT

if I arrange 2n items, do I get 2n.n?

alexey
Sun, 08 Nov 2015 01:51:30 GMT

I'd say the question is not *what* you get.. If you arrange 2n items, you just get a permutation of those 2n items.. No more, no less. The question is *how* 2n things can be permuted. What sequence of choices is necessary for achieving that. In particular, what sequence of choices is described by the following counting formula: *( 2n choose n ) · n! · n!*. This is not just a formula, this is an _algorithm_ for permuting 2n items. You need to see, why this is the case. )