Cómo son las soluciones de las distintas soluciones no negativas para $k_1+\cdots+k_n=k$ ?

Question

Cuántos distintos $n$ -tuplas con elementos enteros distintos no negativos que se suman a $k$ .

Por ejemplo, hay $6$ triples que se suman a $4$ . A saber: $(0, 1, 3)$ y su $6$ permutaciones. ¿Existe una fórmula para esta cantidad? Lo he intentado con todas mis fuerzas pero sin suerte.

Esta pregunta también puede reformularse como:

¿Cuántos conjuntos de soluciones no negativas hay para $k_1+\cdots+k_n=k$ donde $k_i\ne k_j$ .

Es obvio que el más pequeño $k$ sería $\frac{n(n-1)}{2}$ .

---

Otro ejemplo sería

¿Cuántos pares de enteros distintos no negativos hay que sumen $6$ ? Claramente es el número de composiciones de longitud $2$ con términos distintos y $2!$ veces el número de composiciones de longitud $1$ con términos distintos (cómo contar los ceros). Obtenemos

$0+6$ , $1+5$ , $2+3$ , $3+2$ , $5+1$ , $6+0$

Así que hay $6$ tales pares.

---

Debo señalar que la respuesta puede darse en términos de la función de partición. Que da cuántas maneras puede un entero ser escrito como una suma de enteros positivos.

Answer 1

A modo de enriquecimiento me gustaría señalar que utilizando el Teorema de Enumeración de Polya la forma cerrada también viene dada por

$$n! [z^k] Z(P_n)\left(\frac{1}{1-z}\right)$$

donde $Z(P_n) = Z(A_n)-Z(S_n)$ es la diferencia entre el índice de ciclo del grupo alterno y el índice de ciclo del grupo simétrico simétrico. Este índice de ciclo se conoce en la teoría de especies como el operador de conjunto $\mathfrak{P}_{=n}$ y la ecuación de la especie aquí es

$$\mathfrak{P}_{=n}\left(\mathcal{E} + \mathcal{Z} + \mathcal{Z}^2 + \mathcal{Z^3} + \cdots\right).$$

Recordemos la recurrencia de Lovasz para el índice de ciclo $Z(P_n)$ de el operador de conjunto $\mathfrak{P}_{=n}$ en $n$ ranuras, que es $$Z(P_n) = \frac{1}{n} \sum_{l=1}^n (-1)^{l-1} a_l Z(P_{n-l}) \quad\text{where}\quad Z(P_0) = 1.$$ Esta recurrencia nos permite calcular el índice del ciclo $Z(P_n)$ muy fácilmente.

Por ejemplo, cuando $n=3$ como en la introducción del problema el ciclo es $$Z(P_3) = 1/6\,{a_{{1}}}^{3}-1/2\,a_{{2}}a_{{1}}+1/3\,a_{{3}} $$ y la función generadora se convierte en $$1/6\, \left( 1-z \right) ^{-3}-1/2\,{\frac {1}{ \left( -{z}^{2}+1 \right) \left( 1-z \right) }}+1/3\, \left( -{z}^{3}+1 \right) ^ {-1} $$ que da la secuencia $$0, 0, 6, 6, 12, 18, 24, 30, 42, 48, 60, 72, 84, 96,\ldots$$ que es seis veces OEIS A069905 .

Del mismo modo, cuando $n=5$ obtenemos el índice de ciclo $$Z(P_5) = {\frac {{a_{{1}}}^{5}}{120}}-1/12\,a_{{2}}{a_{{1}}}^{3}+1/6\,a_{{ 3}}{a_{{1}}}^{2}+1/8\,a_{{1}}{a_{{2}}}^{2}\\-1/4\,a_{{4}}a_{{1}}-1/ 6\,a_{{2}}a_{{3}}+1/5\,a_{{5}}$$ y la función generadora se convierte en $${\frac {1}{120\, \left( 1-z \right) ^{5}}}-1/12\,{\frac {1}{ \left( -{z}^{2}+1 \right) \left( 1-z \right) ^{3}}}\\+1/6\,{ \frac {1}{ \left( -{z}^{3}+1 \right) \left( 1-z \right) ^{2}}}+1 /8\,{\frac {1}{ \left( -{z}^{2}+1 \right) ^{2} \left( 1-z \right) }}-1/4\,{\frac {1}{ \left( -{z}^{4}+1 \right) \left( 1- z \right) }}\\-1/6\,{\frac {1}{ \left( -{z}^{2}+1 \right) \left( - {z}^{3}+1 \right) }}+1/5\, \left( -{z}^{5}+1 \right) ^{-1}$$ que da la secuencia $$0, 0, 0, 0, 0, 0, 0, 0, 0, 120, 120, 240, 360, 600, \ldots$$ que es $120$ veces OEIS A001401 .

