¿cuál es el número de formas de dividir k elementos distintos en n recipientes distintos sin que ningún recipiente contenga exactamente un elemento?

Question

Estoy tratando de entender algo sobre esta pregunta que apareció en un examen que acabo de hacer. la pregunta es ¿cuál es el número de maneras de dividir k artículos distintos en n recipientes distintos sin que ningún recipiente tenga exactamente un artículo?

Esta es mi solución a la pregunta utilizando el principio de enclusión-exclusión |Ai|= el número de formas de dividir k-1 elementos en n-1 recipientes cuando el elemento i (para k+1>i>0) está en el n-ésimo recipiente = ${n[(n-1)]}^{(k-1)}$ porque hay n opciones para elegir la papelera y $(n-1)^{(k-1)}$ para elegir la ubicación de los otros elementos. así que ahora usando la fórmula de inclusión-exclusión obtenemos - $$|

Answer 1

Al mover el $r!$ en el denominador de $k \choose r$ para emparejarlo con el $\frac{n!}{(n-r)!}$ , queda inmediatamente claro que los sumandos son idénticos entre las dos sumas. La cuestión son los límites de la suma, y para ser técnicos, ambas respuestas son incorrectas, sin información adicional sobre la relación entre $n$ y $k$ . Realmente, ambas respuestas deben tener el límite superior de la suma igual al mínimo de $n$ y $k$ .

Supongamos que $k > n$ . Entonces en su argumento, si $k \geq r > n$ , usted está tratando de insistir en que $k$ artículos se pongan en $n$ bins tal que $r > n$ los artículos están en su propia papelera. Esto es imposible. Su fórmula tiene en cuenta esto, ya que tiene un término $(n-r)!$ que es indefinido para $r > n$ pero probablemente sea mejor asignar correctamente los límites de la suma.