89 votos

Número de formas de escribir n como suma de k enteros no negativos

¿De cuántas maneras puedo escribir un número entero positivo $n$ como una suma de $k$ enteros no negativos hasta la conmutatividad?

Por ejemplo, puedo escribir $4$ como $0+0+4$ , $0+1+3$ , $0+2+2$ y $1+1+2$ .


Sé cómo encontrar el número de formas no conmutativas para formar la suma: Imagina una línea de $n+k-1$ posiciones, donde cada posición puede contener un gato o un divisor. Si tiene $n$ gatos (sin nombre) y $k-1$ divisores, puede dividir los gatos en $k$ grupos eligiendo las posiciones de los separadores: $\binom{n+k-1}{k-1}$ . El tamaño de cada grupo de gatos corresponde a uno de los enteros no negativos de la suma.

0 votos

Quiere el número de particiones de $n$ con un máximo de $k$ partes; esto se vuelve bastante desordenado, por decirlo suavemente.

0 votos

Ya veo. Eso explica por qué se omitió en mi clase de introducción a las matemáticas discretas. Esta pregunta surgió cuando estaba considerando preguntas de la forma "¿cuántas maneras puedo poner $k$ objetos (no) etiquetados en $n$ Grupos (des)etiquetados".

0 votos

Sí, se suele posponer al menos hasta que se llega a una clase seria de combinatoria y se aprende sobre funciones generadoras. Hay una enorme literatura sobre particiones, y algunos de los resultados no son malos, pero en general no es algo sencillo.

40voto

bentsai Puntos 1886

Como menciona Brian M. Scott, estos son particiones de $n$ . Sin embargo, permitir $0$ en la mezcla, hace que sean diferentes a la definición habitual de una partición (que asume partes no nulas). Sin embargo, esto puede ajustarse tomando particiones de $n+k$ en $k$ partes no nulas (y restando $1$ de cada parte).

Si $p(k,n)$ es el número de particiones de $n$ en $k$ distinto de cero partes, entonces $p(k,n)$ satisface la relación de recurrencia \begin{align} p(k,n) &= 0 & \text{if } k>n \\ p(k,n) &= 1 & \text{if } k=n \\ p(k,n) &= p(k+1,n)+p(k,n-k) & \text{otherwise}. \\ \end{align} (esta recurrencia se explica en Wikipedia ). Nota : en el caso anterior, recuerde cambiar $n$ a $n+k$ . Esto da un método (moderadamente eficiente) para calcular $p(k,n)$ .

El número de particiones de $n$ en $k$ piezas en $\{0,1,\ldots,n\}$ puede calcularse en GAP utilizando:

NrPartitions(n+k,k);

A continuación se enumeran algunos pequeños valores:

$$\begin{array}{c|ccccccccccccccc} & k=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 3 & 1 & 2 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\ 4 & 1 & 3 & 4 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 \\ 5 & 1 & 3 & 5 & 6 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 \\ 6 & 1 & 4 & 7 & 9 & 10 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 \\ 7 & 1 & 4 & 8 & 11 & 13 & 14 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 & 15 \\ 8 & 1 & 5 & 10 & 15 & 18 & 20 & 21 & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 \\ 9 & 1 & 5 & 12 & 18 & 23 & 26 & 28 & 29 & 30 & 30 & 30 & 30 & 30 & 30 & 30 \\ 10 & 1 & 6 & 14 & 23 & 30 & 35 & 38 & 40 & 41 & 42 & 42 & 42 & 42 & 42 & 42 \\ 11 & 1 & 6 & 16 & 27 & 37 & 44 & 49 & 52 & 54 & 55 & 56 & 56 & 56 & 56 & 56 \\ 12 & 1 & 7 & 19 & 34 & 47 & 58 & 65 & 70 & 73 & 75 & 76 & 77 & 77 & 77 & 77 \\ 13 & 1 & 7 & 21 & 39 & 57 & 71 & 82 & 89 & 94 & 97 & 99 & 100 & 101 & 101 & 101 \\ 14 & 1 & 8 & 24 & 47 & 70 & 90 & 105 & 116 & 123 & 128 & 131 & 133 & 134 & 135 & 135 \\ 15 & 1 & 8 & 27 & 54 & 84 & 110 & 131 & 146 & 157 & 164 & 169 & 172 & 174 & 175 & 176 \\ \hline \end{array}$$

