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.
- 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.
- 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.\]