Conteo de conjuntos por su conexión

Question

Deje $U = \{u_1, u_2, \ldots , u_m \}$ donde cada una de las $u_i$ $r$- subconjunto de $[n]$ y $\,\bigcup u_i \!=\! [n]$. Construcción de la intersección de la gráfica de $U$. Es decir, que el nodo $i$ corresponden a $u_i$ y añadir borde de $(i,j)$ si $u_i \cap u_j \neq \emptyset$. Por ejemplo, supongamos $n=8$$U = \{123, 124, 234, 567, 568\}$. La intersección de la gráfica es

$\qquad \qquad \qquad \qquad \qquad \qquad \quad $

Hemos notado que hay dos componentes conectados, es decir,. $\mathcal{C}(U)=2$. Dado $n,r,m$ ¿cuántos sets tienen exactamente $c$ componentes conectados?

$$ \begin{array}{ll} T_{n,r,m}(c) &= \displaystyle \left[x^c\right] \sum_{\left|U\right| = m} x^{\mathcal{C}(U)} \\ &= \displaystyle \left[y^m x^c\right] \sum_U y^{\left|U\right|} x^{\mathcal{C}(U)} \end{array} $$

Podemos llegar a una expresión para $T_{n,r,m}(c)$ o, al menos, de alguna forma, para calcular de manera eficiente? Yo sería feliz con un algoritmo donde $n \le 50, r \le 10$ es manejable. He enumerado todos los valores distintos de cero para $n\le6$ a utilizar para la verificación.

---

He publicado una respuesta parcial que reduce el problema a recuento $T_{n,r,m}(1)$, los conjuntos con un gráfico completamente conectado.

Answer 1

Nuevas Notaciones: Siempre fix $r$. Supongamos $L=(c_1, c_2, \ldots, c_l)$ es una lista de no-decreciente de números naturales. Denotan por $|L|$ ($=l$) la longitud de la lista y $\sum L = c_1 + \ldots + c_l$ la suma de las entradas en $L$. Deje $T(n, L)$ contar el número de conjuntos de $U = \{u_1, \ldots, u_{m}\}$ donde $m=\sum L$, cada una de las $u_i$ $r$- subconjunto de $[n]$$\cup U = [n]$, cuya intersección del gráfico tienen exactamente $l$ componentes conectados con los tamaños de las $c_1, c_2, \ldots, c_l$.

Relación con la Antigua Notación: $$T_{n,m}(c)=\sum_{|L| = c, \sum{L}=m}T(n, L).$$

Inductivo De La Propiedad:

1. Si $L = L_1+L_2$ (lista de concatenación) tal que $L_1 < L_2$ (es decir, todas las entradas en $L_1$ es menos que los de $L_2$), $$T(n,L)=\sum_{n_1+n_2=n} {n\choose n_1} T(n_1, L_1)T(n_2, L_2).$$
2. Supongamos $L = (c,c,\ldots, c) =: (c)^l$ donde $l=|L|$. Tenemos $$T(n, L)=\sum_k\sum_{l_1 + \ldots + l_k = l}\frac{1}{l_1!\ldots l_k!}\sum_{\ n_1 < \ldots < n_k}\frac{n!}{(n_1!)^{l_1}\ldots(n_k!)^{l_k}}1_{l_1n_1 + \ldots + l_kn_k=n}T(n_1, (c))^{l_1}\ldots T(n_k, (c))^{l_k}.$$

Condición de frontera: $T(n, L)=0$ si $n < r$ o $n > r|L|$.

Restricción Fórmula: Nota de que el número total de conjuntos de $U = \{u_1, \ldots, u_m\}$ $u_i$ $r$- subconjunto de $[n]$ es igual a $${{n\choose r}\choose m}.$$ On the other hand, one can count it using $T_{n,m}(c)$ according to $\copa U$. We get the total number of $U$ is equal to $$\sum_{n_0\leq n}{n\choose n_0}\sum_cT_{n_0, m}(c) = \sum_{n_0\leq n}{n\choose n_0}\sum_l\sum_{|L| = l, \sum{L}=m}T(n_0, L).$$ Therefore we have $$\sum_{n_0\leq n}{n\choose n_0}\sum_l\sum_{|L| = l, \sum{L}=m}T(n_0, L) = {{n\choose r}\choose m}.$$ We rewrite it as $$T(n,(m)) = {{n\choose r}\choose m} - \sum_{n_0 < n}{n\choose n_0}\sum_l\sum_{|L| = l, \sum{L}=m}T(n_0, L) - \sum_{l>1}\sum_{|L| = l, \sum{L}=m}T(n, L)$$

