Cuántos $n\times m$ ¿hay matrices binarias, hasta las permutaciones de filas y columnas?

Question

Estoy interesado en el número de matrices binarias de un tamaño determinado que son distintas con respecto a las permutaciones de filas y columnas.

Si $\sim$ es la relación de equivalencia en $n\times m$ matrices binarias tales que $A \sim B$ si se puede obtener B aplicando una matriz de permutación a A, me interesa el número de $\sim$ -clases de equivalencia sobre todos los $n\times m$ matrices binarias.

Sé que hay $2^{nm}$ matrices binarias de tamaño $n\times m$ y $n!m!$ posibles permutaciones, pero de alguna manera no consigo intuir lo que esto implica para las clases de equivalencia.

Answer 1

Esto se resuelve aquí utilizando la teoría de la enumeración de Pólya. Para el caso del cuadrado ( $n=m$ ), ver esta secuencia .

Comentario: He encontrado esto buscando $1,2,7$ en la OEIS.

Answer 2

Aquí hay una contribución computacional que trata el caso de una matriz cuadrada cuadrada. Como se ha señalado, este problema puede resolverse utilizando la Polya Teorema de Enumeración. De hecho, si sólo nos interesa contar estas matrices, entonces el lema de Burnside será suficiente. Sólo tenemos que calcular el índice de ciclo del grupo que actúa sobre las ranuras de la matriz.

Estos índices de ciclo son fáciles de calcular y no necesitamos iterar sobre todos los $(n!)^2$ pares de permutaciones (que actúan sobre filas y columnas) sino que basta con iterar sobre pares de términos del índice del ciclo $Z(S_n)$ del grupo simétrico $S_n$ según sus multiplicidades para obtener el índice de ciclo $Z(Q_n)$ de la acción combinada acción sobre las filas y las columnas. El número de términos aquí es el mucho mejor recuento del número de particiones de $n$ al cuadrado (límite superior).

Ahora para un par de ciclos, uno de longitud $l_1$ de una permutación de filas $\alpha$ y otro de longitud $l_2$ de una permutación de columnas $\beta$ su contribución al producto de descomposición de ciclos disjuntos para $(\alpha,\beta)$ en el índice del ciclo $Z(Q_n)$ es por inspección $$a_{\mathrm{lcm}(l_1, l_2)}^{l_1 l_2 / \mathrm{lcm}(l_1, l_2)} = a_{\mathrm{lcm}(l_1, l_2)}^{\gcd(l_1, l_2)}.$$

El algoritmo ahora se vuelve muy simple -- iterar sobre pares de términos como se ha descrito anteriormente, recoger la contribución de cada par de ciclos y añadirla al índice del ciclo que se está calculando.

Esto da los siguientes índices de ciclo (sólo se muestran los cuatro primeros se muestran):

$$Z(Q_2) = 1/4\,{a_{{1}}}^{4}+3/4\,{a_{{2}}}^{2},$$

$$Z(Q_3) = 1/36\,{a_{{1}}}^{9}+1/6\,{a_{{1}}}^{3}{a_{{2}}}^{3}+1/4\,a_{{ 1}}{a_{{2}}}^{4}+2/9\,{a_{{3}}}^{3}+1/3\,a_{{3}}a_{{6}},$$

$$Z(Q_4) = {\frac {{a_{{1}}}^{16}}{576}}+1/48\,{a_{{1}}}^{8}{a_{{2}}}^{4 }+1/16\,{a_{{1}}}^{4}{a_{{2}}}^{6}+1/36\,{a_{{1}}}^{4}{a_{{3} }}^{4}+{\frac {17\,{a_{{2}}}^{8}}{192}}\\+1/6\,{a_{{1}}}^{2}a_{ {2}}{a_{{3}}}^{2}a_{{6}}+1/9\,a_{{1}}{a_{{3}}}^{5}+1/12\,{a_{ {2}}}^{2}{a_{{6}}}^{2}+{\frac {13\,{a_{{4}}}^{4}}{48}}+1/6\,a _{{4}}a_{{12}},$$

y

