Il numero di Nepero \(e\), base dei logaritmi naturali, si manifesta in diversi ambiti della matematica, in modo talvolta, a mio modo di vedere, inaspettato. Ecco un esempio di ciò che intendo.
Considera la sequenza ordinata dei primi \(n\) numeri naturali \(\{1,2,\dots,n\}\) e immagina di contare tutte le possibili permutazioni nelle quali nessuno dei numeri occupa la sua posizione “originaria”; ovvero \(1\) non si trova nella prima posizione, \(2\) non si trova nella seconda posizione, e così via. Quante sono le possibili permutazioni che riesci a costruire?
Come primo passo, genereremo una formula ricorsiva per il calcolo delle permutazioni “valide”, che denominiamo \(\mathcal C_n\). Per gli esempi numerici prenderemo \(n=5\). Osserviamo che una sequenza valida di lunghezza \(n\) può essere costruita in due modi, come segue.
- Si può partire da una sequenza valida di lunghezza \(n-1\) e inserire il numero \(n\) al posto di un qualsiasi numero tra \(1\) e \(n-1\), che possiamo spostare, non violando la regola, in ultima posizione. Partendo da \[\{3,4,2,1\},\] possiamo inserire il \(5\), per esempio, in prima posizione e ottenere la sequenza valida \[\{5,4,2,1,3\}.\] Dal momento che le sequenze valide di lunghezza \(n-1\) sono per definizione \(\mathcal C_{n-1}\) e che ognuna di esse ne genera \(n-1\) valide di lunghezza \(n\), avremo un totale di \((n-1)\mathcal C_{n-1}\) sequenze, che possono essere costruite con questa procedura.
- Possiamo anche partire da una sequenza non valida di lunghezza \(n-1\), purché un elemento soltanto occupi la posizione della sequenza originaria. Inseriremo allora il nuovo elemento al suo posto, mettendo l’elemento prima in posizione non valida in coda. Per esempio, la sequenza \[\{2,4,\boxed{3},1\},\] genera così la sequenza valida \[\{2,4,5,1,3\}.\] Le sequenze lunghe \(n-1\) da cui possiamo partire, in questo caso sono \((n-1)\mathcal C_{n-2}\). Sai dire il perché? Ognuna di essere genera una sola sequenza valida di lunghezza \(n\).
Puoi verificare che le sequenze ottenute con questi due procedimenti sono tutte distinte; per cui concludiamo che
\begin{equation}\mathcal C_n = (n-1)\left(\mathcal C_{n-1} + \mathcal C_{n-2}\right),\tag{1}\label{eq1064:1}\end{equation}
valida per \(n> 2\) e con valori iniziali \(\mathcal C_1 = 0\) e \(\mathcal C_2 = 1\).
Cerchiamo ora un’espressione non ricorsiva. Confrontiamo nella tabella seguente, al variare di \(n\), il numero \(\mathcal C_n\) con il numero totale di permutazioni possibili, ovvero \(n!\), e con il loro rapporto \(\frac
{\mathcal C_n} {n!}\).
\[\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}\]
Riconosci un pattern nei termini incorniciati dell’ultima colonna? Puoi utilizzarli per scrivere \(\mathcal C_n\) in funzione soltanto di \(\mathcal C_{n-1}\)? Come passo successivo, osservando con attenzione l’espressione che hai scritto, dovresti essere in grado di ipotizzare una formula non ricorsiva per \(\mathcal C_n\).
I termini a segno alterno nell’ultima colonna fanno pensare, dunque, di poter esprimere \(\mathcal C_n\) come
\begin{equation}\mathcal C_n = n! \cdot \sum_{k=2}^{n}\frac{(-1)^k}{k!}.\tag{2}\label{eq1064:2}\end{equation}
Puoi verificare la correttezza di questa intuizione con un procedimento induttivo. Ti invito a farlo come esercizio, prima di proseguire la lettura. I casi base sono forniti direttamente dalla tabella qui sopra. Ricorda che, partendo dalla \eqref{eq1064:1} avrai bisogno di verificare che se la \eqref{eq1064:2} è vera per, diciamo, \(n_0-1\) e \(n_0-2\) allora essa è vera anche per \(n=n_0\).
Dalla definizione di \(e^x\)
\[e^x = \sum_{k=0}^{+\infty} \frac{x^k}{k!},\]
deduciamo che
\[\lim_{n\to+\infty} \frac{\mathcal C_n}{n!} = \frac{1}{e}.\]
Inoltre la serie a segni alterni
\[S_n = \sum_{k=2}^{n} \frac{(-1)^k}{k!}\]
ci consente di massimizzare la differenza in modulo tra l’\(n\)-esima somma parziale e il limite della serie, in quanto
\[\left|\frac{1}{e}-S_n\right| < \left|S_{n+1}-S_n\right| = \frac{1}{(n+1)!}.\]
Moltiplicando per \(n!\) e utilizzando il fatto che \(\mathcal C_n = n! S_n\), si ricava
\[\frac{n!}{e} -\frac{1}{n+1} < \mathcal C_n < \frac{n!}{e} + \frac{1}{n+1},\]
che, per \(n\geq 1\), implica
\[\frac{n!}{e} -\frac{1}{2} < \mathcal C_n < \frac{n!}{e} + \frac{1}{2}.\]
Ciò significa che \(\mathcal C_n\) è l’intero più vicino a \(\frac{n!}{e}\), ovvero, in formula,
\[\mathcal C_n = \left\lfloor \frac{n!}{e} + \frac{1}{2}\right\rfloor.\]