3 votos

¿Cuál es el número de particiones del conjunto de $\{1,1,2,2,3,3\}$ ?

Debe ser inferior a $B_6$ (donde $B_6$ es el número de Bell de $6$ ) ya que los elementos están "duplicados". Lo que más agradecería sería una función generadora que diera el número de particiones de conjuntos de $\{1,1,2,2, ...n,n\}$ .

1voto

Marko Riedel Puntos 19255

Utilizando la pista dada en la entrada de la OEIS podemos escribir un que permita calcular la secuencia en cuestión incluso para grandes valores de $n$ por ejemplo este segmento:

$$2, 9, 66, 712, 10457, 198091, 4659138, 132315780, 4441561814, \\ 173290498279, 7751828612725,393110572846777, 22385579339430539, \\ 1419799938299929267, 99593312799819072788, \ldots $$

La pista mencionada anteriormente dice que podemos contar de forma equivalente multigrafos con $n$ aristas etiquetadas donde los vértices del gráfico representan los conjuntos múltiples de la partición de conjuntos múltiples y están conectados por una arista $k$ si las dos instancias del valor $k$ se incluyen en el conjuntos representados por los dos vértices que constituyen la arista.

Suponiendo que tenemos el índice de ciclo $Z(G_n)$ de la acción sobre el bordes del grupo simétrico que permuta el $n$ vértices de un gráfico donde se permiten los bucles, el valor deseado viene dado por ( $2n$ es el número máximo de vértices que podemos cubrir con el $n$ bordes etiquetados y éstas son multi-bordes por lo que pueden ser etiquetadas con cualquier subconjunto de el $n$ etiquetas)

$$[B_1 B_2 \cdots B_n] Z(G_{2n}) \left(\prod_{q=1}^n (1+B_q)\right).$$

Pero este índice de ciclo es fácil de calcular, siendo el cálculo documentado en este Enlace MSE .

Obsérvese que aquí tenemos un caso especial que admite radicales simplificación radical. Supongamos que tenemos un término $\alpha\in Z(G_{2n})$ que tiene la forma $$p(\alpha) \prod_k a_k^{j_k(\alpha)}$$

con $p(\alpha)$ siendo el coeficiente principal (un número) y $j_k(\alpha)$ el grado de $a_k$ en $\alpha.$

Ahora tenemos que cualquier posible factor $a_k$ donde $k\gt 1$ sólo contribuyen a través del término constante porque estamos extrayendo el producto $B_1 B_2\cdots B_n.$ Esto deja $$p(\alpha) a_1^{j_1(\alpha)}.$$

Por último, observe que $$[B_1 B_2\cdots B_n] \left(\prod_{q=1}^n (1+B_q)\right)^{j_1(\alpha)} \\ = [B_1 B_2\cdots B_n] \prod_{q=1}^n (1+B_q)^{j_1(\alpha)} = \prod_{q=1}^n {j_1(\alpha)\choose 1} = j_1(\alpha)^n.$$

El efecto clave aquí es que hemos eliminado las costosas exponencias de los polinomios multivariados y sólo trabajamos con números, calculando este valor: $$\sum_{\alpha\in Z(G_{2n})} p(\alpha) j_1(\alpha)^n.$$

Este es el código:

pet\_cycleind\_symm :=
proc(n)
local p, s;
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\_edg :=
proc(n)
option remember;
local s, t, res, cycs, l1, l2, flat, u, v;

    if n=0 then return 1; fi;

    s := 0:
    for t in pet\_cycleind\_symm(n) do
        flat := pet\_flatten\_term(t);

        cycs := flat\[2\]; res := 1;

        for u to nops(cycs) do
            for v from u+1 to nops(cycs) do
                l1 := op(1, cycs\[u\]); l2 := op(1, cycs\[v\]);
                res := res \* a\[lcm(l1, l2)\]^(l1\*l2/lcm(l1, l2));
            od;
        od;

        for u to nops(cycs) do
            l1 := op(1, cycs\[u\]);
            if type(l1, odd) then
                # a\[l1\]^(1/2\*l1\*(l1-1)/l1);
                res := res\*a\[l1\]^(1/2\*(l1-1));
            else
                # a\[l1/2\]^(l1/2/(l1/2))\*a\[l1\]^(1/2\*l1\*(l1-2)/l1)
                res := res\*a\[l1/2\]\*a\[l1\]^(1/2\*(l1-2));
            fi;
        od;

        s := s + res\*t;
    od;

    s;
end;

Q :=
proc(n)
option remember;
    local res, flat, term;

    res := 0;
    for term in pet\_cycleind\_edg(2\*n) do
        flat := pet\_flatten\_term(term);
        res := res + flat\[1\]\*degree(term, a\[1\])^n;
    od;

    res;
end;

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X