Deck of Cards Revisited...

In Quiz 2 Problem 2.
A deck of cards numbered 1, ... , 2n.
And then there are two cases. 
We asked "what are the possible start states".
So now we can ask some counting, series, and probability questions :)


a)  How many distinct start states are there?

(2n)!

b)  In how many "start" states that case 1 applies?

The only start state that case 1 does not apply is 
1, 2, 3 ,4, 5, ..., 2n 

So the answer will be (2n)! - 1 

c) How many possible states in total?

All possible sequences of length 2k, for k = 1, ... , 2n.
No. of sequences of length 2k:

n!/(n-2k)!

Total: \sum_1^n n!/(n-2k)!

d) Show that the summation given in c is  approaches 

n! (e + e^-1)/2 

when n is big. (or show that it's < n!(e+e^{-1})/2

This is because (e+e^{-1})/2= 1+ 1/2! + 1/4! +1/6! ... 

e) What's the probability that we'll be done exactly after n steps?
(assuming a random start state)

This happens when we case 2 is encountered all the time.

At each step, each case happens with probability 1/2 if 
it was case 2 in the previous step
(actually i'm not sure sure about this  for case 1, but it seems to be true too)
So the probability that we're done after n steps is exactly (1/2)^n.