1
$\begingroup$

Let $i,j,k$ be nonnegative integers and $l$ be a positive integer.

How many solutions does the equation $2i+j+3k=l$ have?

For low enough $l$, I can easily find the number of solutions, but is there a general formula which gives, for arbitrary $l$, the number of solutions? Maybe in some combinatorial way?

$\endgroup$
2
$\begingroup$

It appears there is a recurrence relation describing this problem. See this link for details.

Correction:

Following the description in the link you are asking for what they denote by $p_1(l)+p_2(l)+p_3(l)$, namely the total number of partitions of $l$ you can make with each term at most equal to $3$. Given $(i,j,k)$ in your equation above we have a partition of $2i+j+3k=l$ given as $$ \overbrace{1+1+...+1}^{j\text{ times}}+\overbrace{2+2+...+2}^{i\text{ times}}+\overbrace{3+3+...+3}^{k\text{ times}}=l $$ and we have to add $p_1+p_2+p_3$ since these count the partitions in which the largest part equals $1, 2$ and $3$ respectively, so in effect $p_1$ counts solutions to your equation with $i=k=0$, $p_2$ counts solutions with $i\neq 0$ but $k=0$, and finally $p_3$ counts solutions with $k\neq 0$. So together they give all solutions.

This can be computed recursively for different values of $l$ by applying the recurrence $p_k(n)=p_k(n-k)+p_{k-1}(n-1)$ which leads to the following table: $$ \begin{array}{|c:c:c:c:c|c|} \hline l&p_0(l)&p_1(l)&p_2(l)&p_3(l)&p_1+p_2+p_3\\ \hline 0&1&0&0&0&0\\ \hdashline 1&0&1&0&0&1\\ \hdashline 2&0&1&1&0&2\\ \hdashline 3&0&1&1&1&3\\ \hdashline 4&0&1&2&1&4\\ \hdashline 5&0&1&2&2&5\\ \hdashline 6&0&1&3&3&7\\ \hdashline 7&0&1&3&4&8\\ \hdashline 8&0&1&4&5&10\\ \hdashline 9&0&1&4&7&12\\ \hdashline 10&0&1&5&8&14\\ \hdashline 11&0&1&5&10&16\\ \hdashline 12&0&1&6&12&19\\ \hdashline 13&0&1&6&14&21\\ \hdashline 14&0&1&7&16&24\\ \hdashline 15&0&1&7&19&27\\ \hdashline 16&0&1&8&21&30\\ \hdashline 17&0&1&8&24&33\\ \hdashline 18&0&1&9&27&37\\ \hdashline 19&0&1&9&30&40\\ \hdashline 20&0&1&10&33&44\\ \hdashline 21&0&1&10&37&48\\ \hdashline 22&0&1&11&40&52\\ \hdashline 23&0&1&11&44&56\\ \hdashline 24&0&1&12&48&61\\ \hdashline 25&0&1&12&52&65\\ \hdashline 26&0&1&13&56&70\\ \hdashline 27&0&1&13&61&75\\ \hdashline 28&0&1&14&65&80\\ \hdashline 29&0&1&14&70&85\\ \hdashline 30&0&1&15&75&91\\ \hline \end{array} $$ So the figures you are asking for is the list starting as follows: 0, 1, 2, 3, 4, 5, 7, 8, 10, 12, 14, 16, 19, 21, 24, 27, 30, 33, 37, 40, 44, 48, 52, 56, 61, 65, 70, 75, 80, 85, 91, 96, 102, 108, 114, 120, 127, 133, 140, 147, 154, 161, 169, ... Searching for this in OEIS.org reveals that this is a known sequence. It also says something there regarding formulas for those figures, but I have not read that more closely.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry - something is not right about my table yet - I will try to fix it and edit ... $\endgroup$ – String Sep 21 '14 at 18:17
  • $\begingroup$ Now it should be OK! $\endgroup$ – String Sep 21 '14 at 18:53
  • $\begingroup$ thanks a lot for this nice answer! $\endgroup$ – PepeToro Sep 24 '14 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.