La Línea de golpe: Definir $(n_0, L_0) < (n, L)$ si $n_0 < n$ o $n_0 = n$ pero $|L_0| > |L|$. Claramente, uno puede usar el inductivo propiedades, la condición de frontera y la restricción de la fórmula para calcular el $T(n,L)$ una vez $T(n_0,L_0)$ son para todos los $(n_0, L_0)< (n,L)$ (llame a $(n,L)$ complejidad de $T(n,L)$), ya que en todas las fórmulas de la complejidad en el lado derecho es siempre menor que la complejidad en el lado izquierdo.

Actualización: Para computacional razones (como OP mencionado en el comentario), uno lo desea, puede reemplazar el inductivo de la propiedad 2 por un simple recursividad $$T(n,(c)^l)=\sum_{k}{n-1\choose k-1}T(k,(c))T(n-k,(c)^{l-1}).$$ de Nuevo la idea en la perspectiva de propiedades es, de hecho, basado en OP respuesta.

Answer 2

Aquí es una respuesta parcial, lo que reduce el problema a recuento $T_{n,r,m}(1)$, es decir, contar el número de conjuntos que tienen un ramal de intersección de la gráfica de ($c=1$). La reducción se produce a través de una recurrencia, con $c=1$ correspondiente a la base de casos. En primer lugar, permítanme cambiar la notación. Deje $r$ dará como antes. Desde $r$ se mantiene fijo, suprimir como un índice.

$$ \; $$

• $T_{n,m}^{c,\ell}$ : Este es el mismo que el antiguo notación $T_{n,r,m}(c)$ con el agregado de la restricción de que cada componente tiene menos de $\ell$ nodos.

• $T_{n}^{c\,\times\,\ell}$ : restringe el gráfico exactamente $c$ componentes conectados de tamaño $\ell$. El número de nodos es suprimida como un índice, ya que se ve obligado a igualdad de $c\ell$.

• $T_{n,m} = T_{n,m}^{1,\, \ell_{ > m}} = T_{n}^{1 \, \times \, m}$ : cuenta el número de conectados gráficos en $m$ nodos.

$$ \; $$

Recuerde que para todos los tres de estos, cada nodo corresponde a un $r$-subconjunto y su unión debe ser igual a $[n]$. Para calcular los $T_{n,m}^{c,\ell}$, vamos a $\gamma$ el valor del tamaño de la mayor componente conectado, deje $\varsigma$ el número de componentes de tamaño $\gamma$, vamos a $\kappa$ a ser el número de elementos cubiertos por este tipo de componentes, y, a continuación, recurse.

$$ T_{n,m}^{c,\ell} = \sum_{\gamma \,<\, \ell} \; \sum_{\varsigma \,\le\, c} \; \sum_{\kappa \, \le \, n} {n \elegir \kappa}\; T_{\kappa}^{\varsigma \, \times \, \gamma} \; T_{n-\kappa\,m-\gamma\varsigma}^{c-\varsigma,\,\gamma} $$

Nota: la suma de los límites de frecuencia puede ser podados. El ${n \choose \kappa}$ recoge los elementos de $[n]$ cubierto por los grandes componentes. Para calcular los $T_{n}^{c \, \times \ell}$ $c>1$ imponemos que la "primera" componente a ser el que cubre el elemento "1" y suponemos que cubre $\kappa$ total de elementos. Luego nos recurse.

$$ T_{n}^{c \, \times \, \ell} = \sum_{\kappa \, < \, n} {n-1 \choose \kappa - 1} \; T_{\kappa, \ell} \; T_{n-\kappa}^{(c-1) \, \times \, \ell} $$

Por tanto, el problema se ha reducido a contar conectado gráficos de $T_{n,m}$.

Actualización de @roy restricción de la fórmula: sumando más de $c$ y escoger el plazo $T_{n,m}$ obtenemos la expresión

$$ T_{n,m} \; = \; {{n \choose r} \choose m} \; - \; \sum_{\kappa \, < \, n} \sum_{c} {n \choose \kappa} T_{\kappa,m}^{c, \infty} \; - \; \sum_{c \, > \, 1} T_{n,m}^{c,\infty}$$

nota el tercer término en el lado derecho de no producir un $T_{n,m}$ (por lo que no hay cancelación).