¿Cuántas formas hay de embolsar las canicas?

Question

Supongamos que tenemos $n$ canicas cada una etiquetada con números $1$ a través de $n$ . Tenemos bolsas que pueden contener cosas donde a cosa se define como $\text{(a)}$ un mármol o $\text{(b)}$ otra bolsa.

Queremos considerar todas las formas en que podemos "embolsar" las canicas. "Embolsar" significa que el "resultado final", por así decirlo, es tener un conjunto de bolsas "exteriores" $\{b_1, b_2, b_3 \cdots b_q\}$ de manera que cada canica esté contenida en una de las bolsas exteriores, bien directamente, bien indirectamente (por ejemplo, una canica puede estar dentro de una interior bolsa que está contenida en uno de los $b_i$ y, en general, esta "anidación" puede ser de hasta $n$ bolsas de profundidad).

Disponemos de un sinfín de bolsas. Esto sugiere que hay un problema. Podríamos poner una canica en alguna bolsa $b_1$ y poner $b_1$ en otra bolsa $b_2$ y continuar este proceso de forma arbitraria para tener un número infinito de combinaciones. Nosotros no permitimos esto. Cada bolsa utilizada debe directamente contienen al menos una canica.

Tenga en cuenta que también consideramos las combinaciones de mármol. Por ejemplo, si $n=2$ entonces una idea es poner una canica en una bolsa $b_1$ y tener otra bolsa $b_2$ que contiene el otro mármol junto con $b_1.$ Este método cuenta con dos de la bolsa, ya que las dos canicas pueden intercambiar sus papeles. La razón por la que las canicas están "etiquetadas" es para subrayar este punto.

Ahora, los problemas:

¿Cuál es un algoritmo para calcular el número de todos los embolsamientos posibles en función de $n$ ? ¿Puede hacerse en tiempo polinómico? ¿Existe una forma matemática cerrada?

He tratado de formalizar esto a continuación (si hay algún error en la "formalización", basta con atenerse a lo que he escrito arriba).

Definición formal :

Dejemos que $X$ sea un conjunto finito arbitrario no vacío. Supongamos que tiene cardinalidad $n$ . A este conjunto le asignamos una clase finita de conjuntos $B_{X}$ . Un miembro de esta clase se denomina " $B_{X}$ conjunto". Esta asignación se define de forma recursiva.

Si $n=1$ entonces $X = \{x_0\}$ es un conjunto único. En este caso, el único $B_{X}$ es simplemente $X$ .

Si $n > 1$ entonces el $B_{X}$ conjuntos de $X$ son aquellos conjuntos $B$ que satisfacen lo siguiente: $B \cap X \neq \varnothing$ y $B \setminus (B \cap X) = \{B({X_1}), B({X_2}) \cdots B({X_p})\}$ donde $X_1, X_2 \cdots X_p$ son disjuntos por pares con $\bigcup_{1 \leq i \leq p} X_i = X \setminus (B \cap X)$ y cada $B(X_i)$ es un $B_{X_i}$ (esta es la parte recursiva; tenga en cuenta $|X_i| < |X|=n$ ). Tenga en cuenta que $B \setminus (B \cap X) = \varnothing$ también está permitido. En particular, esto implica que todos los subconjuntos no vacíos de $X$ son $B_{X}$ conjuntos.

Está bastante claro que la recursión termina.

A ensacado completo de $X$ es un conjunto finito no vacío $\{b_1, b_2, b_3 \cdots b_q\}$ de conjuntos donde cada $b_i$ es un $B_{Y_i}$ con todos los $Y_i$ son no vacíos, disjuntos entre sí y $\bigcup_{1 \leq i \leq q} Y_i = X$ .

El número de bolsas completas de $X$ depende únicamente de $n$ . Sea $C(n)$ denotan esta cantidad. Queremos calcular $C(n)$ .

Answer 1

El problema se divide naturalmente en dos partes:

1. Poner las canicas en el $k$ bolsas que los contienen.
2. Anidar el $k$ bolsas en otras bolsas.

Fijar un valor determinado de $k$ la primera tarea se puede realizar en $S(n,k)$ formas, donde $S(n,k)$ es el número de Stirling del segundo tipo.

Para la segunda tarea, trate la mesa sobre la que se asientan las bolsas "exteriores" como una "superbolsa". Entonces, el embolsado que incluye la "superbolsa" es un árbol rooteado y etiquetado en $k+1$ nodos, de los cuales hay $(k+1)^{k-1}$ posibilidades.

Sumando estos valores para $k \in \{1 \ldots n\}$ encontramos el número de bolsas de $n$ objetos es $$\displaystyle \sum_{k=1}^n S(n,k) (k+1)^{k-1}$$

Los primeros términos de la secuencia son 1, 4, 26, 243, 2992, 45906. Si se repiten algunos términos más y se comprueba en OEIS, esta secuencia se indexa como A052880 .

Anexo: Para abordar la cuestión planteada por @Jens, he aquí una enumeración para $n=3$

1. Tres bolsas exteriores - 1 vía: (A)(B)(C)
2. Dos bolsas exteriores: - 9 vías: (AB)(C), (AC)(B) y (A)(BC); (A(B))(C), (B(A))(C), (A(C))(B), (C(A))(B), (A)(B(C)), (A)(C(B))
3. Una bolsa exterior, tres bolas en la bolsa exterior - 1 vía: (ABC)
4. Una bolsa exterior, dos bolas en la bolsa exterior - 3 formas: (AB(C)), (AC(B)), (BC(A))
5. Una bolsa exterior, una bola en la bolsa exterior - 12 maneras: hay tres maneras de elegir la bola en la bolsa exterior (digamos A). Luego hay cuatro formas de colocar B y C: (A(BC)), (A(B)(C)), (A(B(C)), (A(C(B))).

La suma da como resultado 26 combinaciones posibles.