¿Cómo abordar este problema de conteo?

Question

Deje $n ≥ 1$ ser un número entero. Una función de $f : \{1, 2, \ldots , n\} \to \{1, 2, \ldots, n\}$ se considera "válida", si existe al menos un entero $i$ $\{1, 2, \ldots, n\}$ que $f(i) = i$.

Determinar el número de funciones válidas.

Estoy teniendo problemas para comprender lo que esta pregunta está pidiendo. Ni siquiera estoy seguro de cómo acercarse a este. Podría alguien que me señale en la dirección correcta? ¿Qué técnica debo utilizar para acercarse a ella?

Supongo que lo que me confunde más, es esta línea aquí. Ya que no la entiendo.

Una función de $f : \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\}$

Answer 1

Para cada una de las $n$ elementos del dominio de la función $f$, debemos elegir un elemento de la gama. Hay $n$ posibilidades para elegir en la gama. Esto significa que el número total de funciones de $\{1,2,\,...\,,n\}$ $\{1,2,\,...\,,n\}$ $$n^n$$

Sin embargo, tenemos una restricción que su función tiene al menos un punto fijo.

Vamos a contar el número de funciones con no hay puntos fijos y restar este de el número total de funciones.

Para cada elemento del dominio, una de las opciones de la gama no está permitido.

Tenemos $n-1$ opciones para cada una de las $n$ elementos del dominio.

Esto significa que el número de funciones de $\{1,2,\,...\,,n\}$ $\{1,2,\,...\,,n\}$sin puntos fijos es

$$(n-1)^{n}\,$$

El número de funciones de $\{1,2,\,...\,,n\}$ $\{1,2,\,...\,,n\}$con al menos un punto fijo es igual al número total de funciones de$\{1,2,\,...\,,n\}$$\{1,2,\,...\,,n\}$, menos el número de funciones con sin puntos fijos. Esta es nuestra respuesta final:

$$n^n - (n-1)^n$$

Answer 2

Que $A_i$ denotan el número de funciones que $f(i) = i$. Necesitamos $\left|\cup_{i=1}^n A_i\right|$. Tenga en cuenta que $|A_i| = n^{n-1}$. También $|A_i \cap A_j| = n^{n-2}$. Así por el principio de exclusión de la inclusión, $$\left|\cup_{i=1}^n A_i\right| = \binom{n}{1}n^{n-1} - \binom{n}{2}n^{n-2} +\cdots =n^n - (n-1)^n

Answer 3

Hay $n^n$ funciones $\{1,\dots,n\}\to\{1,\dots,n\}$ en total, teniendo cada argumento $i\in\{1,\dots,n\}$ $n$ opciones.

Hay $(n-1)^n$ funciones que son no válidos, teniendo estas funciones para cada argumento $i\in\{1,\dots,n\}$ $n-1$ opciones (la opción '$i$' cae).

Por lo tanto son funciones válidas de $n^n-(n-1)^n$.