EL PROBLEMA DE LOS CONTENEDORES
Como resultado de una consulta sobre permutaciones, Miguel Á. Lerma mandó este soberbio artículo, que vale la pena reproducir.
Ese problema se puede formular en general de la siguiente forma: ¿de cuántas maneras distintas se pueden repartir n objetos en r contenedores? En realidad se trata de cuatro problemas en uno:
1. Si los contenedores y los objetos son distintos (o "distinguibles"), de modo que intercambiar dos objetos situados en contenedores diferentes da lugar a una repartición distinta, entonces el resultado es igual al número de lugares donde podemos colocar el primer objeto, multiplicado por el número de lugares donde podemos poner el segundo, etc. El resultado es igual a r×r×r ...× r = rn.
Si ningún contenedor debe quedar vacío, entonces el
problema equivale
a hallar el número de aplicaciones suprayectivas de
un conjunto de
n elementos a otro de r elementos. La solución es:
donde S2(n,r) representa el número de Stirling
de segunda especie con argumentos (n,r).
2. Si los objetos son idénticos (o "indistinguibles")
pero los contenedores son distintos, entonces cada repartición se puede
representar alineando los n objetos y separándolos de
todas las formas posibles con r-1 marcas intercaladas entre ellos. El resultado
es el número de permutaciones de n+r-1 items (objetos más marcas), donde hay n repetidos y otros
r-1 repetidos. En total, 
.
Si no deben quedar contenedores
vacíos entonces ponemos un objeto en
cada uno de los r contenedores y repartimos los n-r objetos restantes según el
procedimiento anterior. Ahora la solución sería 
.
3. Si los objetos son distintos pero los contenedores son idénticos no pudiendo quedar contenedores vacíos, entonces la solución se puede obtener dividiendo por r! la solución obtenida en la segunda parte del caso 1. El resultado es el número de Stirling de segunda especie:
Si pueden quedar contenedores
vacíos, entonces el resultado es 
.
4. Si los objetos y los contenedores son idénticos, entonces cada repartición se llama una "partición" de n. No hay una fórmula explícita para el número de particiones de n, pero hay estimaciones asintóticas, como la proporcionada por la fórmula de Hardy-Ramanujan (1918):
El problema se puede abordar también con la teoría de funciones generatrices, en particular el número de particiones de n es igual al coeficiente de xn en el desarrollo en serie de potencias de la función:
Si truncamos el producto en el factor k=m entonces obtenemos la función generatriz del número de particiones de n con sumandos no mayores que m.
De todos modos, el cálculo de las particiones carece por el momento de fórmula explícita para el término n-simo. Lo más parecido a ella es la fórmula de Rademacher, serie infinita cuyo primer término es precisamente la fórmula asíntótica de Hardy-Ramanujan. Eso sí, se puede calcular mediante fórmulas recurrentes, la más conocida de las cuales es la de Euler:
Para n < 0, p(n) = 0
Para n = 0, p(0) = 1
Para n>0:
Donde w(k)=k(3k-1)/2 es el k-simo número pentagonal. La suma antes indicada sólo contiene un número finito de términos no nulos.
Por ejemplo: p(12) = p(12-1) + p(12-2) - p(12-5) - p(12-7) + p(12-12) = p(11) + p(10) – p(7) – p(5) + p(0) = 56 + 42 – 15 – 7 + 1 = 77.
Éstos son los primeros términos de la sucesión:
|
n |
p(n) |
|
0 |
1 |
|
1 |
1 |
|
2 |
2 |
|
3 |
3 |
|
4 |
5 |
|
5 |
7 |
|
6 |
9 |
APÉNDICE
Los números de Stirling, que aparecen en la solución de los casos 1 y 3, verifican una propiedad que recuerda la de los números combinatorios:
S1(n+1,r) = S1(n,r-1) + nS1(n,r)
S2(n+1,r) = S2(n,r-1) + rS2(n,r)
Esa propiedad se puede aprovechar
para calcular números de Stirling
formando un triángulo similar al de Pascal:
|
NÚMEROS DE STIRLING DE PRIMERA
ESPECIE |
n! |
|||||||||||
|
k\n |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
|
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
2 |
|
1 |
1 |
|
|
|
|
|
|
2 |
|
|
|
3 |
|
2 |
3 |
1 |
|
|
|
|
|
6 |
|
|
|
4 |
|
6 |
11 |
6 |
1 |
|
|
|
|
24 |
|
|
|
5 |
|
24 |
50 |
35 |
10 |
1 |
|
|
|
120 |
|
|
|
6 |
|
120 |
274 |
225 |
85 |
15 |
1 |
|
|
720 |
|
|
|
7 |
|
720 |
1764 |
1624 |
735 |
175 |
21 |
1 |
|
5040 |
|
|
|
8 |
|
5040 |
13068 |
13132 |
6769 |
1960 |
322 |
28 |
1 |
40320 |
|
|
|
NÚMEROS DE STIRLING DE SEGUNDA
ESPECIE |
n! |
|||||||||
|
k\n |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
2 |
|
1 |
1 |
|
|
|
|
|
|
2 |
|
3 |
|
1 |
3 |
1 |
|
|
|
|
|
5 |
|
4 |
|
1 |
7 |
6 |
1 |
|
|
|
|
15 |
|
5 |
|
1 |
15 |
25 |
10 |
1 |
|
|
|
52 |
|
6 |
|
1 |
31 |
90 |
65 |
15 |
1 |
|
|
203 |
|
7 |
|
1 |
63 |
301 |
||||||