Números de Stirling de segundo tipo en Multiset

Question

Números de Stirling de segundo tipo en Multiset

multiconjuntos
Matemáticas
combinatoria
números de stirling
Matemáticas discretas

seda

Números de Stirling de segunda clase $S(n, k)$ Contar el número de formas de particionar un conjunto de $n$ elementos en $k$ subconjuntos no vacíos. ¿Qué pasaría si hubiera elementos duplicados en el conjunto? Es decir, el conjunto es un conjunto múltiple ?

David

Sería bueno agregar el enlace a la definición de números de Stirling: en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

Yuan Qiaochu

Es probable que la respuesta sea algo complicada de expresar. Por ejemplo, si el conjunto consta de un solo tipo de elemento, obtendrá los números de partición p_{n,k}: en.wikipedia.org/wiki/Partition_(number_theory)

Arturo Magidín

Creo que [matemáticas] es una etiqueta bastante inútil en este sitio; Lo eliminé y agregué [contando]

Respuestas (5)

Números de Stirling de segundo tipo en Multiset

Sería bueno agregar el enlace a la definición de números de Stirling: en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
Es probable que la respuesta sea algo complicada de expresar. Por ejemplo, si el conjunto consta de un solo tipo de elemento, obtendrá los números de partición p_{n,k}: en.wikipedia.org/wiki/Partition_(number_theory)
Creo que [matemáticas] es una etiqueta bastante inútil en este sitio; Lo eliminé y agregué [contando]

ken gonzales · Answer 1

No existe una formulación conocida para un conjunto múltiple general. Sin embargo, un artículo de JIS aborda el caso en el que el elemento 1 aparece varias veces.

Marko Riedel · Answer 2

A modo de enriquecimiento, aquí hay una solución que utiliza la enumeración de grupos de potencia en forma de polinomio. Este no es el algoritmo más eficiente y, si estamos justo después del conteo, de hecho podemos hacerlo mejor enumerando todas las particiones de conjunto recursivamente, que también se incluye aquí. Sin embargo, el algoritmo PGE tiene una cierta posibilidad de conducir realmente a una expresión de forma cerrada en lugar de a la salida de algún procedimiento.

El algoritmo es el mismo que se presenta en el siguiente enlace MSE I y en este enlace MSE enlace II (colores de borde del cubo). Requerimos los índices de ciclo de los grupos de permutación que actúan sobre las ranuras y sobre los valores que se distribuyen en ellas. Para un conjunto múltiple

A_{1}^{q_{1}} A_{2}^{q_{2}} \times \dots \times A_{pag}^{q_{pag}}

$A_1^{q_1} A_2^{q_2} \times \cdots \times A_p^{q_p}$

con $q_k$ las multiplicidades de las que están compuestas las ranuras $Q= \sum_r q_r$ ranuras distintas, en las que distribuimos los identificadores de los conjuntos múltiples donde residirá esa ranura. Podemos imaginar $q_r$ ranuras de tipo $r$ formando un bloque, siendo los bloques adyacentes y conteniendo solo ranuras del mismo tipo. Ahora, con un bloque que forma un conjunto múltiple, el grupo que actúa en estas ranuras es el grupo simétrico $S_{q_r}$ con índice de ciclo $Z(S_{q_r}).$ Por lo tanto, el índice de ciclo del grupo de permutación de intervalos (todos los bloques) es

\prod_{r} Z (S_{q_{r}}) .

$\prod_r Z(S_{q_r}).$ Por otro lado, los identificadores multiconjunto son permutados por el grupo simétrico

S_{Q}

$S_Q$ con índice de ciclo

Z (S_{Q}) .

$Z(S_Q).$ Estos datos son suficientes para ejecutar el algoritmo. Observe que cuando cubrimos (consulte los enlaces para los detalles de este procedimiento) los ciclos de una permutación de ranura con un ciclo de una permutación de identificador multiconjunto, debemos registrar los identificadores utilizados en la cobertura en una función generadora. Luego obtenemos el resultado deseado reemplazando los indeterminados en los términos de esta función generadora (una vez calculada) con

v^{m}

$v^m$ dónde

m

$m$ es el número de indeterminados en el término. Esto produce la función generadora por el número de conjuntos múltiples para todos

k

$k$ En seguida.

