Fijar enteros positivos $n$ y $k$ . Encuentre el número de $k$ -tuplas $(S_1, S_2,\dots, S_k)$ de subconjuntos $S_i$ de $\{1, 2, \dots , n\}$ con el $S_i$ son disjuntos.
Estoy buscando una manera de encontrar esto combinatoriamente, en lugar de generar funciones/recursiones. La idea de las bolas y las cajas parece el camino a seguir, pero el hecho de que cada caja necesite una bola excepto la "números no utilizados" caja me está causando dificultades.
Contamos el número de $(k+1)$ -tuplas de subconjuntos disjuntos por pares cuya unión es toda la $\{1,\dots,n\}$ . Es el número de funciones del conjunto $\{1,\dots,n\}$ al conjunto $\{1,\dots,k,k+1\}$ . Hay $(k+1)^n$ dichas funciones.
La "caja extra" $k+1$ obtiene los elementos de $\{1,\dots,n\}$ que no están en ninguno de los $S_i$ .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
