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.
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.