Random nonegative solution of multivariate linear Diophantine equation

Question

Consider a diophantine equation in n variables:
$a_1x_1+a_2x_2+...+a_nx_n=k$
All $a_i$'s, $x_i$'s and $k$ are restricted to non-negative integers $\mathbb{Z^+}$. (note that because of domain restrictions the number if solutions is guaranteed to be finite)
I need to generate a random solution to this equation and i do not know how to approach it. In other words i need an algorithm which is equally likely to generate any one of the possible solutions.
Any help would be welcome.

Answer 1

Let $f(a_1, a_2, \ldots, a_n, k)$ be the number of solutions. This is the coefficient of $x^k$ in the Maclaurin series $\prod_{j=1}^n (1 - x^{a_i})^{-1}$. The number of solutions with $x_1 = t$ is $f(a_2, \ldots, a_n, k - a_1 t)$ for $t = 0$ to $\lfloor k/a_1 \rfloor$. So choose $x_1$ with the probabilities $P(x_1 = t) = f(a_2,\ldots,a_n, k - a_1 t)/f(a_1,a_2,\ldots,a_n,k)$. Proceed recursively.