# Find $k$-tuples satisfies $j=n_2+2n_3+\cdots+(k-1)n_k$ if $n_1+\cdots+n_k=n$.

Let $n_i \in N$, $i=1,\ldots,k$ and such that $n_1+\cdots+n_k=n$. Fix $j \in N$.

I would like to find all $k$-tuples (or algorithm how to find $k$-tuples) satisfies $$j=n_2+2n_3+\cdots+(k-1)n_k$$

Any help would be very appreciated.

Thank you.

• Interesting. What did you try? Apr 22 '12 at 16:00
• I am not really familiar with number theory... Its hard for me even to start. So far I've just tried different particular cases... Apr 22 '12 at 16:34

Presumably $n$, $j$ and $k$ are given.
Let's call $A_{(n,j,k)}$ this set of $k$-tuples and let's write $a_k = (a_{k-1},m)$ to mean a $k-1$-tuple with the number $m$ appended to make a $k$-tuple.
In practice $n$ is an upper limit on $n_2+\cdots+n_k$ since $n_1$ can be altered to make up the difference. Clearly $n_k \le n$ and $n_k(k-1) \le j$.
Then recursively $$A_{(n,j,k)} = \bigcup_{n_k=0}^{\min(n,\lfloor j/(k-1) \rfloor)} \left\{ (a_{k-1} \in A_{(n-n_k,j-n_k(k-1),k-1)} , n_k) \right\}$$ where $A_{(n,j,k)} = \emptyset$ when $n \lt 0$ or $j \lt 0$ or $j \gt n(k-1)$, and where $A_{(n,0,1)} = \{(n)\}$ when $n \ge 0$.
You can use this to generate the $k$-tuples. At the end you can save some effort by noting that $A_{(n,j,2)} = \{(n-j,j)\}$ when $0 \le j \le n$, and that $A_{(n,j,k)} = \{(n,0,\ldots,0)\}$ when $n \ge 0$ and $j=0$.