Presentamos algunos ejemplos. Cuando todo $q_r$ es uno con el que estamos trabajando $p$ elementos distintos y deben obtener números de Stirling. (Los números de Stirling ejemplifican la complejidad de este problema, ya que la rutina PGE es más rápida aquí y requiere menos memoria que la rutina de enumeración recursiva. Esto se debe a que el grupo de permutación de intervalos en este caso contiene solo un elemento. El cálculo se realizó en este enlace MSE III .) De hecho encontramos

> añadir(v^k*stirling2(3,k), k=1..3);  
                         3 2
                        v + 3 v + v

> CONJUNTOSMS([1,1,1]);
                         3 2
                        v + 3 v + v
> añadir(v^k*stirling2(7,k), k=1..7);
       7 6 5 4 3 2
      v + 21 v + 140 v + 350 v + 301 v + 63 v + v

> MSETS([seg(1, w=1..7)]);
       7 6 5 4 3 2
      v + 21 v + 140 v + 350 v + 301 v + 63 v + v

> añadir(v^k*stirling2(10,k), k=1..10);
 10 9 8 7 6 5
v + 45 v + 750 v + 5880 v + 22827 v + 42525 v

              4 3 2
     + 34105 v + 9330 v + 511 v + v

> MSETS([seg(1, w=1..10)]);         
 10 9 8 7 6 5
v + 45 v + 750 v + 5880 v + 22827 v + 42525 v

              4 3 2
     + 34105 v + 9330 v + 511 v + v

Por otra parte cuando $p=1$ tenemos $q_1$ como elementos y debe obtener los valores de la función de partición $p_k(n).$ Aquí nos encontramos una vez más

> añadir(v^k*parte(3,k), k=1..3);     
                          3 2
                         v + v + v

> MSETS([3]);                
                          3 2
                         v + v + v

> añadir(v^k*parte(7,k), k=1..7);
            7 6 5 4 3 2
           v + v + 2 v + 3 v + 4 v + 3 v + v

> MSETS([7]);                
            7 6 5 4 3 2
           v + v + 2 v + 3 v + 4 v + 3 v + v

> añadir(v^k*parte(10,k), k=1..10);
 10 9 8 7 6 5 4 3 2
v + v + 2 v + 3 v + 5 v + 7 v + 9 v + 8 v + 5 v + v

> CONJUNTOSMS([10]);                 
 10 9 8 7 6 5 4 3 2
v + v + 2 v + 3 v + 5 v + 7 v + 9 v + 8 v + 5 v + v

Ahora, por supuesto, se vuelve difícil e interesante cuando tenemos menos estructura en el tamaño y el número del multiconjunto fuente. Aquí hay algunos últimos ejemplos:

> ENUM([2,3,4]);               
 9 8 7 6 5 4 3 2
v + 6 v + 26 v + 75 v + 151 v + 191 v + 126 v + 29 v

     +v

> CONJUNTOSMS([2,3,4]);
 9 8 7 6 5 4 3 2
v + 6 v + 26 v + 75 v + 151 v + 191 v + 126 v + 29 v

     +v

> ENUM([3,4,5]);
 12 11 10 9 8 7 6
v + 6 v + 30 v + 111 v + 328 v + 757 v + 1331 v

             5 4 3 2
     + 1652 v + 1264 v + 474 v + 59 v + v

> CONJUNTOSMS([3,4,5]);
 12 11 10 9 8 7 6
v + 6 v + 30 v + 111 v + 328 v + 757 v + 1331 v

             5 4 3 2
     + 1652 v + 1264 v + 474 v + 59 v + v

> ENUM([2,2,3,3]);
 10 9 8 7 6 5 4
v + 10 v + 63 v + 257 v + 704 v + 1223 v + 1204 v

            3 2
     + 536 v + 71 v + v

> CONJUNTOSMS([2,2,3,3]);
 10 9 8 7 6 5 4
v + 10 v + 63 v + 257 v + 704 v + 1223 v + 1204 v

            3 2
     + 536 v + 71 v + v

El código fuente es bastante compacto, siendo la respuesta aproximadamente la mitad y el resto para pruebas y verificación.

con (combinar);

pet_cycleind_symm :=
proceso(n)
opción recordar;

    si n=0 entonces devuelve 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(nl), l=1..n));
fin;