Si quieres una lista de las posibles particiones, utiliza:

RestrictedPartitions(n,[0..n],k);

Comentario : En la última versión de GAP,

NrRestrictedPartitions(n,[0..n],k);

no parece funcionar correctamente aquí, ya que no coincide con

Size(RestrictedPartitions(n,[0..n],k));

cuando $k>n$ . Envié un correo electrónico al equipo de soporte sobre esto, y me dijeron que NrRestrictedPartitions y RestrictedPartitions sólo son válidos para conjuntos de números enteros positivos. (Sigo pensando que lo anterior es un error, pero dejémoslo pasar.) Esto significa que NrPartitions(n+k,k); es la opción técnicamente correcta, y, estrictamente hablando, no deberíamos usar RestrictedPartitions(n,[0..n],k); pero, a juzgar por el código fuente, funcionará como se espera.

1 votos

¡Gran respuesta! ¿Pero qué pasa si la partición tiene un límite superior?

3 votos

Creo que hay un error en la relación de recurrencia. Da una respuesta errónea y no coincide con la tabla. Haciendo $p(k,n) = p(k-1,n-1)$ y añadiendo que $p(1,n) = 1$ parece proporcionar el resultado correcto.

0 votos

Esta respuesta parece realmente errónea, ya que $k=2, n=5$ La tabla muestra 2, pero tenemos 3 formas $[(0 + 5), (1 + 4), (2 + 3)]$

11voto

Johan Puntos 11

Si sólo está interesado en un número reducido de $k$ entonces esto se resuelve más fácilmente pensando recursivamente y utilizando la inducción. Primero algo de notación. Sea $F_k(n)$ sea el número de formas de sumar $k$ números naturales por lo que la suma es $n$ .

El razonamiento genérico puede deducirse de un pequeño ejemplo.

Supongamos que tenemos tres números que queremos sumar a 4. El número de formas de hacerlo es el mismo que poner el primer dígito en $k=4,3,2,1,0$ a su vez y luego utilizando los dígitos restantes para sumar $k-1$ .

número de formas de escribir 4 con tres dígitos =

{4 + {número de formas de escribir 0 con dos dígitos}} +

{3 + {número de formas de escribir 1 con dos dígitos}} +

{2 + {número de formas de escribir 2 con dos dígitos}} +

{1 + {número de formas de escribir 3 con dos dígitos}} +

{0 + {número de formas de escribir 4 con dos dígitos}}

(Quizá quiera convencerse de que es así y de que no hay necesidad de asumir el dígito conjunto en diferentes posiciones)

Que es lo mismo que escribir (en nuestra notación)

$F_3(4) = F_2(0) + F_2(1) + F_2(2) + F_2(3) + F_2(4)$

Para el caso general tenemos

$F_k(n) = \sum_{l=0}^n F_{k-1}(l)$

también se ve fácilmente que $F_1(n)=1$ y $F_k(0)=1$ . Esto nos permite ahora ampliar las primeras relaciones como

$$F_1(n) = 1$$ $$F_2(n) = \sum_{l=0}^n F_1(l) = \frac{(n+1)}{1!}$$ $$F_3(n) = \sum_{l=0}^n F_2(l) = \sum_{l=0}^n n+1 = \frac{(n+1)^2+(n+1)}{2!}$$ $$F_4(n) = \sum_{l=0}^n F_3(l) = \frac{(n+1)^3+3(n+1)^2+2(n+1)}{3!}$$ $$F_5(n) = \sum_{l=0}^n F_4(l) = \frac{(n+1)^4 + 6(n+1)^3+11(n+1)^2+6(n+1)}{4!}$$

... y así sucesivamente

Desgraciadamente no hay ninguna expresión genérica "bonita" para los coeficientes del numerador. Es un buen ejercicio para encontrarla, pero hay que tener en cuenta que es bastante complicado, aparte de los dos coeficientes más altos y más bajos del polinomio del numerador, que probablemente se pueden detectar por inspección.

Adenda:

Factorizando el numerador y reconociendo la función Gamma la expresión puede escribirse en forma semicerrada como:

