miércoles, 2 de febrero de 2011

Particiones de un número

Seguimos con el tema de las piezas de construcción y su distribución en lotes. Indicábamos que 9 piezas se podían distribuir de 30 formas diferentes. Lo concretamos un poco:

Se llaman particiones de un número natural N a las distintas formas de descomponerlo en sumandos enteros positivos sin tener en cuenta el orden y admitiendo repetición de sumandos.  Para no tener en cuenta el orden se puede exigir que los sumandos sean decrecientes en sentido amplio.  Así es más fácil representarlos.

Al número total de particiones de N lo representaremos por la función P(N). Por tanto la afirmación anterior se puede representar como P(9)=30.

En efecto, el 9 se puede descomponer en estas sumas:


9,   8+1,  7+2,   7+1+1,   6+3,   6+2+1,   6+1+1+1,   5+4,   5+3+1, 5+2+2 
5+2+1+1,   5+1+1+1+1,   4+4+1,  4+3+2,  4+3+1+1,   4+2+2+1,   4+2+1+1+1 
4+1+1+1+1+1,   3+3+3,  3+3+2+1,   3+3+1+1+1, 3+2+2+2,   3+2+2+1+1,   3+2+1+1+1+1
3+1+1+1+1+1+1, 2+2+2+2+1, 2+2+2+1+1+1, 2+2+1+1+1+1+1, 2+1+1+1+1+1+1+1 
1+1+1+1+1+1+1+1+1

Son 30 en total

Cada posible suma se puede representar mediante los llamados diagramas de Ferrer, en los que los sumandos se dibujan como conjuntos en filas.

Por ejemplo, 3+2+2+1+1 se puede representar así:

OOO
OO
OO
O
O

Puedes investigar en la Red las propiedades de estos diagramas.

El número de particiones se corresponde con el de soluciones no negativas de la ecuación diofántica

1x1+2x2+3x3+…Nxn = N

como es fácil demostrar.

También coincide con  el de soluciones no negativas de la ecuación diofántica

x1+x2+x3+…xn = N

si se exige que las soluciones formen una sucesión no creciente:

x1>=x2>=x3>=…xn

Igualmente, representa también las formas de repartir N objetos indistinguibles en cajas indistinguibles. En la imagen, extraída de una hoja de cálculo, puedes observar la distribución de seis bolas (11 particiones del número 6)



Más adelante estudiaremos otras funciones de partición condicionada de un número y su cálculo.

Mientras tanto te puedes dedicar a comprobar (con piezas, bolitas o lápiz) estos resultados:

N    P(N)
1     1
2     2
3     3
4     5
5     7
6     11
7     15
8     22
9     30
10   42
11   56
12   77

No perderás el tiempo, porque es divertido encontrar estrategias para no olvidar ninguna suma.