Regresos 16 (1): Particiones condicionadas de un número natural

En el año 2017 publiqué en mi blog “Números y hoja de cálculo” (https://hojaynumeros.blogspot.com/) una serie de estudios sobre particiones de un número obtenidas mediante mi herramienta Cartesius.

Quedé bastante satisfecho, pero echaba de menos poder estudiar las particiones de un número (formas de descomponer un número natural en sumandos) para valores mayores que doce, que es el máximo que me permitía Cartesius. He despojado los algoritmos de esta herramienta de muchas opciones, y me he quedado con lo imprescindible para calcular números de particiones condicionadas. Sigue siendo un proceso lento, pero me permite, con paciencia, abordar cálculos para números mayores que doce.

Lo he incorporado a la hoja “Buscador”, que tengo preparada para su descarga gratuita (https://www.hojamat.es/blog/buscador1.xlsm), y con ella, y sin abandonar Cartesius, ampliaré los trabajos del año 2017.

Tres herramientas

Esta va a ser una serie de entradas, por lo que es conveniente realizar una presentación previa de las mismas. En primer lugar, hay que advertir que el espíritu de ellas es el de aprendizaje y ejercitación. En este tema está todo publicado, y desde este blog poco se puede añadir, pero sí resulta atractivo cotejar distintos métodos para llegar a un mismo objetivo.  El mejor y más aconsejable sería el de trabajar con papel y bolígrafo, que es como mejor se aprende, pero al final se terminará recurriendo a herramientas informáticas.

Usaremos, de forma más o menos simultánea, tres herramientas básicas:

Cartesius

Es mi herramienta tradicional para construir productos cartesianos condicionados. En el tema de particiones ya he publicado muchos ejemplos, y resulta bastante sencilla de entender. Sus condiciones resultan claras.

Descargable desde

https://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius

Buscador

En el archivo descargable presentado más arriba he situado, en su tercera hoja, una subrutina para realizar el mismo trabajo que el de Cartesius, pero que no sufre la restricción de las doce columnas. Resulta también más rápida, ya que el que no sea tan general le dota de más velocidad, pero nunca suficiente, porque todos los temas de Combinatoria acaban por abordar cálculos que resultan muy lentos.

Dirección de descarga: https://www.hojamat.es/blog/buscador1.xlsm

PARI

Este lenguaje posee herramientas potentes y rápidas, aunque adolece de falta de presentaciones intuitivas. Está dirigido a profesionales, pero en este blog le hemos conseguido mucha utilidad. Su orden FORPART será un pequeño tesoro para comprobar cálculos o ampliarlos.

Página web: https://pari.math.u-bordeaux.fr/gpwasm.html

 Algoritmo básico

Las particiones actúan sobre conjuntos de sumandos. Por ejemplo, si deseo descomponer el número 20 en cuatro sumandos primos, deberé usar el conjunto (2, 3, 5, 7, 11, 13, 17, 19). El resultado final es que existen 6 particiones distintas.

 Particiones condicionadas                         

Número:    20             

Número de particiones: 6

Conjunto de particiones: 5 5 5 5, 7 5 5 3, 7 7 3 3, 11 3 3 3, 11 5 2 2,       13 3 2 2

En algunas ocasiones, el número de particiones condicionadas proviene de operaciones sobre conjuntos de números sometidos a alguna operación (condición previa). Por ejemplo, podemos estar interesados en particiones en las que las partes sean todas libres de cuadrados, o que pertenezcan a la sucesión de Fibonacci. Esta será la condición previa en cada caso.

El manejo de cuatro números que no tienen que guardar relación entre ellos nos lleva, en el nivel elemental de algoritmos en el que se mueve esta serie, a usar bucles anidados: FOR I=12 T0…FOR J=12 TO…FOR K=12 TO… Esto supone una gran ineficiencia y poca versatilidad, porque el número de bucles debería adaptarse a cada ejemplo determinado.

Desde hace muchos años llevo usando punteros sobre una matriz rectangular (es una imagen para entendernos) en el que van avanzando por los distintos elementos llevando algún tipo de recuerdo de los que ya han visitado.

Concretando el ejemplo del primer párrafo, imaginemos que estudiamos el rango de números entre 40 y 50, y buscamos en ellos conjuntos de cuatro números con la propiedad pedida. Llamamos, por ejemplo, INICIO al valor mínimo (40 en este caso) y TOPE o FINAL al último (50). Por otra parte, daremos el nombre de NUME al número de elementos que tendrán nuestros conjuntos. Desde INICIO hasta final llamaremos E(I) a cada valor concreto de un elemento. En la imagen que sigue sería una columna, mientras que horizontalmente se representarían los elementos elegidos de izquierda a derecha, que será el “movimiento” que tendrá el puntero.

 

Al principio cuesta un poco entender la dinámica de este proceso, pero compensa el no tener que anidar bucles. En mis herramientas de ayuda a la enseñanza lo he usado, entre otros, en estas tres:

Combimaq (https://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#combimaq)

Cartesius

(https://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius)

Partlista (https://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#reprenum)

En la siguiente entrada se desarrollarán estas ideas.

 

Submulticonjuntos (2)

 Representación numérica de un multiconjunto

Con lo visto hasta ahora en la anterior entrada, lo esencial en un multiconjunto lo constituyen las multiplicidades. La naturaleza de los elementos no influye apenas en los conteos. Es un fenómeno similar a la descomposición en factores primos, que muchas funciones dependen tan solo de los exponentes. Esto nos permite representar un multiconjunto como un número, de forma unívoca. De las posibilidades existentes (hay variantes en la tarea de representar un multiconjunto mediante un número, como, por ejemplo, los números de Heinz), elegiremos aquí las siguientes:

·      Ordenamos las multiplicidades de mayor a menor (para que el número resultante sea lo más pequeño posible)

·      A cada multiplicidad correspondiente a un elemento dado le asignamos un número primo repetido, siguiendo el orden natural (algunos autores comienzan con el 1). En caso de empate, no hay problema, porque resulta el mismo número.

·   Si multiplicamos todos esos primos, resultará un número que poseerá una relación biunívoca con el conjunto.

Por ejemplo, en la palabra ZARAGOZA ordenamos las multiplicidades vistas en la entrada anterior: 3 de A, 2 de Z y 1 del resto de caracteres, R, G y O.

Sustituimos cada multiplicidad por números primos repetidos y ordenados:

2*2*2*3*3*5*7*11=27720.

Este número identifica, de forma unívoca, a todos los multiconjuntos con la serie de multiplicidades 3, 2, 1, 1, 1. Cada submulticonjunto de ellos se relacionará con un divisor de 27720, por el criterio general de divisibilidad, en el que los factores primos de los divisores son subconjuntos de los correspondientes en 27720.

Pedimos los divisores de 27720 con bigomega=3 (tres factores primos) en cualquier buscador, o con la función siguiente:

Function dosfact$(n, k)

Dim i

s = ""

For i = 2 To n

If n / i = n \ i Then

If bigomega(i) = k Then

s = s + ajusta(i) + "  "

End If

End If

Next i

dosfact = s

End Function

La aplicamos a 27720 con k=3, por ejemplo, y resultan 19 divisores:

8  12  18  20  28  30  42  44  45  63  66  70  99  105  110  154  165  231  385 

Ahora usamos la técnica de las combinaciones acotadas que vimos en la entrada anterior, con Cartesius:

xtotal=3

xt=2,3,5,7,11

creciente

contar(2)<4

contar(3)<3

contar(5)<2

contar(7)<2

contar(11)<2

Coincide el número de submulticonjuntos de tres elementos:

Son también 19.

Cálculo directo

Usando la técnica combinatoria de eliminar combinaciones prohibidas resultaría:

Combinaciones con repetición:

COMBINAT(5+3-1;3) = COMBINAT(7;3 = 35

Hay que restarle uno por la combinación prohibida (3,3,3) y para el 5, 7 y 11, cinco cada uno para eliminar aquellos en los que están repetidos: (5,5,2), (5,5,3), …

En total: 35-1-5-5-5=19

Para casos más complicados habría que acudir a técnicas parecidas al Principio de Inclusión y exclusión, sumando y restando posibilidades. Para cálculos mediante fórmulas directas, las incluidas en https://arxiv.org/abs/2009.01233, m-submultisets and m-permutations of multisets elements

Para encontrar el número total de submulticonjuntos sustituiríamos XTOTAL=3 en Cartesius por XRANGO=8, que los abarca todos menos el conjunto vacío. Resultan 95.

Si contamos el conjunto vacío, serían 96, representado en los divisores de 27720 por el número 1.

Si ahora calculamos la función TAU (número de divisores) por su fórmula, usando las multiplicidades, resulta:

TAU(27720)=(1+3)(1+2)(1+1)(1+1)(1+1)=4*3*2*2*2=96

El paralelismo entre subconjuntos y divisores queda comprobado. Es interesante.

Submulticonjuntos (1)

Un multiconjunto (multiset en inglés) es un conjunto en el que se permite la repetición de algunos o todos sus elementos un número determinado de veces, llamado multiplicidad del elemento. Al conjunto de elementos tomados sin repetición se le llama conjunto subyacente,

Un ejemplo claro son los conjuntos de tiradas en Combinatoria, las extracciones de bolas con repetición o el conjunto de los factores primos de un número. En todos ellos se permite que algunos elementos estén repetidos, Otro ejemplo típico es el las letras de una palabra. Por ejemplo, las letras de la palabra ZARAGOZA. Aquí se permite que la Z se repita dos veces y la A tres. Su conjunto subyacente es ZARGO.

Formalmente, un multiconjunto es un conjunto de elementos que son pares del tipo (elemento, multiplicidad). Por ejemplo, las letras de ZARAGOZA forman el multiconjunto

{(A,3),(Z,2),(R,1),(G,1),(O,1)}

Un submulticonjunto de un multiconjunto es otro multiconjunto cuyos elementos pertenecen al multiconjunto inicial con multiplicidades no mayores que las del mismo.

Así, GOZAR es submulticonjunto de ZARAGOZA, pero no lo es ARROZ, porque la R tiene una multiplicidad mayor.

Combinaciones con repetición

En todas las cuestiones que siguen, la base son las combinaciones con repetición. Podremos usar la fórmula para m objetos tomados de n en n, fórmula elemental y conocida:

Tomemos como ejemplo el conjunto {2,3,4,5} Si deseamos construir todas las combinaciones con repetición de 3 en 3, según la fórmula, deberemos obtener en total, usando el lenguaje de las hojas de cálculo:

COMBINAT(4+3-1,3) = COMBINAT(6,3)=6*5*4/6=5*4=20

En efecto, con nuestra herramienta Cartesius se puede comprobar.

(https://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius)

Basta exigir estas tres condiciones:

xtotal=3

xt=2,3,4,5

creciente

Se pide crear tres columnas con contenido 2,3,4,5 y solo se exige que los arreglos sean crecientes, para que resulten combinaciones y no variaciones. El resultado es el esperado, 20 combinaciones con repetición.

 

Combinaciones con repetición acotadas

Si en lugar del conjunto {2,3,4,5} eligiéramos el multiconjunto {2,3,3,4,4,5} deberíamos tener en cuenta que sus subconjuntos no pueden presentar más frecuencias que las determinadas, un 2, dos 3, dos 4 y un 5.

En Cartesius tendríamos que acotar las frecuencias, para que resultaran subconjuntos. Podría ser así:

 

xtotal=3

xt=2,3,4,5

creciente

contar(2)<2

contar(3)<3

contar(4)<3

contar(5)<2

 

Se restringen las frecuencias, con lo que resultan submulticonjuntos:

El resultado sería:

Las combinaciones se han reducido a 10.

¿Cómo llegar a ese número sin usar Cartesius?

En nuestro caso, al número 20 habría que restarle las combinaciones en las que el 3 se repite más de dos veces, y también aquellas en las que ocurre lo mismo con el cuatro. Después eliminaríamos aquellas en las que el 2 o el 5 se repitieran más de una vez

Sería:

Combinaciones totales: CR(4,3)=COMBINAT(6,3)=20

Combinaciones no válidas con el 2: Hay que desechar aquellas combinaciones en las que el 2 se repita dos o tres veces, es decir, fijamos el 2 dos veces, y nos quedan combinaciones de cuatro elementos tomados de uno en, es decir:

CR(4,1)=COMBINAT(4,1)=4. Igual ocurre con el 5

Combinaciones no válidas para el 3: Siguiendo el mismo razonamiento, fijamos el 3 tres veces y queda CR(4,0)=1, e igual para el 4

Nos quedaría prohibir que dos elementos sobrepasaran la multiplicidad, pero eso no ocurre y hemos terminado:

Número de submulticonjuntos: 20-4-4-1-1=10

Así que la idea es, para eliminar combinaciones, fijar cada elemento en su multiplicidad y uno más, y desarrollar lo que queda:

CR(4,3)-CR(4,1)-CR(4,1)-CR(4,0)-CR(4,0)

Se comprende que con más elementos el cálculo se complica, pero este sería el camino correcto.