MSETS :=
proc(mset)
opción recordar;
idx_slots locales, idx_sets, res, term_a, term_b,
    v_a, v_b, inst_a, inst_b, len_a, len_b, p, q;

    ranuras_idx :=
    expand(mul(pet_cycleind_symm(elemento), elemento en mset));

    si no (tipo (idx_slots, `+`)) entonces
        ranuras_idx := [ranuras_idx];
    fi;

    idx_conjuntos :=
    pet_cycleind_symm(add(elemento, elemento en mset));

    si no (tipo (idx_sets, `+`)) entonces
        idx_conjuntos := [idx_conjuntos];
    fi;

    resolución := 0;

    para term_a en idx_slots hacer
        para term_b en idx_sets hacer
            pag := 1;

            para v_a en indets(term_a) hacer
                len_a := op(1, v_a);
                inst_a := grado(término_a, v_a);

                q := 0;

                para v_b en indets(term_b) hacer
                    len_b := op(1, v_b);
                    inst_b := grado(término_b, v_b);

                    si len_a mod len_b = 0 entonces
                        q := q +
                        len_b*
                        agregar(mul(B[len_b,
                                  len_b*núm_ciclo+pos_ciclo],
                                cyc_pos=1..len_b),
                            cic_num=0..inst_b-1);
                    fi;
                sobredosis;

                p := p*q^inst_a;
            sobredosis;

            resolución := resolución +
            lcoeff(término_a)*lcoeff(término_b)*p;
        sobredosis;
    sobredosis;

    map(término -> lcoeff(término)*v^nops(indets(término)),
        expandir(res));
fin;

parte :=
proceso(n, k)
opción recordar;
res local;

    si n=0 o k=0 entonces
        devuelve `si`(n=0 y k=0, 1, 0);
    fi;

    si k=1 entonces devuelve 1 fi;

    resolución := 0;
    si n >= 1 entonces
        res := res + parte(n-1, k-1);
    fi;
    si n >= k entonces
        res := res + parte(nk, k);
    fi;

    res;
fin;

ENUM :=
proc(mset)
opción recordar;
total local, plana, recursiva, msets, res;

    total := add(elemento, elemento en mset);
    plano :=
    [seq(seq(p, q=1..mset[p]), p=1..nops(mset))];

    msets := tabla(); resolución := 0;

    recursiva :=
    proc(idx, len, parte)
    local pos, cur, sorted;

        si idx > total entonces
            ordenado :=
            sort([seq(part[pos], pos=1..len)]);

            if not(type(msets[sorted], `integer`)) entonces
                res := res + v^len;
                msets[ordenados] := 1;
            fi;

            devolver;
        fi;

        cur := A[plano[idx]];
        para pos a len hacer
            parte[pos] := parte[pos]*cur;
            recurse(idx+1, largo, parte);
            parte[pos] := parte[pos]/cur;
        sobredosis;

        parte[longitud+1] := parte[longitud+1]*cur;
        recurse(idx+1, len+1, parte);
        parte[longitud+1] := parte[longitud+1]/cur;
    fin;

    recurse(1, 0, Array([seq(1, q=1..total)]));
    res;
fin;

usuario1709 · Answer 3

Aquí hay dos enlaces para empezar:

Los números eulerianos del segundo tipo pueden ser útiles (para contar ascensos, descensos, etc., aunque creo)
Además, se puede encontrar más información útil en el libro de Stanley.

KRT · Answer 4

Divide el número de Stirling por las posibles permutaciones de elementos idénticos, ya que esto solo cambia el orden dentro del ejemplo de estrellas y barras.

David · Answer 5

Por definición, un conjunto solo tiene elementos distintos. Si los elementos están duplicados, entonces sí, el conjunto en cuestión sería un conjunto múltiple .

Números de Stirling de segundo tipo en Multiset

seda

David

Yuan Qiaochu

Arturo Magidín

Respuestas (5)

ken gonzales

Marko Riedel

usuario1709

KRT

David

Interpretación combinatoria de la fórmula explícita para los números de Stirling de segunda clase

¿Cuál es la prueba combinatoria para la fórmula de S(n,k)S(n,k)S(n,k) - Números de Stirling de segunda especie?

Sobre el número de Stirling de segunda clase

Un problema de Combinatoria de Brualdi sobre el cálculo de los Números de Stirling

Incapaz de probar una relación que los Números de Stirling de 2º tipo deben satisfacer

Números de Stirling de segunda clase

¿Cómo relacionar el número de todas las aplicaciones X→YX→YX\to Y con los números de Stirling del segundo tipo?

¿Cuál es la relación entre los números de Stirling y las funciones generadoras?

Factorial ascendente y número de Stirling de primera clase

Prueba combinatoria de recurrencia del número de Stirling de segunda clase