$$Z(Q_5) = {\frac {{a_{{1}}}^{25}}{14400}}+{\frac {{a_{{1}}}^{15}{a_{{2} }}^{5}}{720}}+{\frac {{a_{{1}}}^{9}{a_{{2}}}^{8}}{144}}+{ \frac {{a_{{1}}}^{10}{a_{{3}}}^{5}}{360}}+{\frac {{a_{{1}}}^{ 5}{a_{{2}}}^{10}}{480}}\\+1/48\,{a_{{1}}}^{3}{a_{{2}}}^{11}+{ \frac {a_{{1}}{a_{{2}}}^{12}}{64}}+1/36\,{a_{{1}}}^{6}{a_{{2} }}^{2}{a_{{3}}}^{3}a_{{6}}+1/36\,{a_{{1}}}^{4}{a_{{3}}}^{7}+{ \frac {{a_{{1}}}^{5}{a_{{4}}}^{5}}{240}}\\+{\frac {{a_{{2}}}^{5 }{a_{{3}}}^{5}}{360}}+1/24\,{a_{{1}}}^{3}a_{{2}}{a_{{4}}}^{5} +1/24\,{a_{{1}}}^{2}{a_{{2}}}^{4}a_{{3}}{a_{{6}}}^{2}+1/36\,{ a_{{2}}}^{5}{a_{{3}}}^{3}a_{{6}}\\+1/16\,a_{{1}}{a_{{2}}}^{2}{a _{{4}}}^{5}+1/24\,{a_{{2}}}^{5}a_{{3}}{a_{{6}}}^{2}+1/18\,{a_ {{2}}}^{2}{a_{{3}}}^{5}a_{{6}}+1/16\,a_{{1}}{a_{{4}}}^{6}\\+1/ 36\,{a_{{2}}}^{2}{a_{{3}}}^{3}{a_{{6}}}^{2}+1/12\,{a_{{1}}}^{ 2}a_{{3}}{a_{{4}}}^{2}a_{{12}}+1/12\,a_{{2}}a_{{3}}{a_{{4}}}^ {2}a_{{12}}+{\frac {13\,{a_{{5}}}^{5}}{300}}\\+1/30\,{a_{{5}}}^ {3}a_{{10}}+1/15\,{a_{{5}}}^{2}a_{{15}}+1/20\,a_{{5}}{a_{{10} }}^{2}+1/10\,a_{{5}}a_{{20}}+1/15\,a_{{10}}a_{{15}}.$$

Evaluando estos índices de ciclo con las variables ajustadas a dos tenemos obtenemos rápidamente la secuencia

$$2, 7, 36, 317, 5624, 251610, 33642660, 14685630688,\\ 21467043671008, 105735224248507784,1764356230257807614296,\\ 100455994644460412263071692,19674097197480928600253198363072,\\ 13363679231028322645152300040033513414,\\ 31735555932041230032311939400670284689732948,\ldots$$ que es en realidad OEIS A002724 .

Obsérvese que los índices de ciclo permiten enumerar configuraciones con más de dos entradas posibles o con entradas con pesos diferentes. Por ejemplo, con un cuadrado de 3x3 y tres colores $A,B$ y $C$ obtenemos la función generadora

$$Z(Q_3)(A+B+C) = 1/36\, \left( A+B+C \right) ^{9}+1/6\, \left( A+B+C \right) ^{3} \left( {A}^{2}+{B}^{2}+{C}^{2} \right) ^{3}\\+2/9\, \left( {A}^{3}+{B}^{3}+{C}^{3} \right)^{3} +1/4\, \left( A+B+C \right) \left( {A}^{2}+{B}^{2}+{C}^{2 } \right) ^{4}\\+1/3\, \left( {A}^{3}+{B}^{3}+{C}^{3} \right) \left( {A}^{6}+{B}^{6}+{C}^{6} \right)$$

que se amplía a

