I need to find the number of total possible different solution to an equation with more than one variable.
For example:
$$ 1x + 2y + 8z = 13 $$
What is the total number of different combinations for the values of $x$, $y$ and $z$? I can't think of an algorithm to solve this. I don't need the answers printed, just the total number of different combinations! The coeficients will always be positive, so are the variables and the final number too.
$x, y ,z$, and possibly more are always positive integers (or $0$)!
Guys, the question above is not what I really wanted to ask, you can find it better formulated bellow. I tried to solve it with this code here, and it did not work, it returns 647 instead of the expected 415 for the inputs ({1,2,8}, 13):
public static int getProbability(int[] distances, int n){
if(n==distances[0])
return 1;
else if(n<distances[0])
return 0;
else {
int returnInt = 0;
for (int i=0 ;i<distances.length; i++){
returnInt += getProbability(distances, n-distances[i]);
}
if (Arrays.binarySearch(distances, n) != -1) {
returnInt = returnInt+1;
}
return returnInt;
}
}
As mentioned in the comments above, the number of solutions to $x+2y+8z=13$ is ten. From the comments, we learn that the real question being asked is the following:
In how many ways can we tile a $13\times 1$ grid with monominos ($1\times 1$ tiles) dominos ($2\times 1$ tiles) and octominos ($8\times 1$ tiles)?
(I.e. how many ways can we partition the number $13$ into parts of size $1,2$ and $8$ respectively where order of parts matters)
We form a recurrence relation: Letting $a_n$ be the number of arrangements for a length $n$ grid, we can break $a_n$ up based on the length of the furthest right tile. If the furthest right tile were a monomino, then there are still $n-1$ spaces to be filled which can be done in $a_{n-1}$ ways. If it were a domino, there are still $n-2$ spaces to be filled which can be done in $a_{n-2}$ ways. If it were an octomino, there are still $n-8$ spaces to be filled which can be done in $a_{n-8}$ ways.
This gives the recurrence relation $a_n = a_{n-1}+a_{n-2}+a_{n-8}$.
We need to find initial conditions to proceed. $a_1=1$ as the only arrangement is a single monomino.
$a_2=2$ as it could be two monominos (1+1) or it could be a single domino (2)
$a_3 = 3$ as it could be three monominos (1+1+1), a monomino then a domino (1+2), or a domino followed by a monomino (2+1)
From earlier example, we know that the sequence begins $a_1=1,a_2=2,a_3=3,a_4=5,a_5=8,a_6=13,a_7=21$ as until we have the opportunity to place the octomino this exactly matches the problem where we have only monominos and dominos which we know to follow the fibonacci sequence.
We then have $a_8=35$ ways to arrange the length eight grid (as there are $34$ ways to do it without any octominos and exactly one way to do it with)
We can then continue the sequence via brute force by hand, by computer, by linear algebra (but factoring the degree eight polynomial to get a closed form solution will be trouble) etc...
$\begin{array}{|r|l|l|}\hline a_0&1\\ a_1&1&1+0+0\\ a_2&2&1+1+0\\ a_3&3&2+1+0\\ a_4&5&3+2+0\\ a_5&8&5+3+0\\ a_6&13&8+5+0\\ a_7&21&13+8+0\\ a_8&35&21+13+1\\ a_9&57&35+21+1\\ a_{10}&94&57+35+2\\ a_{11}&154&94+57+3\\ a_{12}&253&154+94+5\\ a_{13}&415&253+154+8\\ \hline\end{array}$
Alternatively, we could break apart based on if there is an octomino or not, and where it is. Given that the solution to the length $n$ problem with only monominos and dominos is $F(n+1)$ where $F(n)$ represents the $n$'th fibonacci number, we get:
$a_{13} = F(14)+F(1)F(6)+F(2)F(5)+F(3)F(4)+F(4)F(3)+F(5)F(2)+F(6)F(1) = 415$