$$F_k(n) = \frac {\Gamma \left( n+k \right) }{\Gamma \left( n+1 \right) \left( k-1 \right) !}$$

1 votos

El numerador es factorizable $F_k(n)=\frac{(n+1)(n+2)\cdots(n+k-1)}{(k-1)!}$ .

0 votos

¿No debería ser la tercera fila $F_3(n) = \sum_{l=0}^n F_2(l) = \sum_{l=0}^n n-l+1 = \frac{n(n+1)}{2} + (n+1)$ y así sucesivamente para las siguientes filas? Creo que está utilizando $n$ en lugar de $l$ por error al llamar a $F_{k-1}(l)$

7voto

Tom Ferguson Puntos 329

Un enfoque mucho más sencillo y matemático:

Este problema equivale a encontrar el coeficiente de $x^N$ en la expresión $f(x) = (1+x+x^2+x^3+\dots +x^N)^M$

Entonces $f(x) = ((x^{(N-1)} - 1)/(x-1))^M$ . Diferéncielo $M$ veces (así que use $\frac{d^Nf(x)}{dx^N}$ ) y el coeficiente será $(\frac{1}{n!})\left(\frac{d^Nf(x)}{dx^N}\right)$ en $x = 0$ ; la diferenciación puede realizarse mediante cualquier técnica de diferenciación numérica. Por lo tanto, la complejidad del algoritmo es $O(N\times \text{the complexity of differentiation})$ .

3 votos

Um... ¿Cómo es equivalente? Ese coeficiente sería el número de sumas no conmutativas diferentes. Pero la pregunta es sobre el número de sumas conmutativas diferentes.

2voto

Lee Theobald Puntos 141

Recientemente he resuelto un problema similar: ¿de cuántas maneras pueden caer 1024 elementos en 16 franjas del histograma? Esta es esencialmente la misma pregunta, y el problema con el que coincide es el número de particiones desordenadas (no nos importa en qué orden se rellenan los números, escribir, por ejemplo, 1024 = 512 + 256 + 256 + 0's es lo mismo que 1024 = 0's + 256 + 512 + 256, o cualquier otro).

Como mi problema es bastante grande, he escrito código C++ para contar sólo las particiones o también enumerarlas. Consíguelo en http://www.stud.fit.vutbr.cz/~xpolok00/proj/UnPart.h . Se puede utilizar:

CUnorderedPartition(n, k).n_Partition_Num()

para obtener sólo el número de particiones. Para n = 1024 y k = 16, devolverá 6561153029810 en unos dos días de tiempo en un ordenador medio.

Para evaluar también las pariciones, se puede, por ejemplo, utilizar:

CUnorderedPartition part(10, 3); // write 10 as a sum of 3 numbers
do {
    cout << part.r_Bin_Values()[0] << ", " <<
            part.r_Bin_Values()[1] << ", " <<
            part.r_Bin_Values()[2] << endl;
} while(part.b_Next()); // is there a next combination?
cout << "that was " << part.n_Partition_Num() << " partitions" << endl;

Y que escribirá:

0, 0, 10
0, 1, 9
0, 2, 8
0, 3, 7
0, 4, 6
0, 5, 5
1, 1, 8
1, 2, 7
1, 3, 6
1, 4, 5
2, 2, 6
2, 3, 5
2, 4, 4
3, 3, 4
that was 14 partitions

Puedes ver en la tabla que el resultado es correcto. Los valores siempre saldrán ordenados de forma ascendente (ya que genera desordenado particiones). Enumerar las particiones es un poco más lento, para 1024, 16 tarda unos tres días.

2voto

Tom Ferguson Puntos 329