El prefijo de ceros (estos dos ejemplos empiezan por el uno) en comparación con las dos entradas OEIS representa el hecho de que el valor mínimo alcanzable con $n$ sumandos distintos en $$[z^k] Z(P_n)\left(\frac{1}{1-z}\right)$$ es $0+1+2+\cdots+n-1 = 1/2\times n\times (n-1).$

Estas secuencias coinciden con la fórmula de @bof, que es $$n! p_n\left(k - \frac{1}{2} n (n - 3)\right).$$

Hay muchos más enlaces relacionados en MSE Meta en Burnside/Polya .

El código de Maple para estos era el siguiente.

p :=
proc(n, k)
    option remember;

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

    p(n-1, k-1)+p(n-k,k)
end;

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\_cycleind\_set :=
proc(n)
        local p, s;
        option remember;

        if n=0 then return 1; fi;

        expand(1/n\*add((-1)^(l-1)\*
        a\[l\]\*pet\_cycleind\_set(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;

q1 :=
proc(n, k)
option remember;
    local gf;

    gf := pet\_varinto\_cind(1/(1-z), pet\_cycleind\_set(n));
    n!\*coeftayl(gf, z=0, k);
end;

q2 :=
proc(n, k)
option remember;
    n!\*p(k-n\*(n-3)/2, n);
end;

Adenda. Según la petición, ahora damos una prueba mixta (combinatoria, algebraica) de la identidad $$[z^n] Z(P_k)\left(\frac{1}{1-z}\right) = p_k\left(n - \frac{1}{2} k(k-3)\right).$$

Obsérvese que hemos vuelto a la convención estándar de utilizar $n$ para la suma de la partición y $k$ para el número de piezas.

Por la misma construcción que antes (PET) tenemos $$p_k\left(n - \frac{1}{2} k(k-3)\right) = [z^{n- \frac{1}{2} k(k-3)}] Z(S_k)\left(\frac{z}{1-z}\right)$$ con $Z(S_k)$ que es el índice de ciclo del grupo simétrico (sin etiquetar conjuntos múltiples con el operador $\mathfrak{M}_{=k}$ .)

Utilizando el álgebra básica esto se convierte en $$[z^{n- \frac{1}{2} k(k-3)}] z^k Z(S_k)\left(\frac{1}{1-z}\right) = [z^{n- \frac{1}{2} k(k-3) -\frac{1}{2} 2k}] Z(S_k)\left(\frac{1}{1-z}\right) \\ = [z^{n- \frac{1}{2} k(k-1)}] Z(S_k)\left(\frac{1}{1-z}\right).$$

Pero esta es la especie $$\mathfrak{M}_{=k}\left(\mathcal{E} + \mathcal{Z} + \mathcal{Z}^2 + \mathcal{Z^3} + \cdots\right),$$ es decir, particiones con constituyentes vacíos permitidos y constituyentes no necesariamente distintos.

Sin embargo, existe una biyección directa entre éstas y particiones con constituyentes potencialmente vacíos pero distintos. Para pasar de las primeras a las segundas hay que añadir $q$ círculos a la izquierda de cada fila en el diagrama de Ferrers con índices de fila $q$ a partir de cero. Ahora bien, si tuviéramos dos filas adyacentes con la primera por encima de la segunda con longitud $b_1$ y $a_1$ donde $b_1\ge a_1$ entonces el par resultante es $b_1+q$ y $a_1+q-1.$ La diferencia entre estos es $b_1-a_1+1\ge 1$ por lo que el nuevo par es distinto y en orden no decreciente visto desde abajo. Para pasar de lo segundo a lo primero eliminar $q$ círculos de cada fila (el índice es $q$ ), girando $b_2$ y $a_2$ donde $b_2>a_2$ en $b_2-q$ y $a_2 -(q-1).$ La diferencia es $b_2-a_2-1\ge 0$ y el par es orden no decreciente pero no necesariamente distinto. El número de círculos que se añaden/quitan es
$$\sum_{q=0}^{k-1} q = \frac{1}{2} k(k-1).$$

Hemos demostrado que $$ [z^{n- \frac{1}{2} k(k-1)}] Z(S_k)\left(\frac{1}{1-z}\right) = [z^n] Z(P_k)\left(\frac{1}{1-z}\right).$$ Aquí tenemos $n\ge \frac{1}{2} k (k-1),$ ambos lados son cero en caso contrario. Con esto concluye el argumento.

Answer 2

Esto es realmente un comentario a la respuesta de yashg (ahora borrada); sólo quiero aportar un poco de contexto y una referencia.

Para evitar repeticiones: todas las variables de este post están restringidas a números enteros.

El título de la pregunta es algo confuso: el vector $(0,1,3)$ es un solución , no un "conjunto de soluciones", de la ecuación multivariable $k_1+k_2+k_3=4$ . Estás preguntando por el número de soluciones de la ecuación $k_1+\cdots+k_n=k$ donde $k_1,\dots,k_n$ son enteros no negativos distintos. Por cierto, creo que es habitual en la literatura (al menos, en la referencia de Wikipedia que voy a dar) intercambiar los papeles de $k$ y $n$ en este tipo de problemas.

La respuesta es en términos de la muy estudiada función de partición $p_k(n)$ que se define como el número de soluciones de la ecuación $x_1+\cdots+x_k=n$ donde $x_1\ge x_2\ge\cdots\ge x_k\ge1$ Esas soluciones se denominan particiones de $n$ en (exactamente) $k$ piezas . Para las instalaciones fijas $k$ la función generadora es $$\sum_{k=0}^\infty p_k(n)x^n=\frac{x^k}{(1-x)(1-x^2)\cdots(1-x^k)}.$$ Para $n\ge k\gt1$ tenemos la ecuación de recurrencia $$p_k(n)=p_{k-1}(n-1)+p_k(n-k),$$ desde $p_{k-1}(n-1)$ es el número de particiones de $n$ en $k$ partes con la parte más pequeña igual a $1$ , mientras que $p_k(n-k)$ es el número de particiones de $n$ en $k$ piezas $\ge2$ . Utilizando la ecuación de recurrencia y las condiciones de contorno obvias $p_k(n)=0$ para $n\lt k$ y $p_1(n)=1$ para $n\gt0$ podemos calcular los valores de $p(n,k)$ y derivar fórmulas cerradas para las $k$ Por ejemplo, $p_2(n)=\lfloor\frac n2\rfloor$ , $p_3(n)=\lfloor\frac{n^2+3}{12}\rfloor$ etc.

A continuación, la transformación $y_j=x_j+1-k+j$ muestra que el número de soluciones de la ecuación $x_1+\cdots+x_k=n$ con $x_1\gt x_2\gt\cdots\gt x_k\ge0$ es igual al número de soluciones de $y_1+\cdots+y_k=n-\frac{k(k-3)}2$ con $y_1\ge y_2\ge\cdots\ge y_k\ge1$ Es decir, $p_k(n-\frac{k(k-3)}2)$ .

Dado que su pregunta permite que los sumandos estén dispuestos en cualquier orden, y dado que todos son distintos, el número de soluciones de $x_1+\cdots+x_k=n$ donde $x_1,\dots,x_k$ son enteros no negativos distintos es $k!\,p_k(n-\frac{k(k-3)}2)$ o en su notación:

El número de soluciones de $k_1+\cdots+k_n=k$ donde $k_1,\dots,k_n$ son enteros no negativos distintos es $$n!\,p_n(k-\frac{n(n-3)}2).$$

Answer 3

Creo que he encontrado una solución, pero os toca a todos comprobar que es correcta. Aquí va:

Tenemos que encontrar el número de soluciones integrales no negativas de : $$k_1+k_2+....+k_n=P$$ donde $k_i\in \{ 0,1,2,3,.....\}$ , $P\in\{1,2,3,4,....\}$ y $k_i\ne k_j$

Como todos los números del LHS son distintos, podemos suponer por simplicidad que $k_i<k_{i+1}$

Con esta suposición, dejemos: $$k_1=k_1+0$$$$ k_2=k_1+a_1 $$$$.$$$$ . $$$$.$$$$ k_n=k_{n-1}+a_{n-1} $$ where $ a_i\in \{ 1,2,3,.....\}$

Entonces, $$k_1+k_2+...+k_n=k_1+(k_1+a_1)+(k_1+a_1+a_2)+...+(k_1+a_1+...a_{n-1})$$ $$k_1+k_2+...+k_n=nk_1+(n-1)a_1+(n-2)a_2+...+2a_{n-2}+a_{n-1}$$ Así que tenemos que encontrar las soluciones a $$nk_1+(n-1)a_1+(n-2)a_2+...+2a_{n-2}+a_{n-1}=P$$ Como no sé cómo tratar con números naturales, reescribo la ecuación como $$nk_1+(n-1)b_1+(n-2)b_2+...+2b_{n-2}+b_{n-1}=P-\binom{n}{2}$$ donde $b_i\in \{0,1,2,3,.....\}$

Ahora muy fácilmente podemos escribir el multinomio en el que tendremos el coeficiente de $x^{P-\binom{n}{2}}$ como el número de conjuntos de soluciones. Que podemos multiplicar por $n!$ para obtener el número deseado de tuplas. Doy la respuesta final como $C$ multiplicado por $n!$ , donde $C$ es el coeficiente de $x^{P-\binom{n}{2}}$ en la expansión de $$(1+x^n+x^{2n}+...+x^{n\lfloor\frac{P-\binom{n}{2}}{n}\rfloor})(1+x^{n-1}+x^{2n-2}+...+x^{(n-1)\lfloor\frac{P-\binom{n}{2}}{n-1}\rfloor}).....(1+x+x^2+....+x^{P-\binom{n}{2}})$$ NOTA : Si no es visible, el poder de $x$ en los últimos términos de los paréntesis tiene una función de suelo. Si todavía no está claro, es ${n\lfloor\frac{P-\binom{n}{2}}{n}\rfloor}$ en el primer paréntesis, y luego sigue disminuyendo n en 1 en los siguientes paréntesis.

COMPROBACIÓN DE LA FÓRMULA

En primer lugar, tomemos su primer caso en el que $n=3$ y $P=4$ . La expresión será $(x^0)(x^0)(x^0)$ en el que el coeficiente de $x^0$ es 1. Que multiplicamos por 3 para obtener la respuesta 6.

Ahora tomemos tu segundo caso en el que $n=2$ y $P=6$ . La expresión será $(1+x^2+x^4)(1+x+x^2+x^3+x^4+x^5)$ en el que el coeficiente de $x^5$ es 3. Que multiplicamos por 2 para obtener 6.

Answer 4

No es mi especialidad, pero creo que lo que buscas se llama en la literatura composiciones de $k$ en $n$ partes distintas .

Probablemente pueda encontrar la respuesta en el siguiente artículo de 1995 de B.Richmond y A.Knopfmacher "Compositions with distinct parts" ( enlace ), al que desgraciadamente no tengo acceso.

La función generadora del número de composición de $k$ en $n$ partes distintas también se da al final de la siguiente preimpresión y posiblemente se podría derivar una fórmula cercana a ella.

Answer 5

Si $k_i$ no son distintos, entonces los caminos totales sí lo son: $$\sum_{i}^nk_i=k,k_i\ge0\longrightarrow \binom{k+n-1}{n-1}$$ Ahora tenemos que utilizar la inclusión-exclusión para eliminar los casos en los que dos o más $k_i$ son iguales, tenga en cuenta que debe tener más cuidado al utilizar la inclusión-exclusión porque al tomar por ejemplo $k_1$ y $k_2$ igual puede darse el caso de que $k_3=k_4,k_1\ne k_3$ , ni siquiera eso pues puede ser que al mismo tiempo grupos de 2,3 y 4 elementos sean iguales y esto puede requerir mucho trabajo que me salto aquí.