El recuento no isomorfos de relaciones

Question

En un conjunto $X$ $n$ elementos, ¿cuántos no isomorfos de las relaciones que existen? El número de relaciones en un conjunto de $n$ elementos es $|\mathcal{P}(X \times X)|=2^{n^2}$, pero ¿hay alguna manera de dar una fórmula general para cómo muchos de estos no son isomorfos? Estoy interesado en esta cuestión para una aplicación a la lógica modal. Gracias!

En particular, considero que las dos relaciones de $R$ $S$ a ser isomorfos si existe un bijection $\varphi: X \rightarrow X$ tal que $\varphi(x) R \varphi(y) \Leftrightarrow x S y$

Answer 1

Una relación en $X$ puede ser modelado como un gráfico en el conjunto de vértices $X$. Ya que es un problema difícil de determinar el número de tipos de isomorfismo de grafos, supongo que tu respuesta no tiene una respuesta sencilla, y que no hay ninguna fórmula simple para el número de no-isomorfo relaciones.

ADEMÁS Esta es la secuencia de 595 en la enciclopedia en línea de secuencias de enteros. Estoy un poco sorprendido de que realmente hay una fórmula dada: $$a(n) = \sum_{1s_1+2s_2+\ldots =n} \frac{\operatorname{fixA}[s_1, s_2, ...]}{1^{s_1}s_1!\cdot 2^{s_2}s_2!\cdot\ldots}$$ donde $$\operatorname{fixA}[s_1, s_2, \ldots] = 2^{\sum_{i, j\geq 1} \gcd(i, j)s_i s_j}$$ Supongo que la fórmula surge como una aplicación de Cauchy-Frobenius lema.

Answer 2

Aquí hay algunos detalles más acerca de este cálculo. Vamos a resolver el problema a través de la Polya Enumeración Teorema. Este cálculo es muy similar a la enumeración de los no-isomorfo gráficos se muestra en este MSE enlace.

Tenemos que calcular el ciclo de índice del borde de permutación grupo de la completa bipartito gráfico en $2n$ nodos. Este es casi el mismo que el borde de permutación grupo de una gráfica en la $n$ nodos. La única diferencia es que el grupo correspondiente se obtiene a partir de la acción del grupo simétrico $S_n$ en pares ordenados en lugar de pares no ordenados como en el borde de permutación grupo. En realidad, esto simplifica el análisis, debido a un par de vértices en un ciclo no se cierra el ciclo después de atravesar $n/2$ elementos sino que atraviesa todo el ciclo.

El siguiente Arce código calcula este índice de ciclo del ciclo del índice del grupo simétrico, el cual, cabe señalar, es más rápido que itera sobre todas las particiones como en la otra respuesta.

con(numtheory);
con(grupo):
con(planta):

pet_cycleind_symm :=
proc(n)
 local p, s;
 opción de recordar;

 si n=0 entonces devolver 1; fi;

 ampliar(1/n*añadir(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_flatten_term :=
proc(varp)
 local terml, d, cf, v;

 terml := [];

 cf := varp;
 para v en indets(varp) ¿
 d := grado(varp, v);
 terml := [op(terml), seq(v, k=1..d)];
 cf := cf/v^d;
od;

 [cf, terml];
end;


pet_cycleind_rel :=
proc(n)
 opción de recordar;
 local dsjc, plano, p, cyc1, cyc2, l1, l2, res;

 si n=0 entonces devolver 1; fi;
 si n=1, a continuación, volver a[1] fi;

 res := 0;

 para dsjc en pet_cycleind_symm(n) hacer
 plano := pet_flatten_term(dsjc);

 p := 1;

 para cyc1 en el plano[2] ¿
 l1 := op(1, cyc1);
 para cyc2 en el plano[2] ¿
 l2 := op(1, cyc2);

 p := p *
 [lcm(l1,l2)]^(l1*l2/lcm(l1, l2));
od;
od;

 res := res + plano[1]*p;
od;

res;
end;

pet_varinto_cind :=
proc(poli, ind)
 local subs1, subs2, polyvars, indvars, v, bote, res;

 res := ind;

 polyvars := indets(poli);
 indvars := indets(ind);

 para v en indvars ¿
 bote := op(1, v);

 subs1 :=
[seq(polyvars[k]=polyvars[k]^olla,
k=1..nops(polyvars))];

 subs2 := [v=subs(subs1, poli)];

 res := subs(subs2, res);
od;

res;
end;

v :=
proc(n)
 opción de recordar;
 local p, k, gf;

 p := q1+q2;
 gf := expand(pet_varinto_cind(p, pet_cycleind_rel(n)));

 subs({t1=1, t2=1}, gf);
end;

Este es el ciclo de índice de $n=3$: $$1/6\,{a_{{1}}}^{9}+1/2\,{a_{{2}}}^{4}a_{{1}}+1/3\,{a_{{3}}}^{3}$$ y aquí es por $n=4$: $$1/24\,{a_{{1}}}^{16}+1/4\,{a_{{1}}}^{4}{a_{{2}}}^{6}+1/3\,{a_{{3}}}^{5}a_{{1}}+1/8\, {a_{{2}}}^{8}+1/4\,{a_{{4}}}^{4}. $$ El ciclo sustituido índice de $n=4$ es $${z}^{16}+2\,{z}^{15}+9\,{z}^{14}+32\,{z}^{13}+95\,{z}^{12}+203\,{z}^{11}+373\,{z}^{ 10}+515\,{z}^{9}\\+584\,{z}^{8}+515\,{z}^{7}+373\,{z}^{6}+203\,{z}^{5}+95\,{z}^{4}+32 \,{z}^{3}+9\,{z}^{2}+2\,z+1 .$$ Para $n=5$ tenemos $$ {\frac {1}{120}}\,{a_{{1}}}^{25}+1/12\,{a_{{1}}}^{9}{a_{{2}}}^{8}+1/6\,{a_{{3}}}^{7} {a_{{1}}}^{4}+1/8\,{a_{{2}}}^{12}a_{{1}}+1/4\,{a_{{4}}}^{6}a_{{1}}+1/6\,{a_{{2}}}^{2 }{a_{{6}}}^{2}{a_{{3}}}^{3}+1/5\,{a_{{5}}}^{5}.$$ El recuento del número de no-isomorfo binario de las relaciones $$2, 10, 104, 3044, 291968, 96928992, 112282908928, 458297100061728,\\ 6666621572153927936, 349390545493499839161856,66603421985078180758538636288,\\ 46557456482586989066031126651104256,120168591267113007604119117625289606148096,\\ 1152050155760474157553893461743236772303142428672,\\ 41233441401686067929518834693764864820973598636585435136,\ldots$$ Este es, de hecho, OEIS A000595 como señaló el otro cartel.