3 questions from basic binominal theory

[threeder]

Homework Statement

1. Three people each select a different card from a single pack of 52 distinct cards. How mnay choices are possible if we record who selected which card, and if we forget who selected which card?
2. Three people each select a main dish from a menu of five items. How many choices are possible if we record who selected which dish and if we ignore who selected which dish?
3. Use (1+i)^n to prove that {\sum_{0\geq 2r\geq n}} (-1)^r \binom{n}{2r} = \begin{cases}(-4)^k = 0 &if ~n=4k,\\(-4)^k = 0 &if ~n=4k+1,\\0 &if ~n=4k+2,\\ \frac{1}{2}(-4)^{k+1} = 0 &if ~n=4k+3,\end{cases}

The Attempt at a Solution

Just want to make sure that I got first two right:
1. If we record who selected - 132600 and three times more if we forget.
2. If we record who selected - 125 and three time more if we forget
3. As for the third I am stuck. Tried to plug different values for n, but then got lost in algebra. I think there has to be a better way using the hint as well, right?

 

[Simon Bridge]

When you to section 3: The attempt at a solution, you should show the attempt rather than the answers you got.

The questions are asking about the difference between permutations and combinations.

What is your reasoning for getting 3x more possible choices if you don't care who got what?

eg. for the first one ... each person has to get a different card, so there are 52x51x50=132600 possible ways this could end up.
Just like you got, but I said how I got it you see?

This is if we care who gets what ... Alice picks one of the 52, Bob picks one of the remaining 51, and Carol has only 50 to pick one from.

But if we don't care who gets which card - why should this lead to more different ways and not less?
For instance, say the cards were 2,3,4 of hearts ... then A:2, B:3, C:4 would be indistinguishable from A:3, B:4, C:3 if you forgot about who got what.
Doesn't that mean you have fewer?

 

[threeder]

I rushed into things because I got the answer while creating this topic :) The difference is 3! because I simplified things a little bit too much, right?

 

[Simon Bridge]

The right number is 3! but it is not a "difference" and you haven't said if you multiply or divide by it or what or even why it is the right number.

You have to be prepared to show us your reasoning if you want to get the most out of this site.

 

[threeder]

OK, sorry for being so ignorant about it. Here was my initial line:

If we know who pick what, we know that the first one has 52 combinations of picking first card, second has 51 and the thirds has 50 which leads to 132600. Thought, I thought, since we do not know who picks what, hence the first one has 52, 51 and 50. On the other hand, the "first" card can be picked by the second or third person. There are 3!(52*51*51) of possibilities. But obviously, if you do not know who picks up what, there are actually (52*51*51)/3! possibilities, since we don't really care who ends up with which card. Same reasoning I suppose goes with the second.

Now, could anybody give me hints regarding the third? :)

 

[Simon Bridge]

I'm not sure on the notation under the sum ... it seems to be saying that 2r and n are negative. But note that 2r is an even number.

It looks like it is asking you to sum the binomial coefficients ... but alternating + and -.

So you get patterns off Pascals triangle like:
for the 1 3 3 1 row, you get 1-3+3-1=0
for the 1 4 6 4 1 row though, you get 1-4+6-4+1=2-8+6=0

... you need to relate this to your specific problem and check what that notation means.

 

[Dick]

OK, sorry for being so ignorant about it. Here was my initial line:

If we know who pick what, we know that the first one has 52 combinations of picking first card, second has 51 and the thirds has 50 which leads to 132600. Thought, I thought, since we do not know who picks what, hence the first one has 52, 51 and 50. On the other hand, the "first" card can be picked by the second or third person. There are 3!(52*51*51) of possibilities. But obviously, if you do not know who picks up what, there are actually (52*51*51)/3! possibilities, since we don't really care who ends up with which card. Same reasoning I suppose goes with the second.

Now, could anybody give me hints regarding the third? :)

I'm not quite sure what you want to prove. (-4)^k is not equal to zero. Try looking at the real part of (1+i)^n. Only even powers of i will contribute to that in the binomial expansion. That should be an ok hint.

 

[Simon Bridge]

We don't even know what k is supposed to be do we?
I suspect several different notations got mixed up there.

 

[Dick]

We don't even know what k is supposed to be do we?
I suspect several different notations got mixed up there.

Sure we do. Take the first case. If n=4k then if you know n you know k.

 

[Simon Bridge]

Ah - good point.

 

[threeder]

Sorry guys, I mixed things a little bit. The correct thing should have looked like this:

{\sum_{n\geq 2r\geq 0}} (-1)^r \binom{n}{2r} = \begin{cases}(-4)^k &if ~n=4k,\\(-4)^k &if ~n=4k+1,\\0 &if ~n=4k+2,\\ \frac{1}{2}(-4)^{k+1} &if ~n=4k+3,\end{cases}

Though, after Dicks' simple hint I was able to cope with this problem.

Thanks for your patience! :)