Collares binarios primitivos

Question

El problema/solución de contar el número de collares (primitivos) (palabras de Lyndon) es muy conocido.

Pero, ¿qué pasa con los resultados que dan condiciones suficientes para que un collar dado sea primitivo? Por ejemplo, en el caso binario, un collar de longitud $N$ (00..00100..01) será primitivo siempre que el número $M$ de ceros entre los dos 1 es tal que $\gcd(N,M)=1$ .

¿Alguna idea o referencia de otros resultados de este tipo?

Answer 1

El número de cadenas primitivas de longitud $n$ Llámalo $p_n$ es fácil de conseguir. El número total de longitudes $n$ cuerdas hechas de $s$ símbolos es sólo $s^n$ . Todas las cadenas están hechas de repeticiones de alguna cadena primitiva (en caso de que sea primitiva, es una repetición). Entonces: $$ s^n = \sum_{d \mid n} p_d $$ y la inversión de Möbius da: $$ p_n = \sum_{d \mid n} \mu(n/d) s^d $$ Ahora cada collar primitivo (es decir, ciclo) se puede cortar en $n$ lugares para obtener diferentes cadenas primitivas, por lo que el número de collares primitivos es justo: $$ c_n = \frac{1}{n} \sum_{d \mid n} \mu(n/d) s^d $$

Answer 2

Me gustaría añadir algunas vinculadas material de la OEIS a este hilo con el fin de facilitar la exploración de este problema. (La cantidad de material en la OEIS indica que este problema ha interesado a muchos combinatoria de los aficionados.) Nos muestran cómo contar primitivo collares de en la mayoría de las $N$ colores. Recordemos que el Poli Enumeración Teorema nos dice que el número total de collares (simetría rotacional sólo) en la mayoría de los $N$ colores está dada por el sustituido ciclo de índice de la cíclico grupo $$Z(C_n) = \frac{1}{n}\sum_{d|n} \varphi(d) a_d^{n/d}$$ que es, suponiendo que hay $N$ colores, $$q_n = Z(C_n)(c_1+c_2+\cdots+c_N)_{c_1=c_2=\cdots=c_N=1} \\= \left. \frac{1}{n}\sum_{d|n} \varphi(d) (c_1^d+c_2^d+\cdots+c_N^d)^{n/d} \right|_{c_1=c_2=\cdots=c_N=1} = \frac{1}{n}\sum_{d|n} \varphi(d) N^{n/d}.$$ Deje que el número de primitivas collares ser $p_n$, entonces es perfectamente sencillo para mostrar que $$\sum_{d|n} p_d = q_n.$$ Aplicar Moebius inversión para obtener $$p_n = \sum_{d|n} \frac{\mu(n/d)}{d} \left(\sum_{f|d} \varphi(f) N^{d/f}\right).$$

Aquí es el de Arce código para calcular esta función.

con(numtheory);

p := proc(n, N)
local d, f, res;
 res := 0;
 para d en numtheory:-divisores(n) de f en numtheory:-divisores(d) ¿
 res := res + numtheory:-mobius(n/d)*numtheory:-phi(f)*N^(d/f)/d
 final ¿
 fin de hacer;
res
end proc

Esto da para dos colores ($N=2$) de la secuencia $$2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161, 2182,\ldots$$ que es OEIS A001037.

Durante tres colores ( $N=3$ ), llegamos a la secuencia $$3, 3, 8, 18, 48, 116, 312, 810, 2184, 5880, 16104, 44220, 122640, 341484, 956576,\ldots$$ que es OEIS A027376.

Finalmente, para cuatro colores ( $N=4$ ), llegamos a la secuencia $$4, 6, 20, 60, 204, 670, 2340, 8160, 29120, 104754, 381300, 1397740, 5162220,\ldots$$ que es OEIS A027377.

Adenda. De acuerdo a la OEIS, la fórmula anterior para $p_n$ se simplifica a $$p_n = \frac{1}{n}\sum_{d|n} \mu(d) N^{n/d}.$$

