¿Cuántas estructuras binarias no isomorfas en el conjunto de $n$ ¿elementos?

Question

Esta pregunta tiene su origen en Álgebra abstracta de Fraleigh, Ex3.34 . El ejercicio es para el caso de $n=2$ . La respuesta es 10, y la siguiente es mi solución al respecto.

Sea el conjunto $\{{ a,b \}}$ . Si dejamos que $f$ sea el isomorfismo no identitario( $f(a)=b, f(b)=a$ ), entonces 4 estructuras binarias son invariantes bajo $f$ : Si se establece $a*a$ y $a*b$ entonces el resto están determinados ya que $f(a)*f(a)=b*b$ y $f(a)*f(b)=b*a$ . Así que el número de estructuras binarias no isomórficas es $4+ \frac {16-4} 2 = 10$ .

¿Hay alguna generalización de esto en $n$ ¿elementos? Me parece un poco complicado. He intentado encontrar algo en google, pero no lo consigo.

Answer 1

Siguiendo con las citas de la página de la OEIS en mi comentario, parece que se puede aprender mucho de Michael A Harrison, The number of isomorphism types of finite algebras, Proc Amer Math Soc 17 (1966) 731-737. Las fórmulas allí son elementales pero muy largas, así que no las escribiré aquí. Creo que el artículo está disponible gratuitamente en el sitio web de la AMS.

Si las fuentes dicen lo que yo creo que dicen, por $n=3$ se obtienen 3.330.

EDIT: En un comentario, Doug pregunta por una fórmula en la página de la OEIS. No creo que quepa en un comentario, así que intentaré escribirla aquí. Deja que $${\rm fix\ }A(s_1,s_2,\dots)=\prod_{i,j\ge1}\sum_{d\mid{\rm lcm}(i,j)}(ds_d)^{s_is_j\gcd(i,j)}$$ Entonces $$a_n=\sum_{s_1+2s_2+\dots=n}{{\rm fix\ }A(s_1,s_2,\dots)\over1^{s_1}s_1!2^{s_2}s_2!\dots}$$

Answer 2

Me parece importante señalar que la fórmula anterior iterando sobre todas las formas de partición no es lo mejor que podemos hacer. Lo que buscamos aquí es una enumeración de todas las $N\times N$ matrices con entradas de $1$ a $N$ bajo el grupo simétrico que actúa sobre las entradas y las filas y columnas al mismo tiempo. Podemos utilizar Burnside directamente y calcular el índice de ciclo apropiado (que representa la acción del grupo simétrico sobre los pares ordenados) a partir del índice de ciclo del grupo simétrico, como se hizo en este Enlace MSE . El índice de ciclo del grupo simétrico puede calcularse con un truco que se remonta a Lovasz: $$ Z(S_0) = 1 \quad \text{and} \quad Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l Z(S_{n-l})$$ y no necesitamos iterar sobre todas las particiones para calcular este índice. (Sin embargo, hay que señalar que este índice de ciclos contiene términos con descomposiciones de ciclos disjuntos correspondientes a todas las particiones).

Ahora Burnside es bastante simple aquí. Para cada ciclo de una sola permutación $P$ de los elementos de la matriz inducidos por la acción de una permutación $Q$ del grupo simétrico en $N$ necesitamos determinar las asignaciones a las ranuras del ciclo que están fijadas por $P$ . Pero estas son precisamente las asignaciones que consisten en repeticiones cíclicas de ciclos completos de $Q$ es decir, podemos colocar cualquier ciclo de $Q$ en un ciclo de $P$ siempre que la longitud del primero divida la del segundo. Cada uno de estos pares produce $r$ posibles asignaciones en las que $r$ es la duración del ciclo desde $Q.$ Esta simple observación basta para aplicar Burnside.

Obtenemos la siguiente secuencia de valores: $$ 1, 10, 3330, 178981952, 2483527537094825, 14325590003318891522275680,\\ 50976900301814584087291487087214170039,\\ 155682086691137947272042502251643461917498835481022016,\\ 541851439802559836957713164869818405872834954135521300809902639457510935,\ldots$$ que coincide con el Entrada en la OEIS .

Los valores anteriores se calcularon con el siguiente código de Maple.

pet\_cycleind\_symm :=
proc(n)
option remember;

    if n=0 then return 1; fi;

    expand(1/n\*add(a\[l\]\*pet\_cycleind\_symm(n-l), l=1..n));
end;

bs\_binop :=
proc(n)
option remember;
local dsjc, varp1, varp2, var, p, q, len,
    l1, l2, res;

    if n=0 then return 1; fi;
    if n=1 then return 1; fi;

    res := 0;

    for dsjc in pet\_cycleind\_symm(n) do
        p := 1;

        for varp1 in indets(dsjc) do
            l1 := op(1, varp1);

            for varp2 in indets(dsjc) do
                l2 := op(1, varp2);

                len := lcm(l1,l2); q := 0;

                for var in indets(dsjc) do
                    if len mod op(1, var) = 0 then
                        q := q  +
                        op(1, var)\*degree(dsjc, var);
                    fi;
                od;

                p := p \*
                q^(degree(dsjc, varp1) \*
                   degree(dsjc, varp2)
                   \*l1\*l2/len);
            od;
        od;

        res := res + p\*lcoeff(dsjc);
    od;

    res;
end;