##### Euler’s number $$e$$, the base of the natural logarithm, manifests itself in various mathematical contexts, sometimes unexpectedly. In the following you will read an example of what I mean.

Consider the sequence of the first $$n$$ natural numbers $$\{1,2,\dots,n\}$$ and suppose to count all permutations in which no element occupies the original position, i.e. $$1$$ is not in the first position, $$2$$ is not in the second position, and so forth. What is the number of all permutations of this kind you can construct?

We will first construct a recursive formula for $$\mathcal C_n$$, the number of valid permutations of length $$n$$. For the numerical examples that follow, we will take $$n = 5$$. Observe that a valid permutation can be constructed in two ways.

1. We can start from a valid permutation of length $$n-1$$ and place number $$n$$ in the position occupied by any number between $$0$$ and $$n-1$$. Putting then the latter number in the last position will not violate the rule. For example, starting from $\{3,4,2,1\},$ we can place number $$5$$ in the first position and get the valid sequence $\{5,4,2,1,3\}.$ Since by definition the number of valid permutations of length $$n-1$$ is $$\mathcal C_{n-1}$$, and considering that each of them generates $$n-1$$ sequences of length $$n$$, we obtain, with this procedure, $$(n-1) \mathcal C_{n-1}$$ valid sequences.
2. We can also start from a non valid sequence of length $$n-1$$, provided that only one number occupies a non valid position. In this case we generate one valid sequence of length $$n$$ by placing the new element in that postition. E.g., from $\{2,4,\boxed{3},1\},$ we can generat the valid sequence $$\{2,4,5,1,3\}$$. You can verify that the total number of length-$$n-1$$ sequences with one invalid element is $$(n–1)\mathcal C_{n-2}$$. Why?

It is straightforward, also, to check that the permutations obtained with these two methods are all distinct, so that in the end we get

\begin{equation}\mathcal C_n = (n-1)\left(\mathcal C_{n-1} + \mathcal C_{n-2}\right),\tag{1}\label{eq1149:1}\end{equation}

which is valid for $$n>2$$. The recursion has initial values $$\mathcal C_1 = 0$$ and $$\mathcal C_2 = 1$$.

We look now for a non recursive expression of $$\mathcal C_n$$. In order to do so, let us have a look at a table that summarizes the values of $$n$$ and $$\mathcal C_n$$, together with the overall number of permutations $$n!$$ and their ratio $$\frac{\mathcal C_n}{n!}$$, for $$n$$ up to 6.

$\newcommand\T{\Rule{0pt}{1em}{.3em}}\begin{array}{|c|c|c|c|}\hline n&\mathcal C_n&n!&\frac{\mathcal C_n} {n!}\\ \hline\hline 2 & 1 & 2 & \mathbf{1/2}\\ \hline 3 & 2 & 6 & \mathbf{1/3=1/2\boxed{\bf -1/6}}\\ \hline 4 & 9 & 24 & \mathbf{9/24=1/3\boxed{\bf +1/24}}\\ \hline 5& 44 & 120 & \mathbf{44/120 = 9/24\boxed{\bf -1/120}}\\ \hline 6 & 265 & 720 & \mathbf{265/720 = 44/120\boxed{\bf + 1/720}}\\\hline \end{array}$

Do you recognize any pattern in the boxed elements in the last column? Can you use them to derive a recursive formula for $$\mathcal C_n$$ which only depends on $$\mathcal C_{n-1}$$? From here, as a next step, you should be able to make an hypothesis about a non recursive formula for the number of valid permutations.

By considering the alternating sign boxed elements in the table, a reasonable hypothesis should be

\begin{equation}\mathcal C_n = n! \cdot \sum_{k=2}^{n}\frac{(-1)^k}{k!}.\tag{2}\label{eq1149:2}\end{equation}

I leave you as an exercise to verify, using induction, that this intuition is in fact correct. Base cases are given in the table already. Thus, starting from definition \eqref{eq1149:1}, you need to demonstrate that if the assertion \eqref{eq1149:2} is true for, say, $$n_0-1$$ and $$n_0-2$$, then it is true also for $$n_0$$.

Using definition of $$e$$

$e^x = \sum_{k=0}^{+\infty} \frac{x^k}{k!},$

we deduce that

$\lim_{n\to+\infty} \frac{\mathcal C_n}{n!} = \frac{1}{e}.$

Furthmore the alternating series

$S_n = \sum_{k=2}^{n} \frac{(-1)^k}{k!}$

allows us to maximize the absolute value of the difference between the $$n$$th partial sum and the limit of the series. In fact we have

$\left|\frac{1}{e}-S_n\right| < \left|S_{n+1}-S_n\right| = \frac{1}{(n+1)!}.$

Multuplying by $$n!$$ and recalling that $$\mathcal C_n = n! S_n$$ yields

$\frac{n!}{e} -\frac{1}{n+1} < \mathcal C_n < \frac{n!}{e} + \frac{1}{n+1}.$

For $$n\geq 1$$ we can therfore write

$\frac{n!}{e} -\frac{1}{2} < \mathcal C_n < \frac{n!}{e} + \frac{1}{2}.$

This means that $$\mathcal C_n$$ is the closest integer to $$\frac{n!}{e}$$, i.e.

$\mathcal C_n = \left\lfloor \frac{n!}{e} + \frac{1}{2}\right\rfloor.$