El número de familias de subconjuntos de a $\{1,2,...,n\}$ cuya unión no es todo el conjunto.

Question

Escribí un código de Mathematica que devuelve el número de familias (colecciones) de subconjuntos de a $\{1,2,...,n\}$ cuya unión no es todo el conjunto. El código sólo puede devolver los valores de $n = 1,2,3,4$. Los respectivos valores se $2,6,40, 1376$. Estos son los cuatro primeros términos de Sloane del A051185 que cuenta el número de intersección de las familias. Es esto una coincidencia o es que hay alguna razón por la que estas dos cuentas son iguales?

Answer 1

A051185 es el número de pares-) de intersección de las familias. Dos subconjuntos de a $\{1,\ldots, n\}$ se cruzan iff la unión de sus complementos no es $\{1,\ldots,n\}$. Pero desea no sólo los pares de los sindicatos sino de la unión de todos los conjuntos en su familia para no estar todo el conjunto. Así que usted debe conseguir un resultado diferente para $n=3$: la familia $\{\{1,2\}, \{1,3\}, \{2,3\}\}$ es de a pares de intersección, por lo que debe ser incluido en A051185, pero su complementa $\{\{3\},\{2\},\{1\}\}$ no debe ser incluido en la cuenta.
De hecho, llego $38$, no$40$$n=3$$942$, no$1376$$n=4$.

Answer 2

Si entiendo correctamente lo que estamos tratando de contar, el código es incorrecto. Creo que la secuencia que buscas es este: https://oeis.org/A005530

Answer 3

El problema es equivalente a contar el número de cubiertas de un conjunto finito.

Se ha mencionado al comienzo del artículo Mínima Cubre Finito de Conjuntos por Hearne y Wagner que el número es dado como la siguiente (donde "$n=1$" debe ser un error tipográfico):

---

Alternativamente, el número de posibles portadas para un conjunto de $N$ elementos

$$ C(N)=\frac{1}{2}\sum_{k=0}^N(-1)^k\binom{N}{k}2^{2^{N-k}}, $$ los primeros de los cuales se $1, 5, 109, 32297,\cdots$ (OEIS A003465: Número de maneras para cubrir un n-conjunto. ).

Answer 4

Aquí es un método que utiliza el Polya Enumeración Teorema (PET) con la misma técnica que en este MSE enlace.

Empezamos con el complementario problema de conteo de familias que cubren todos los de $[n].$ obtenemos la siguiente generación de la función de estos subconjuntos:

$$\prod_{q=1}^n (1+A_q).$$

La selección de un subconjunto de estos de tamaño $k$ se hace con la etiqueta establecer operador $\mathfrak{P}:$

$$Z(P_k)\left(\prod_{q=1}^n (1+A_q)\right).$$

Este operador ha OGF

$A$Z(P_k) = [w^k] \exp\left(\sum_{d\ge 1} (-1)^{d+1} a_d \frac{w^d}{d}\right)$$

La sustitución en el ciclo del índice de usos

$$a_d = \prod_{q=1}^n (1+A_q^d).$$

Utilizamos la inclusión-exclusión para calcular los términos que no todos los $A_q$ un presente. Estos se obtienen por primera restando aquellos en que una sola $A_q$ o más no están presentes, es decir, mediante el establecimiento de ese $A_q$ a cero. A continuación, añadimos en aquellos en los que un par de dos $A_q$ o más no son presente, de nuevo mediante la configuración de estos $A_q$ a cero y así sucesivamente. Los restantes $A_q$ se establece en uno. Por lo tanto, si $p$ o más de las $A_q$ no presente la sustitución se convierte en

$$a_d = 2^{n-p}.$$

De este modo, obtener por cédula del ciclo del índice

$$[w^k] \exp\left(\sum_{d\ge 1} (-1)^{d+1} 2^{n-p} \frac{w^d}{d}\right) \\ = [w^k] \exp\left(2^{n-p} \sum_{d\ge 1} (-1)^{d+1} \frac{w^d}{d}\right) \\ = [w^k] \exp\left(2^{n-p} \log(1+w) \right) = [w^k] (1+w)^{2^{n-p}} = {2^{n-p}\elegir k}.$$

Esto significa que tenemos por la inclusión-exclusión para el problema de la serie siendo cubierto

$$\sum_{p=0}^n {n\choose p} (-1)^p {2^{n-p}\choose k}.$$

Sumando sobre todos los posibles $k$ (puede ser en cualquier lugar de cero a $2^n$) se obtiene finalmente

$$\sum_{p=0}^n {n\elegir p} (-1)^p \sum_{k=0}^{2^n} {2^{n-p}\elegir k} = \sum_{p=0}^n {n\elegir p} (-1)^p 2^{2^{n-p}}.$$

Este rendimientos para el problema original, cuya respuesta se busca

$$\bbox[5px,border:2px solid #00A000]{ 2^{2^n} - \sum_{p=0}^n {n\elegir p} (-1)^p 2^{2^{n-p}}.}$$

que es la secuencia OEIS A005530

$$2, 6, 38, 942, 325262, 25768825638, \\ 129127208425774833206, \ldots$$

como se observó en un compañero de puesto.

El Arce código para esto (que calcular los cuatro primeros valores) era como este (que se muestra aquí para aclarar lo que la interpretación de la el problema está siendo utilizado):

con(planta);

ENUM :=
proc(n)
opción de recordar;
conjunto local, res, a que se refiere;

 res := 0;

 para establecer en powerset(powerset(n)) ¿
 cubierta := `unión`(op(set));

 si nops(cubierto) < n, entonces
 res := res + 1;
fi;
od;

res;
end;

X := n-> 2^(2^n)
-agregar(binomial(n,p)*(-1)^p*2^(2^(n-p)), p=0..n);

Adenda. Algunos pensaron que se produce la siguiente secuencia de comandos Perl que adhereres a los primeros principios (definición del problema), sin embargo, es la capacidad de calcular los cinco primeros valores de la secuencia en menos de tres segundos, que parece ser el límite natural de lo es posible. Vamos a resolver el complementario problema como el anterior.

#! /usr/bin/perl -w
#

sub recurse {
 my ($src, $visto, $pos, $n, $cref) = @_;

 mi $ch, ch, ch;
 for($ch, ch, ch = 0; $ch, ch, ch < $n; $ch, ch, ch++){
 última si $visto->[$chk] == 0;
}

 if($ch, ch, ch == $n){
 $$cref += 1 << ((1<<$n)-$pos);
de retorno;
}

 de regreso si $pos >= (1 << $n);

 recurse($src, $visto, $pos+1, $n, $cref);

 foreach my $el (@{ $src->[$pos] }){
$ver->[$el]++;
}
 recurse($src, $visto, $pos+1, $n, $cref);
 foreach my $el (@{ $src->[$pos] }){
$ver->[$el]--;
}

1;
}

PRINCIPAL : {
 mi $n = shift || 4;

 mi $srcset = [];

 para(mi $idx = 2**$n-1; $idx >= 0; $idx--){
 mi @data;

 para(mi ($bitpos, $idx2) = (0, $idx); 
 $bitpos < $n; $bitpos++){
 mi $bits = $idx2 % 2;

 push @de datos, $bitpos si $bits == 1;
 $idx2 = ($idx2-$bits)/2;
}

 push @$srcset, \@data;
}

 mi (@vis) = (0) x $n;

 mi $resultado = 0; 
 recurse($srcset, \@vis, 0, $n, \$resultado);
 $resultado = 2**(2**$n) - $resultado;

 print "$resultado\n";

1;
}