One of the ways that ex can be defined is as follows:
∞
_____
x \ i
e = \ x
/ -----
/____ i!
i=0
Since 1/e = e-1, that means that
∞
_____
-1 \ i
e = \ (-1)
/ ------
/____ i!
i=0
Now to figure out what the probability is that, a deck of n cards shuffled as described previously, the cards are in the same order as before. Let's start by considering the number of ways to shuffle n cards keeping exactly t of them in the same place. I'll call this function M(n,t). The number of ways to shuffle the cards and end up with no cards in the same place will then be M(n,0), and the probability of achieving this outcome will be M(n.0)/n!.
If you want t cards in the same place, you have to choose which t cards those are and arrange the rest of the cards in such a way that none of them are in the same position as before. The number of way of choosing t cards out of n is represented as:
/n\ \t/
and the number of ways to arrange the rest of the cards so that none of them are in the position they were in before is M(n-t, 0). So we know the following two facts about M(n,t):
n
______
\
M(n,t)= /n\ M(n-t,0) and \ M(n,t) = n!
\t/ /
/_____
t=0
So now for the proof.
The basic idea behind it was, OK, I've got these two sequences (the probability of no cards in the same place with n cards and the partial sums of the series expansion of e to the power of -1); I suspect they are the same; let's try to prove it using induction.
So let's start with the following lemma.
n
_____
\ i
Let P(n)= n! \ (-1)
/ ---- .
/____ i!
i=0
Then P(n) can be defined recursively as follows:
n-1
______
\
P(n) = n! - \ /n\ p(i) with p(0)=1.
/ \i/
/_____
i=0
P(0)=1. Yup. n-1
______
\
Let S(n) = n! - \ /n\ P(i). Then S(0)= 0!-0=1.
/ \i/
/_____
i=0
n-1 i
______ _____
\ \ j
S(n) = n! - \ [ /n\ (i! \ (-1) ]
/ \i/ / -----
/_____ /____ j!
i=1 j=0
n-1 i
______ ______ j
\ 1 \ (-1)
= n! ( 1 - \ -------- \ ------ )
/ (n-i)! / j!
/_____ /_____
i=0 j=0
S(n+1) S(n)
Then ------ - ---- equals
(n+1)! n!
n n-1
______ i ______ i
\ 1 _____ j \ 1 ____ j
1 - \ -------- \ (-1) - 1 + \ ------ \ (-1)
/ (n+1-i)! /____ ----- / (n-i)! /___ -----
/_____ j=0 j! /_____ j=0 j!
i=0 i=0
0 k-1 n
______ j _____ j ____ j
1 \ (-1) 1 \ (-1) 1 \ (-1)
= - ------ \ ----- - ... - -------- \ ----- - ... - -- \ -----
(n+1)! / j! (n+1-k)! / j! 1! / j!
/_____ /_____ /___
j=0 j=0 j=0
0 k-1 n-1
_____ j _____ j _____ j
1 \ (-1) 1 \ (-1) 1 \ (-1)
+ --- \ ----- + ... + ------ \ ----- + ... + -- \ -----
n! / j! (n-k)! / j! 1! / j!
/____ /____ /____
j=0 j=0 j=0
Combining like terms (all terms with 1/(n-k)! in them for each k), I get
0 1 k+1 n
1 (-1) 1 (-1) 1 (-1) 1 (-1)
- ------ ----- + --- ----- + ... + ------ ------- + ... + --- -----
(n+1)! 0! n! 1! (n-k)! (k+1)! 1! n!
n
______ i
\ (-1)
= - \ ----------
/ (n+1-i)!i!
/_____
i=0
n
______ i
So: S(n+1) S(n) \ (-1)
------ - ---- = - \ ----------
(n+1)! n! / (n+1-i)!i!
/_____
i=0
Solving for S(n+1), we get
n n
______ i ____
\ (-1) \ i
S(n+1) = (n+1)![S(n)/n! - \ ---------- ] = (n+1)S(n) - \ /n+1\ (-1)
/ (n+1-i)!i! / \ i /
/_____ /___
i=0 i=0
n+1
______
\ i n+1
= (n+1)S(n) - \ /n+1\ (-1) + (-1)
/ \ i /
/_____
i=0
n+1 n+1
= (n+1)S(n) - (1-1) + (-1) [by the binomial theorem]
n+1
= (n+1)S(n) + (-1)
n+1 n
_____ i _____ i
Now, P(n+1) P(n) \ (-1) \ (-1)
------ - ---- = \ ----- - \ -----
(n+1)! n! / i! / i!
/____ /____
i=0 i=0
n+1
(-1)
= -------
(n+1)!
n+1 n+1
So P(n+1) = (n+1)! [ P(n)/n! + (-1) /(n+1)! ] = (n+1)P(n) + (-1)
Since P(n) and S(n) can be derived from the same recursive formula, they are the same, and so my lemma is proved.
Now consider M(n,t), the number of ways to shuffle n cards keeping exactly t of them in the same place. As previously noted,
n
______
\
M(n,t)= /n\ M(n-t,0) and \ M(n,t) = n!
\t/ /
/_____
t=0
n n-1
______ ______
\ \
So M(n,0) = n! - \ /n\ M(n-t,0) = n! - \ /n\ M(i,0)
/ \t/ / \i/
/_____ /_____
t=1 i=0
Also, M(0,0)=1.
This is the same as the formula for P(n) in my Lemma, i.e.
n-1
______
\
P(n) = n! - \ /n\ P(i) with P(0)=1.
/ \i/
/_____
i=0
Hence, P(n) = M(n,0) for all n≥0, and so by my Lemma:
n
______
\ i
M(n,0) = n! \ (-1)
/ -----
/_____ i!
i=0
Now, the probability of getting no cards in the same place with n cards after a random shuffle is M(n,0)/n!, or
n
______
\ i
\ (-1)
/ -----
/_____ i!
i=0
As the number of cards gets larger, this probability approaches the limit
n
______ i
\ (-1) -1 1
lim \ ----- = e = --- .
n->∞ / i! e
/_____
i=0