Sea $A$ un multiconjunto con $n$ elementos distintos donde cada elemento ocurre exactamente dos veces. ¿Cuántas formas hay de particionar $A$ en $k$ submulticonjuntos no vacíos (sin etiqueta) (denotados $T(n,k)$)?
Mi enfoque sería algo similar a los Números de Stirling. Para cada elemento $x \in A$, podemos incluir ambas copias de $x$ en un conjunto, o incluirlas en dos conjuntos distintos. Por lo tanto, podemos definir etiquetas de conjuntos (partes), como subconjuntos unitarios y de dos elementos de $\{1,2,3,...k\}$. En total hay $k + {{k}\choose{2}} = {{k+1}\choose{2}}$ etiquetas diferentes que podemos asignar a cada elemento. (Nota: Dividimos el resultado final por $k!$ porque las etiquetas no importaban originalmente) Los elementos donde ambas copias están incluidas en el mismo conjunto están etiquetados con un unitario, y si un elemento ocurre en dos conjuntos, se etiqueta con un conjunto de dos elementos.
Por ejemplo, la partición de $\{\{a,a,c\},\{b,b,c\}\}$ de $\{a,a,b,b,c,c\}$ puede ser definida por una clase de equivalencia o función como $f(a)=\{1\}$, $f(b)=\{2\}$, $f(c)=\{1,2\}$.
La idea básica es contar el número de funciones $f:A_s \xrightarrow{} S$ tal que $|\cup_{x \in A_s} f(x)| = k$. Aquí, $A_s$ es el conjunto que contiene solo una de cada elemento en $A$, y $S = \{ s \in \mathcal{P}(\{1,2,3,...k\})\ \mid |s| = {1,2} \}$.
Dado que $|S|={{k+1}\choose{2}}$, y $|A_s|=n$, tenemos $|S|^{|A_s|} = {{k+1}\choose{2}}^{n}$ funciones diferentes para elegir.
Sin embargo, algunas funciones pueden no cumplir nuestra restricción inicial de que $|\cup_{x \in A_s} f(x)| = k$. Podemos usar la inclusión-exclusión para esto (similar a cómo se derivan los Números de Stirling de Segundo Tipo).
Lo que obtengo es algo como
$$ T(n,k) = \frac{1}{k!} \sum_{i=0}^{k} (-1)^{k-i} {{k}\choose{i}} {{i+1}\choose{2}}^n $$
Creo que la fórmula está equivocada, y no puedo entender por qué. Por ejemplo, con $k=2$, tenemos $T(n,2) = \frac{1}{2}(3^n - 2)$. Sé que debería ser $\frac{1}{2}(3^n - 1)$ porque cada subconjunto de $A$ tiene un complemento, pero un conjunto es su propio complemento, y necesitamos "agregar" un par a la colección, luego dividir por 2.
Para $k=3$, tenemos $T(n,k) = \frac{1}{6}(6^n - 3^{n+1} + 3)$, pero los cálculos manuales muestran que esto es incorrecto. (Por ejemplo, $T(3,3) = 23$, pero debería ser $26$, y $T(4,3) = 176$, pero debería ser $183$).
¿Alguien podría por favor darme pistas sobre lo que me falta aquí? Realmente estoy intentando entenderlo por mi cuenta, o al menos comprender por qué mis cálculos son incorrectos. ¡Gracias de antemano!
Edición:
Me di cuenta de mi error (gracias a usuario2661923).
Básicamente, tenía el conteo correcto, pero para particiones ordenadas en lugar de particiones desordenadas. Básicamente, si olvidamos el orden, algunas particiones tienen $k!$ copias, otras tienen menos de $k!$ duplicados. Entonces todo lo que necesitamos hacer para corregir el conteo es "agregar" suficientes duplicados (para esas permutaciones que tienen menos de $k!$ copias).
Por ejemplo, si $k=2$ usando la fórmula anterior (ignora el $\frac{1}{k!}$), obtenemos $T(n,k) = 3^n-2$. Sin embargo, habrá una partición de la forma $\{X, X\}$ (donde $X$ es un multiconjunto). Solo se incluye una copia de esta partición, por lo que necesitamos "agregar" otra copia de ella, lo que lleva a $3^n-1$, en lugar de $3^n-2$, que luego podemos dividir por 2, para obtener el valor correcto de $T(n,2) = (3^n-1)/2$
Si $k=3$, entonces inicialmente obtenemos $T(n,3) = 6^n - 3^{n+1} + 3$. Las particiones de la forma $\{X,X,Y\}$ solo tienen $3$ copias incluidas, por lo que necesitamos "agregar" tres más. Cada elemento se asigna a $\{X,X\}$ o $\{Y\}$, pero no todos pueden asignarse a los mismos conjuntos, por lo que esto da $2^n-2$ copias diferentes que necesitamos agregar (no olvides que esto da $3$ copias adicionales). Dado que teníamos originalmente $3$ etiquetas diferentes, necesitamos multiplicar este resultado por $3$. Esto da $$T(n,3) = (6^n - 3^{n+1} + 3 + 3(2^n-2))/6 = (6^n - 3^{n+1} + (3)2^n - 3)/6$$
El caso para $k=4$ es más complicado, pero después de verificar manualmente todas las particiones posibles que necesitan copias adicionales, obtengo la fórmula:
$$T(n,4) = (10^n - (4)6^n + (6)4^n - (9)2^n + 8)/24$$
No estoy poniendo esto como una respuesta porque todavía no estoy seguro de una fórmula general que no involucre verificar manualmente todas las particiones posibles que son inicialmente contadas de menos.
