Cantidad de soluciones de la ecuación diofantina de Frobenius

Question

La ecuación diofantina de Frobenius es cualquier ecuación de la forma:

$$\sum_{i=1}^k a_i x_i = n$$ donde el $a_i$ y también $k$ y $n$ .

Busco un algoritmo para calcular el número de soluciones en enteros no negativos de dicha ecuación. Dado como entrada un array de los $a_i$ y $n$ Necesito que el algoritmo me proporcione la CANTIDAD de soluciones de la ecuación, independientemente de cuáles sean. He buscado por todo internet (literalmente), incluyendo este sitio y https://stackoverflow.com/ . He encontrado muchos artículos al respecto y preguntas similares, y todos los que he leído, pero no he encontrado particularmente lo que estoy buscando. El artículo más "útil" que he encontrado es : http://sertoz.bilkent.edu.tr/papers/froben.pdf que proporciona una fórmula explícita al final. Sin embargo, con la falta de conocimientos matemáticos y de reconocimiento de las notaciones, debido a que no soy estudiante de matemáticas/combinatoria, no puedo calcular el algoritmo de la fórmula, ni estar seguro de que sea realmente "explícita" y sencilla.

He encontrado un libro con el que he llegado hasta aquí (he leído más de 100 páginas), que proporciona fórmulas explícitas para dichas soluciones pero para ecuaciones diofánticas muy sencillas. Si existen o no fórmulas para $k$ (hasta 20) y $n$ (hasta 5000), sé CON SEGURIDAD que estas ecuaciones pueden resolverse algorítmica y eficientemente, ya que conozco a (muy pocas) personas que lo han hecho. También he tratado de crear tal algoritmo eficiente a mí mismo, pero fue en vano.

Así que .. Supongo que eso es todo. Si usted me puede proporcionar algunas ideas / fórmulas / algoritmos (si en Java, entonces aún mejor), entonces yo sería.. Indescriptiblemente feliz y agradecido por esto.

Muchas gracias de antemano, Matan.

Answer 1

Si el $a$ son enteros positivos, hay una solución directa a tu pregunta que implica funciones generadoras. El número de soluciones de tu ecuación es $[x^n]\prod_i(1-x^{a_i})^{-1}$ . Sin embargo, como dices que no eres "estudiante de combinatoria", probablemente tendrás que aprender sobre funciones generadoras para que esta respuesta tenga algún sentido. Hay muchos libros buenos sobre el tema. Mi favorito es este .