Explicación de la recursión para el número de supresiones

Question

Tengo una pregunta acerca de la recursividad de la cantidad de surjections de $\{1,\ldots,n\}$ a $\{1,\ldots,k\}$: $$\mathrm{Sur}(n,k) = k \cdot \mathrm{Sur}(n-1,k-1) + k \cdot \mathrm{Sur}(n-1,k).$$ Mi explicación de esto es: Nos fijamos en el elemento $k$ a partir de $\{1,\ldots,k\}$. $k$ puede ser golpeado por $1$ elemento de $\{1,\ldots,n\}$, o $2$ o más.

En el primer caso, nos quite ese $k$ y que el elemento de $\{1,\ldots,n\}$, y nos quedamos con $n-1$ elementos en el dominio, y $k-1$ elementos en el rango. También tiene que ser un surjection, por lo que podemos recoger en $\mathrm{Sur}(n-1,k-1)$ maneras.

En el segundo caso, se elimina ese elemento del dominio, y nos quedamos con $n-1$ elementos en el dominio, y $k$ elementos en el rango. Así que podemos escoger el número de surjections en $\mathrm{Sur}(n-1,k)$ maneras.

Pero, ¿por qué es que el factor de $k$ hay en ambos casos?

Answer 1

No contabilizó las$n$ opciones diferentes de elementos asignados a$k$. En su primer caso, eso lleva a un factor de$n$. El segundo caso es más complicado porque también tiene una opción de los elementos asignados a$k$ para eliminar. Para evitar estas complicaciones, puede derivar la recurrencia como en la respuesta de polkjh.

Answer 2

Deje $f(n)$ ser la imagen de elemento $n$.

Si $n$ es el único elemento con $f(n)$ como es la imagen, entonces podemos eliminar a $n$ $f(n)$ y ver el $S(n-1,k-1)$. Pero hay $k$ formas para recoger $f(n)$. Así que esto explica el por $k.S(n-1,k-1)$ maneras.

Si $n$ no es el único elemento con $f(n)$ como es la imagen, entonces podemos simplemente eliminar las $n$ y ver el $S(n-1,k)$. Y $f(n)$ puede volver a ser elegido en $k$ diferentes maneras. Esto le da otra $k.S(n-1,k)$ surjections.

En su argumento, en el caso de $k$ tiene exactamente un elemento de golpearlo, puedes escoger el elemento en $n$ maneras. Por lo que cuentas para $n.S(n-1,k-1)$ surjections. Pero el otro caso es más complicado. Si hay $r$ elementos que apunta a $k$, $\binom{n}{r}$ formas de seleccionar los $r$ elementos. Entonces podemos eliminar los $r$ elementos y $k$ y ver el $S(n-r,k-1)$. No podemos simplemente eliminar uno de estos elementos y mirar surjections de $n-1$ $k$ya que estos no son cualquier general surjections (en estos surjections, usted necesita $r-1$ elementos que apunta a $k$).

Esto le da

$$ S(n,k) = \sum _{i=1}^{n} \binom{n}{r} S(n-r,k-1) $$

Answer 3

Esto es sólo mi impresión rápida, pero parece ser todo acerca de las permutaciones.

En primer lugar, tenemos nuestros conjuntos $A = \{a_1,...,a_n\}$, $B = \{b_1,...,b_k\}$ y algunos $f:A \rightarrow B$.

Trate de pensar acerca de lo que sucede a $a_n$ en todos los posibles surjections.

Mi pensamiento está más abajo en el spoiler:

Si $a \epsilon A$, $b \epsilon B$ y dejamos $f(a)=b$, entonces hay dos posibilidades para nuestros surjections: algunos otros $a' \epsilon A$ también se asigna a $b$ o no. En el caso de que $f(a)$ únicamente se asigna a $b$, hay claramente $Sur(n-1,k-1)$ maneras de hacer esto.

Entonces

En el otro caso, $f(a')=b=f(a)$ para algunos arbitraria $a' \epsilon A$. Es decir, nuestro surjection es $f(a)=b$ junto con algunos surjection $g: A \backslash a \rightarrow B$. Por lo que el número de maneras de hacer esto debería ser $Sur(n-1,k)$.

Así

El número de surjections donde $f(a)=b$ debe venir a $Sur(n-1,k-1) + Sur(n-1,k)$. Pero, evidentemente, la de arriba arugment es simétrica a través de todos los $b$--de los cuales hay $k$ de ellos, así que multiplicar por $k$.

Q. E. D.