Q:

Is there a combinatorial proof that $e$ is finite?

I'm looking for an integer $N$ and a combinatorial proof either that $(n+1)^n<Nn^n$ or that $\sum_{k=0}^n \frac{n!}{k!}<N\cdot n!$. By "combinatorial proof of $a<b$" I mean exhibiting explicit finite sets $A$ and $B$ with cardinalities $a$ and $b$, respectively, and either an injection $A\to B$ or a surjection $B\to A$.

A:

Let us consider the functions from $[1,n]$ to $[1,n+1]$: they clearly are $(n+1)^n$. Any function of this kind might attain or not the value $n+1$, and the number of function not attaining the value $n+1$ is precisely $n^n$.  Assume that $f:[1,n]\to [1,n+1]$ does attain the value $n+1$ and consider the chances for $f^{-1}(\{n+1\})$: this set may have $1,2,\ldots,n-1$ or $n$ elements, and there obviously are $\binom{n}{k}$ ways for picking $f^{-1}(\{n+1\})$ among the subsets of $[1,n]$, once established that $\left|f^{-1}(\{n+1\})\right|=k$. It follows that
$$\left|\{f:[1,n]\to[1,n+1]:\exists a\in[1,n]:f(a)=n+1\}\right| $$
equals
$$\binom{n}{1} n^{n-1} + \binom{n}{2} n^{n-2} + \binom{n}{3} n^{n-3} +\ldots + \binom{n}{n} $$
which is less than
$$ \frac{n^1}{1!}n^{n-1}+\frac{n^2}{2!}n^{n-2}+\frac{n^3}{3!}n^{n-3}+\ldots < n!\sum_{k\geq 1}\frac{1}{k!}. $$
On the other hand
$$ \sum_{k\geq 1}\frac{1}{k!}< 1+\frac{1}{2}+\sum_{k\geq 3}\frac{1}{2\cdot 3^{k-2}}=\frac{7}{4}$$
and this proves that $(n+1)^n < \frac{11}{4} n^n$.

A:

You can always do some artificial nonsense like saying that $\sum_{k=0}^n\frac{n!}{k!}$ is the number of ways to choose some amount $p$ of numbers out of $1,\dots,n$ and order them. Clearly, the number of ways to do it for $p=n,n-1$ are $n!$. As to all other $p\le n-2$, you can consider full orderings and remove the numbers up to and including the first one that violates an increasing order (so if the full ordering is 3546127, then you remove 354 and keep just 6127). This gives you a surjection from the set of all orderings to the set of choices and orderings of at most $n-2$ numbers, effectively showing that $e\le 3$. However, I really wonder what the point of this exercise is...