$${A}^{9}+{A}^{8}B+{A}^{8}C+3\,{A}^{7}{B}^{2}+3\,{A}^{7}B C+3\,{A}^{7}{C}^{2}+6\,{A}^{6}{B}^{3}+10\,{A}^{6}{B}^{2 }C\\+10\,{A}^{6}B{C}^{2}+6\,{A}^{6}{C}^{3}+7\,{A}^{5}{B}^ {4}+17\,{A}^{5}{B}^{3}C+28\,{A}^{5}{B}^{2}{C}^{2}\\+17\,{ A}^{5}B{C}^{3}+7\,{A}^{5}{C}^{4}+7\,{A}^{4}{B}^{5}+22\, {A}^{4}{B}^{4}C+43\,{A}^{4}{B}^{3}{C}^{2}+43\,{A}^{4}{B }^{2}{C}^{3}\\+22\,{A}^{4}B{C}^{4}+7\,{A}^{4}{C}^{5}+6\,{ A}^{3}{B}^{6}+17\,{A}^{3}{B}^{5}C+43\,{A}^{3}{B}^{4}{C} ^{2}+54\,{A}^{3}{B}^{3}{C}^{3}\\+43\,{A}^{3}{B}^{2}{C}^{4 }+17\,{A}^{3}B{C}^{5}+6\,{A}^{3}{C}^{6}+3\,{A}^{2}{B}^{ 7}+10\,{A}^{2}{B}^{6}C+28\,{A}^{2}{B}^{5}{C}^{2}\\+43\,{A }^{2}{B}^{4}{C}^{3}+43\,{A}^{2}{B}^{3}{C}^{4}+28\,{A}^{ 2}{B}^{2}{C}^{5}+10\,{A}^{2}B{C}^{6}+3\,{A}^{2}{C}^{7}\\+ A{B}^{8}+3\,A{B}^{7}C+10\,A{B}^{6}{C}^{2}+17\,A{B}^{5}{ C}^{3}+22\,A{B}^{4}{C}^{4}+17\,A{B}^{3}{C}^{5}\\+10\,A{B} ^{2}{C}^{6}+3\,AB{C}^{7}+A{C}^{8}+{B}^{9}+{B}^{8}C+3\,{ B}^{7}{C}^{2}+6\,{B}^{6}{C}^{3}+7\,{B}^{5}{C}^{4}\\+7\,{B }^{4}{C}^{5}+6\,{B}^{3}{C}^{6}+3\,{B}^{2}{C}^{7}+B{C}^{ 8}+{C}^{9}.$$

Este es el código de Maple para este cálculo. Aquí tenemos dos cálculos ligeramente diferentes de evaluar el recuento, la primera sustituyendo en el índice del ciclo y la segunda saltándose el índice del ciclo por completo y evaluando todas las variables a dos durante el procesamiento. Esta última cuando sólo nos interesa el recuento, en lugar de clasificar las configuraciones clasificar las configuraciones según el número de cada color / que están presentes.

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;

pet\_varinto\_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;

    res := ind;

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

    for v in indvars do
        pot := op(1, v);

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

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

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

    res;
end;

pet\_cycleind\_sqmat :=
proc(n)
option remember;
local sind, cind, term\_a, term\_b, v\_a, v\_b,
    len\_a, len\_b, inst\_a, inst\_b, p;

    cind := 0;

    if n=1 then
        sind := return a\[1\];
    else
        sind := pet\_cycleind\_symm(n);
    fi;

    for term\_a in sind do
        for term\_b in sind do
            p := 1;
            for v\_a in indets(term\_a) do
                len\_a := op(1, v\_a);
                inst\_a := degree(term\_a, v\_a);

                for v\_b in indets(term\_b) do
                    len\_b := op(1, v\_b);
                    inst\_b := degree(term\_b, v\_b);

                    p := p\*a\[lcm(len\_a, len\_b)\]
                    ^(gcd(len\_a, len\_b)\*inst\_a\*inst\_b);
                od;
            od;

            cind := cind +
            lcoeff(term\_a)\*lcoeff(term\_b)\*p;
        od;
    od;

    cind;
end;

v :=
proc(n)
    option remember;
    local cind, vars, sbl;

    cind := pet\_cycleind\_sqmat(n);

    vars := indets(cind);
    sbl := \[seq(v=2, v in vars)\];

    subs(sbl, cind);
end;

w := 
proc(n)
option remember;
local sind, count, term\_a, term\_b, v\_a, v\_b,
    len\_a, len\_b, inst\_a, inst\_b, p;

    count := 0;

    if n=1 then
        sind := return 2;
    else
        sind := pet\_cycleind\_symm(n);
    fi;

    for term\_a in sind do
        for term\_b in sind do
            p := 1;
            for v\_a in indets(term\_a) do
                len\_a := op(1, v\_a);
                inst\_a := degree(term\_a, v\_a);

                for v\_b in indets(term\_b) do
                    len\_b := op(1, v\_b);
                    inst\_b := degree(term\_b, v\_b);

                    p := p\*
                    2^(gcd(len\_a, len\_b)\*inst\_a\*inst\_b);
                od;
            od;

            count := count +
            lcoeff(term\_a)\*lcoeff(term\_b)\*p;
        od;
    od;

    count;
end;

Este Metaenlace MSE tiene muchos más cálculos de PET por parte de varios usuarios.