La simplificación de la anterior va de esta.

Empezar con $$p_n = \sum_{d|n} \frac{\mu(n/d)}{d} \left(\sum_{f|d} \varphi(f) N^{d/f}\right).$$

Volver a índice de ajuste de $d/f=q$, de modo que $d=fq$ obtener $$p_n = \sum_{p|n} N^q \sum_{f|n/q} \frac{\mu(n/f/q)}{qf} \varphi(f).$$

Este es $$p_n = \frac{1}{n} \sum_{p|n} N^q \sum_{f|n/q} \frac{\mu(n/f/q)}{fq/n} \varphi(f).$$ Poner a $m= n/q$ el interior de la suma se convierte en $$\sum_{f|m} \mu(m/f) \times m/f \times \varphi(f).$$

Esta es una convolución de funciones multiplicativas por lo que sólo necesitamos verificar que para el primer potencias $m = p^v.$ Esto le da dos términos, es decir, para $f = p^v$ $f = p^{v-1}$ , que para $v\ge 2$ contribuir $$1 \1 \times \varphi(p^v) - 1 \times p \times \varphi(p^{v-1}) = p^v - p^{v-1} - p (p^{v-1} - p^{v-2}) = 0.$$ Para $v=1$ tenemos $$1 \1 \times \varphi(p) - 1 \times p \times \varphi(1) = p-1 - p = -1.$$ Finalmente, para $m=1$ obtenemos $1.$ Esto muestra que (mediante la convolución de ser multiplicativa) $$\sum_{f|m} \mu(m/f) \times m/f \times \varphi(f) = \mu(m)$$ y finalmente tenemos $$p_n = \frac{1}{n} \sum_{q|n} N^q \mu(n/q).$$

Answer 3

He aquí otra respuesta que presenta un giro adicional a la problema de contar collares primitivos, a saber Grupo de potencia Enumeración (tal como lo presentan Harary y Palmer y Fripertinger, en una publicación diferente), con el grupo actuando en las ranuras donde el $N$ colores se colocan siendo el grupo cíclico $C_n$ en $n$ elementos y el grupo que actúa sobre los colores es el grupo simétrico sobre $N$ elementos $S_N$ .

Esto trata el problema de contar collares primitivos donde los colores pueden intercambiarse sin que los collares resultantes se consideren diferentes.

Como en la otra respuesta tenemos la relación $$\sum_{d|n} p_d = q_n,$$ pero ahora $q_n$ se calcula mediante Enumeración de grupos de potencia . No se pero explicaremos cómo calcular $q_n$ y presentar el código Maple correspondiente. El valor deseado para primitivo collares entonces sigue por $$p_n = \sum_{d|n} \mu(n/d) q_d.$$

Podemos calcular el número $q_n$ de configuraciones por el lema de Burnside que dice promediar el número de asignaciones fijadas por los elementos del grupo de potencias, que tiene $N!\times |C_n|$ elementos y $|C_n|=n$ . Pero este número es fácil de calcular. Supongamos que tenemos una permutación $\alpha$ de $C_n$ y una permutación $\beta$ de $S_N.$ Si colocamos el número apropiado de copias completas, dirigidas y consecutivas de un ciclo de $\beta$ en un ciclo de $\alpha$ entonces esta asignación es fija bajo la acción del grupo de potencia, y esto es posible si la longitud del ciclo de $\beta$ divide la duración del ciclo de $\alpha$ y hay tantas asignaciones como la longitud de $\beta.$

Ahora el cálculo Burnside se hace mejor con un CAS, aquí está el código Maple.

with(numtheory);

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\_flatten\_term :=
proc(varp)
        local terml, d, cf, v;

        terml := \[\];

        cf := varp;
        for v in indets(varp) do
            d := degree(varp, v);
            terml := \[op(terml), seq(v, k=1..d)\];
            cf := cf/v^d;
        od;

        \[cf, terml\];
end;

pet\_cycleind\_cyclic :=
proc(n)
        1/n\*add(phi(d)\*a\[d\]^(n/d), d in divisors(n));
