Estoy buscando un entero $N$ y una combinatoria pruebas de que $(n+1)^n<Nn^n$ o que $\sum_{k=0}^n \frac{n!}{k!}<N\cdot n!$. Por "combinatoria prueba de $a<b$" me refiero a exhibir explícita finito de conjuntos de $A$ e $B$ con cardinalidades $a$ e $b$, respectivamente, y una inyección $A\to B$ o un surjection $B\to A$.
Respuestas
¿Demasiados anuncios?
Roger Hoover
Puntos
56
Consideremos las funciones de $[1,n]$ a $[1,n+1]$: lo que está claro que $(n+1)^n$. Cualquier función de este tipo podría alcanzar o no el valor de $n+1$, y el número de la función de no alcanzar el valor de $n+1$ es, precisamente, $n^n$. Suponga que $f:[1,n]\to [1,n+1]$ obtener el valor de $n+1$ y considerar las posibilidades de $f^{-1}(\{n+1\})$: este conjunto puede tener $1,2,\ldots,n-1$ o $n$ elementos, y no son, evidentemente, $\binom{n}{k}$ formas para la selección de $f^{-1}(\{n+1\})$ entre los subconjuntos de a$[1,n]$, una vez establecido que la $\left|f^{-1}(\{n+1\})\right|=k$.
De ello se sigue que
$$\left|\{f:[1,n]\to[1,n+1]:\exists a\in[1,n]:f(a)=n+1\}\right| $$ es igual $$\binom{n}{1} n^{n-1} + \binom{n}{2} n^{n-2} + \binom{n}{3} n^{n-3} +\ldots + \binom{n}{n} $$ que es menos $$ \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!}. $$ En el otro lado $$ \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}$$ y esto demuestra que $(n+1)^n < \frac{11}{4} n^n$.
alberta
Puntos
16
Siempre se puede hacer algo de artificial absurdo como decir que el $\sum_{k=0}^n\frac{n!}{k!}$ es el número de formas de elegir una cierta cantidad $p$ de los números de $1,\dots,n$ y el fin de ellos. Claramente, el número de maneras de hacerlo para $p=n,n-1$ se $n!$. Como a todos los demás $p\le n-2$, se puede considerar completo orden y quitar los números hasta e incluyendo el primero que viola una orden creciente (de modo que si el total de pedidos es 3546127, a continuación, quite 354 y mantener 6127). Esto le da una surjection desde el conjunto de todos los ordenamientos para el conjunto de decisiones y órdenes de la mayoría de las $n-2$ números, mostrando efectivamente ese $e\le 3$. Sin embargo, me pregunto cuál es el punto de este ejercicio es...
