In how many ways can $n$ letters can be placed in $m$ $(m>n)$ addressed envelopes, such that no letter is put in the correct envelope?

Question

I am confused on a problem. It goes as following:

In how many ways can $n$ letters can be placed in $m$ $(m>n)$ addressed envelopes, such that no letter is put in the correct envelope?

Here is the solution given in textbook (for $n=4$ and $m=5$)

Can anyone provide any simple approach?
I tried to do it by breaking into several parts. But it didn't worked any good and I ended up making more trouble.

Answer 1

Formalize the question:

How many injections $f$ are there from $\{1,2,\dots, n\}$ to $\{1,2,\dots, m\}$ such that $\forall j: f(j)\neq j$.

I assume this is what is meant, i.e. there is exactly one correct envelope for each letter (and the extra envelopes are addressed to some other letters).

We use the notation $[k]=\{1,2,\dots, k\}$ and $(k)_r = k(k-1)\dots(k-r+1)$ for the falling factorial.

Let's solve this with the inclusion-exclusion principle. Denote

$$A_j = \{f:[n] \to [m] \text{ injection s.t. } f(j)=j\}, \space j=1,2,\dots, n.$$

We are looking for the size of $(\bigcup_{j=1}^n A_j)^C$. By inclusion-exclusion

$$| \bigcup_{j=1}^n A_j | = \sum_{J\subset [n], J \neq \emptyset} (-1)^{|J|+1}|\bigcap_{j\in J} A_j| = \sum_{r=1}^n (-1)^{r+1} {n \choose r} (m-r)_{n-r} $$

Here we enumerated the sets $J$ by their cardinality $r$ and notice each such intersection of $A_j$'s has the same size $(m-r)_{n-r}$ because we're fixing $r$ elements and picking $n-r$ from the remaining $m-r$ (and order matters). And there are ${n \choose r}$ such $J$'s.

We then subtract this from the total number of injections since we were interested in the complement. The formula can be turned into

$$\sum_{r=0}^n (-1)^r {n \choose r} (m-r)_{n-r}.$$

For $n=4, m=5$, this gives $5*4*3*2 - {4 \choose 1}4*3*2 + {4 \choose 2}3*2 -{4 \choose 3}2 + 1 = 53.$

---

PS. I tested it with this Sagemath code

import itertools

def bruteF(n, m):
    ret = 0
    for c in itertools.combinations(range(m), n):
        for p in itertools.permutations(c):
            #print (p)
            if all(p[j]!=j for j in range(n)):
                ret += 1
                #print (p)
    return ret

def f(n, m):
    return sum((-1)^(r)*binomial(n, r)*falling_factorial(m-r, n-r)
              for r in range(n+1))


n = 4
m = 5
print(f(n,m))
print ("Bruteforce:")
print(bruteF(n,m))