Efficient numerical evaluation of weak restricted compositions

• González-Santander, Juan Luis ^[1]
  1. [1] Universidad de Oviedo

     Universidad de Oviedo

     Oviedo, España

     
• Localización: Nereis: revista iberoamericana interdisciplinar de métodos, modelización y simulación, ISSN 1888-8550, Nº. 14, 2022, págs. 175-182
• Idioma: inglés
• DOI: 10.46583/nereis_2022.1.1018
• Títulos paralelos:
  • Evaluación numérica eficiente de las composiciones restringidas débiles
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    Proponemos un algoritmo para calcular el número de composiciones débiles, en el que cada parte está restringida a un rango diferente de números enteros. Este algoritmo realiza diferentes órdenes de aproximación hasta la solución exacta utilizando el Principio de Inclusión-Exclusión. La gran ventaja que tiene con respecto a la técnica clásica de la función generadora es que el cálculo es exponencialmente más rápido a medida que aumenta el tamaño de los números involucrados.

  • English

    We propose an algorithm to calculate the number of weak compositions, wherein each part is restricted to a different range of integers. This algorithm performs different orders of approximation up to the exact solution by using the Inclusion-Exclusion Principle. The great advantage of it with respect to the classical generating function technique is that the calculation is exponentially faster as the size of the numbers involved increases.

• Referencias bibliográficas
  • Brualdi RA. Introductory Combinatorics. Pearson Education India; 1977.
  • Comtet L. Advanced Combinatorics: The art of infinite expansions. Springer Science & Business Media, 2012.
  • De Moivre A. The doctrine of chances: or, A method of calculating the probabilities of events in play, vol. 200. Chelsea Publishing Company...
  • Eger S. Restricted weighted integer compositions and extended binomial coefficients. J Integer Seq 2013;16(13.1.3):1-25.
  • Feller W. An introduction to probability theory and its applications, vol. 2. John Wiley & Sons, 2008.
  • Heubach S, Mansour T. Compositions of n parts in a set. Congressus Numerantium 2004;168:127-140.
  • Heubach S, Mansour T. Combinatorics of compositions and words. CRC Press, 2009.
  • Jakli G, Vitrih V, Žagar E. Closed form formula for the number of restricted compositions. Bulletin of the Australian Mathematical Society...