Cfrgtkky

How many nonnegative integer solutions are there to: $x_1 + 2x_2 + x_3 = 10$? I am able to do this when it is simply $x_1 + x_2 + x_3 = 10$ but by multiplying $x_2$ by 2 has confused me.

Like mentioned in the comments, this sort of problems must be solved pretty much case by case, but let's try to solve at least a little bit more general problem than the particular one asked, namely how many non-negative integer solutions does the equation

$$x_1 + tx_2 + x_3 = n$$

have, where $t, ninmathbb{N}$.

This can be done by letting $x_1$ run through $1, 2, dots, n$ and checking how many values the variable $x_2$ can take, so that $x_1+tx_2 leq n$. The third variable $x_3$ will then always be forced and the solution will work (this happens because the coefficient of $x_3$ is $1$, otherwise $n-x_1-tx_2$ would need to be a multiple of the coefficient of $x_3$ to get an integer solution).

Ok, so if $x_1 = j$, for $n-j-tx_2$ to remain nonnegative, we must have

$$x_2 leq frac{n-j}{t}$$

and $x_2$ can take the values $0, 1, dots, lfloor frac{n-j}{t} rfloor$. Therefore the number of solutions is

$$sum_{j=0}^n left( 1 + leftlfloor frac{n-j}{t} rightrfloor right)
= sum_{j=0}^n left( 1 + leftlfloor frac{j}{t} rightrfloor right)
$$
$$
=n+1 + sum_{j=0}^n leftlfloor frac{j}{t} rightrfloor
$$

(Above we just flipped the sum, i.e change of index $jto n-j$ for a nicer looking formula).

For the particular case $t=2$, we can simplify this by considering cases $n$ even and $n$ odd, splitting the sum to even and odd parts and using the fact that $sum_{k=0}^r k= frac{r(r+1)}{2}$ to

$$n+1 + left lfloor frac{n^2}{4} right rfloor$$

and for $n=10$ we get $36$ solutions.

$x_2$ may be $0...5$. $x_1$ may be $0.. ,10-2x_2$ and $x_3$ is fixed at $10-2x_2 - x_1$

So there are

$sumlimits_{x_2=0}^5 sumlimits_{x_1=0}^{10-2x_2} 1$

Which may be reindexed as

$sumlimits_{x_2=0}^5 sumlimits_{x_1=10; -1}^{2x_2} 1=$

$sumlimits_{x_2=0}^5 sumlimits_{x_1=0}^{2x_2} 1=$

$sumlimits_{x_2=0}^5 (2x+1) = $

$6^2 = 36$

Perhaps the hope for any general methods was too hastily discarded. We can use generating functions.

If $a_n$ denotes the number of solutions to

$$c_1x_1 + c_2x_2+dots + c_kx_k = n$$
$$x_j geq 0$$

Then the generating function $A(z) = sum_{n=0}^{infty} a_nz^n$ is given by

$$A(z) = frac{1}{(1-z^{c_1})(1-z^{c_2})dots(1-z^{c_k})}$$

This comes from the fact that compositions of $n$ into $k$ parts corresponds to a integer-sequence of length $k$. Now, you can use a size-function $xmapsto c_jx$ for each class of integers $cal{I}_j$ in the product $cal{I}_1 times cal{I}_2 dots times cal{I}_k$, so you have the correct equation. The generating function of the class $cal{I}_j$ is $frac{1}{1-z^{c_j}}$ because ${cal{I}}_j = text{SEQ}({ Z })$ and the element $Z$ has size $c_j$.

I don't know if this actually helps, maybe you can do partial fraction expansion of $A(z)$.

By the way, notice how in the case when all $c_j=1$ this amounts to the usual compositions:

$$A(z) = left( frac{1}{1-z} right)^k = (1-z)^{-k} = sum_{j=0}^infty {{-k}choose{j}} (-z)^{j}$$

so $a_j = {{-k}choose{j}} (-1)^{j} = {{k+j-1}choose{k-1}}$.