Contando el número de surjections.

Question

Cómo muchas de las funciones de $\{1,2,3,\ldots,n\}$ $\{A,B,C\}$son surjections? $n \geq 3$

Intento

Tenía la esperanza de contar el número de surjections por el tratamiento de la $A,B,C$ como papeleras, y contar el número de maneras de llenar con $1,2,3,\ldots,n$ tal de que no los contenedores están vacíos. Esto es equivalente a poner dos "separator" barras entre las $n$ números o $n-1 \choose 2$.

Sin embargo, creo que me falta un paso a paso aquí: antes de poner en el separador de barras, que debo permutate la $n$ elementos. Así, se multiplican por $n!$.

El orden de los elementos en los mismos recipientes no importa. Por lo que debe ser dividido por el número de permutaciones de los elementos en cada una de las bandejas. Esto es donde estoy atascado.

Información Adicional

Hice la pregunta a mí mismo. Siéntase libre de modificar la pregunta en una forma soluble, si es muy difícil/complicado.

Answer 1

Has hecho un muy buen inicio: su primera idea no funciona, pero es razonable tratar, y que ha manchado la dificultad con él. Lo que quiere ahora es una inclusión-exclusión en el argumento. Hay $3^n$ funciones en total. $2^n$ de ellos son funciones de$\{1,\dots,n\}$$\{A,B\}$, la falta de $C$ en total, así que tenemos que tirar de ellos hacia fuera. También hay $2^n$ funciones que se pierda $B$ $2^n$ que se pierda $A$, por lo que nuestra mejor aproximación al número de surjections es $3^n-3\cdot2^n$.

Por desgracia, ahora hemos ido por la borda. La función que envía cada $k\in\{1,\dots,n\}$$A$, por ejemplo, ha sido expulsado dos veces, una vez para no golpear a $B$ y de una vez para no golpear a $C$. Lo mismo va para los otros dos constantes de funciones. Tenemos que tirar cada uno de ellos en vez, de modo que en la red nos hemos echado cada uno de ellos sólo una vez, no dos veces. La cifra revisada de surjections es entonces

$$3^n-3\cdot2^n+3=3\left(3^{n-1}-2^n+1\right)\;.\tag{1}$$

Un poco de pensamiento debe convencer de que no son necesarios ulteriores y que $(1)$ es por lo tanto el número deseado.

Answer 2

Haciendo caso omiso de suprayectividad, hay $3^n$mapas de $\{1,2,\ldots,n\}\to \{A,B,C\}$. Debemos restar el $2^n$ mapas que ar sólo mapas $\{1,2,\ldots,n\}\to \{A,B\}$, también el $2^n$mapas de $\ldots\to \{A,C\}$ y $2^n$ $\ldots\to \{B,C\}$ todos los mapas. Pero ahora nos hemos restado demasiado: lo tres mapas constante $f(x)=A$, $f(x)=B$ y $f(x)=C$ cuando restan dos veces (por ejemplo, $f(x)=A$ como un mapa $\to\{A,B\}$ y también como un mapa $\{A,C\}$). En resumen hay por lo tanto $$ 3^n-3\cdot 2^n+3$ $ sobreyectiva mapas $\{1,2,\ldots,n\}\to\{A,B,C\}$.

Answer 3

Esta en mi idioma (Portugués) es "combinção completa" y es equivalente a resolver\begin{equation} x + y + z = n \end{equation} donde $x,y,z$ entero $\ge 0$ $x,y,z \ge 1$ (a surjectve) porque puede representa las soluciones por un esquema de bolas y rastros. Haciendo así, $x=1 +a, y=1+b$ y $z = 1+c$, tenemos $a+b+c =n+3$. Por lo tanto, la solución es $CR^{n+3}_{3}= \binom{(n+3)+(3)-1}{n+3}= \binom{n+5}{n+3}$. ($CR^{n+3}_{3}$ es notación en mi libro en Portugués).