18
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I have a vague memory that $e$ can be expressed as the expectation of some "nice" random variable; perhaps this would be a good direction to go in. $\endgroup$ – Omnomnomnom Nov 5 '18 at 18:34
  • 4
    $\begingroup$ $\frac{1}{e}$ is the asymptotic density of derangements in $S_n$. $\endgroup$ – Jack D'Aurizio Nov 5 '18 at 18:35
  • $\begingroup$ @JackD'Aurizio interesting idea, but I think that to use this, one would need to establish that $$ \frac 1e = \left( \sum_{k=0}^n \frac{n!}{k!}\right)^{-1} \overset != \sum_{k=0}^n (-1)^k \frac{n!}{k!} $$ $\endgroup$ – Omnomnomnom Nov 5 '18 at 18:38
  • $\begingroup$ It follows by expanding $\left(1-\frac{1}{n}\right)^n$ through the binomial theorem, then applying the dominated convergence theorem. $\endgroup$ – Jack D'Aurizio Nov 5 '18 at 18:39
  • $\begingroup$ Perhaps there is something you can do with Cayley's formula. $\endgroup$ – Jair Taylor Nov 5 '18 at 20:23
4
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks, this is helpful. I expected the first inequality to be more difficult, because to pack an $n$-cube into $N$ slightly smaller $n$-cubes requires moving around a lot of low-dimensional surface mass. $\endgroup$ – MTyson Nov 15 '18 at 13:56
  • 2
    $\begingroup$ @MTyson the 1st inequality is similarly easy using fedja's trick. Consider any $n$-vector in $[1,n]^n$ and look for an initial segment up to & including the first violation of increasing order. If the numbers $S$ in the segment are distinct, then interpret them as indices $j\in S$ where $f(j) = n+1$, and interpret the rest of the vector as the other $f(k)$ values (i.e. for $k \in [1,n] - S$) listed in order. This map covers all $f:[1,n]\rightarrow [1,n+1]$ where $f$ achieves $n+1$ at least twice. (There are another $n^n f$ achieving $n+1$ once and another $n^n f$ not achieving $n+1$.) $\endgroup$ – antkam Nov 15 '18 at 16:04
9
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ The first part is a nice combinatorial description of the binomial theorem applied to $(n+1)^n$. However, I don't see how to prove the $7/4$ bound combinatorially. $\endgroup$ – MTyson Nov 5 '18 at 20:05
  • $\begingroup$ @MTyson - would you accept FINITE summations as combinatorial? If I understand correctly, the bounds in this Answer still work if all summations are only up to $k \le n$. I.e. the no. of terms is still dependent on $n$, but at least it's not infinite any more... $\endgroup$ – antkam Nov 9 '18 at 18:58
  • $\begingroup$ @antkam I don't have a problem with finite summations, but I do want to avoid fractions. A bound like $\sum_{k=0}^n 2^k\le 2^{n+1}$ can be made combinatorial by explicitly packing $k$-cubes of side length $2$ into an $n+1$-cube of side length $2$. Jack's bound could be truncated to the first $n$ terms and be multiplied through by $n!$ to match the second inequality in my question, but this leaves the fractions $n!/3^k$ that can't be interpreted combinatorially. $\endgroup$ – MTyson Nov 9 '18 at 19:49
  • $\begingroup$ @MTyson it should be pretty trivial to combinatorially prove the geometric sum formula with base 3 (instead of 2) and with a finite number of terms. If you accept that, then the only missing ingredient is you need to accept "integers $a > b \implies$ rational numbers $1/b > 1/a$"... However, if you wont accept non-integers, then your original puzzle remains unsolved. $\endgroup$ – antkam Nov 9 '18 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.