end;

q :=
proc(n, N)
    option remember;
    local idx\_colors, res, a, b,
    flat\_a, flat\_b, cyc\_a, cyc\_b, len\_a, len\_b, p, q;

    if n=1 then
       idx\_colors := \[a\[1\]\]
    else
       idx\_colors := pet\_cycleind\_symm(N);
    fi;

    res := 0;

    for a in pet\_cycleind\_cyclic(n) do
        flat\_a := pet\_flatten\_term(a);

        for b in idx\_colors do
            flat\_b := pet\_flatten\_term(b);

            p := 1;
            for cyc\_a in flat\_a\[2\] do
                len\_a := op(1, cyc\_a);
                q := 0;

                for cyc\_b in flat\_b\[2\] do
                    len\_b := op(1, cyc\_b);

                    if len\_a mod len\_b = 0 then
                        q := q + len\_b;
                    fi;
                od;

                p := p\*q;
            od;

            res := res + p\*flat\_a\[1\]\*flat\_b\[1\];
        od;
    od;

    res;
end;

p := (n, N) -> add(mobius(n/d)\*q(d,N), d in divisors(n));

Esto da para dos colores ( $N=2$ ) la secuencia $$1, 1, 1, 2, 3, 5, 9, 16, 28, 51, 93, 170,\ldots$$ que es OEIS A000048 .

Para tres colores ( $N=3$ ) $$1, 1, 2, 4, 8, 22, 52, 140, 366, 992, 2684, 7404,\ldots$$ que es OEIS A002075 .

Por último, para cuatro colores ( $N=4$ ) $$1, 1, 2, 5, 10, 35, 102, 360, 1232, 4427, 15934, 58465,\ldots$$ que es OEIS A056300 .

Vinculación adicional. Para $N=5$ encontramos una secuencia $$1, 1, 2, 5, 11, 38, 122, 496, 2005, 8707, 38364, 173562,\ldots$$ que es OEIS A056301 .

Para $N=6$ encontramos la secuencia $$1, 1, 2, 5, 11, 39, 125, 532, 2301, 11010, 54681, 284023,\ldots$$ que es OEIS A056302 .

Para $N=7$ encontramos la secuencia $$1, 1, 2, 5, 11, 39, 126, 536, 2353, 11606, 60498, 336399,\ldots$$ que aún no figura en la OEIS.

Adenda sáb 21 abr 2018. El algoritmo que acabamos de presentar admite un mejora considerable, a saber, que no es necesario aplanar las permutaciones porque podemos calcular la contribución de los ciclos de un par $(\alpha, \beta)$ multiplicando el número de coberturas de un tipo de ciclo de $\alpha$ por el número de instancias del ciclo de $\beta$ elevando el resultado a la potencia del número de instancias del tipo de ciclo de $\alpha.$

El resultado es el siguiente código Maple.

with(numtheory);

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\_cycleind\_cyclic :=
proc(n)
    1/n\*add(phi(d)\*a\[d\]^(n/d), d in divisors(n));
end;

q := proc(n, N)
option remember;
local idx\_slots, idx\_colors, res, term\_a, term\_b,
    v\_a, v\_b, inst\_a, inst\_b, len\_a, len\_b, p, q;

    if n = 1 then
        idx\_slots := \[a\[1\]\];
    else
        idx\_slots := pet\_cycleind\_cyclic(n);
    fi;

    if N = 1 then
        idx\_colors := \[a\[1\]\];
    else
        idx\_colors := pet\_cycleind\_symm(N);
    fi;

    res := 0;

    for term\_a in idx\_slots do
        for term\_b in idx\_colors do
            p := 1;

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

                q := 0;

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

                    if len\_a mod len\_b = 0 then
                        q := q + len\_b\*inst\_b;
                    fi;
                od;

                p := p\*q^inst\_a;
            od;

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

    res;
end;

p := (n, N) -> add(mobius(n/d)\*q(d,N), d in divisors(n));