Tengo un enfoque mucho más simple usando DP que no toma un tiempo exponencial para calcular el número de partición. He verificado esto con ciertos valores pequeños aunque para n=1024 y k=16 obtuve una respuesta diferente. La siguiente es la implementación en java del problema. Tiene tres partes independientes:

  1. Divide S en K partes. Las partes pueden tener valor 0 y el orden importa, es decir, 10 = 0+5+5+0 y 10=5+5+0+0 son diferentes
  2. Divide S en K partes. Las partes no pueden tener valor 0 y el orden importa, es decir, 10 no puede tener valor 0+5+5+0 pero 10 puede ser 1+4+4+1 y 4+4+1+1
  3. Divide S en K partes. Las partes pueden tener valor 0, pero el orden no importa, es decir, 10 = 0+5+5+0 y 10=5+5+0+0 son iguales.

    public class Main {
    public static void main(String[] args) throws Exception {
        int S = 10, K = 4;
        System.out.println("S=" + S + "   K=" + K);
        System.out.println(PartionwithZero(S, K));
        System.out.println(PartionwithoutZero(S, K));
        System.out.println(PartionwithZeroUnique(S, K));
    }
    
    /* Divide S in K parts 0 may be present */
    public static long PartionwithZero(int S, int K) {
        long DP_Table[][] = new long[K][];
        for (int i = 0; i < K; i++)
            DP_Table[i] = new long[S + 1];
        for (int i = 0; i < S + 1; i++)
            DP_Table[0][i] = 1;
        for (int i = 0; i < K; i++)
            DP_Table[i][0] = 1;
    
        for (int i = 1; i < K; i++) {
            for (int j = 1; j < S + 1; j++)
                DP_Table[i][j] = DP_Table[i - 1][j] + DP_Table[i][j - 1];
        }
    
        /*
         * for(long i=0;i<K;i++) { for(long j=0;j<S+1;j++)
         * System.out.prlong(DP_Table[i][j]+" "); System.out.println(); }
         */
        return DP_Table[K - 1][S];
    }
    
    /* Divide S in K parts 0 should not be present */
    public static long PartionwithoutZero(int S, int K) {
        long DP_Table[][] = new long[K][S];
        for (int i = 0; i < S; i++)
            DP_Table[0][i] = 1;
        for (int i = 1; i < K; i++)
            DP_Table[i][0] = 0;
    
        for (int i = 1; i < K; i++) {
            for (int j = 1; j < S; j++)
                DP_Table[i][j] = DP_Table[i - 1][j - 1] + DP_Table[i][j - 1];
        }
    
        /*
         * for(long i=0;i<K;i++) { for(long j=0;j<S;j++)
         * System.out.print(DP_Table[i][j]+" "); System.out.println(); }
         */
        return DP_Table[K - 1][S - 1];
    }
    
    /* Divide S in K parts 0 may be present */
    public static long PartionwithZeroUnique(int S, int K) {
        long DP_Table[][][] = new long[K][S + 1][S + 1]; // DP_Table[no of
                                                            // partition][Sum][Maximum
                                                            // value in the
                                                            // partition]
    
        for (int i = 0; i < K; i++)
            DP_Table[i][0][0] = 1;
        for (int i = 1; i < S + 1; i++) {
            DP_Table[0][i][0] = 0;
            DP_Table[0][i][i] = 1;
        }
        for (int i = 1; i < S + 1; i++)
            DP_Table[0][0][i] = 0;
    
        for (int i = 0; i < S + 1; i++)
            for (int j = 0; j < i; j++)
                DP_Table[0][i][j] = 1;
    
        for (int i = 1; i < K; i++) {
            for (int j = 1; j < S + 1; j++)
                for (int k = 1; k < S + 1; k++) {
                    // System.out.println(i+" "+j+" "+k);
                    DP_Table[i][j][k] = (k - j) >= 0 ? DP_Table[i - 1][j][k - j]
                            : 0;
                }
            for (int k = 0; k < S + 1; k++) {
                long sum = 0;
                for (int j = 0; j < S + 1; j++) {
                    DP_Table[i][j][k] += sum;
                    sum = DP_Table[i][j][k];
                }
            }
        }
    
        /*
         * for(int i=0;i<K;i++) { System.out.println("K ="+i); for(int
         * j=0;j<S+1;j++) { for(int k=0;k<S+1;k++)
         * System.out.print(DP_Table[i][j][k]+" "); System.out.println(); }
         * System.out.println(); System.out.println(); }
         */
        return DP_Table[K - 1][S][S];
    }

    }

A continuación se muestran los resultados de algunos casos:

S=6 K=3 28 10 7

S=10 K=3 66 36 14

S=20 K=12 84672315 75582 582

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