# composition of an integer number

Given two positive integers $m$ and $n$. I would like one special non-negative solution to the following system (which is related to a composition of an integer number):
$$\begin{cases} \sum a_i = m \\ \sum (i+1)a_i =n \end{cases}$$

How to describe the solution $(a_0,\dots,a_j)$ with largest index $j$ such that $a_j$ is nonzero?

For instance, if $m=2$ and $n=4$, we have $(1,0,1)$ and $(0,2,0)$ as solutions. So the solution which I want is $(1,0,1)$.

Edit: Another example, for m=3 and n=6 we have $(0,3)$, $(1,1,1)$ and $(2,0,0,1)$, so I take $(2,0,0,1)$.

#### Solutions Collecting From Web of "composition of an integer number"

A necessary condition for a solution is that $m \le n$:

$$m = \sum_{i=0}^j a_i \le \sum_{i=0}^j (i+1)a_i = n$$

If $j$ is the largest index for which $a_j \gt 0$, then either $a_j$ is the only nonzero summand ($m=1$ and $n=j+1$) or else we can remove $j+1$ from $n$ and reduce $m$ by $1$ to obtain the smaller problem for $m’=m-1$ and $n’=n-j-1$.

The smaller problem has a solution only if $m’ \le n’$:

$$m-1 \le n-j-1$$

$$j \le n – m$$

Thus the largest possible nonzero index is $j = n-m$.

To see that such a solution exists, it suffices to verify the cases $m=1$ (when $n=j+1$ and $a_j = 1$) and $m=n$ (when $a_0 = n$).

Remarks: The proof actually shows that maximum index $j=n-m$ is obtained by a summation in only one way. In the case $m=n$ the inequality at top forces $a_0=n$ to be the only feasible summation, with $j=0$. In the case $m=1$ there can be only one summand, and it must be $a_j=1$ with $j=n-1$. All other cases start by setting $a_j=1$ with $j=n-m$, after which the reduced case $m’=m-1$ and $n’=n-j-1$ satisfies the case $m’=n’$. Thus the reduced case has only one feasible summation.

The summations studied here are partitions of $n$ into exactly $m$ parts:

$$\underbrace{1+\ldots+1}_{a_0\text{ times}}+\underbrace{2+\ldots+2}_{a_1\text{ times}}+\ldots+\underbrace{(j+1)+\ldots+(j+1)}_{a_j\text{ times}} = n$$

where $\sum_{i=0}^j a_i = m$ is the collected number of parts (summands).

The original question can thus be recast as, “What is the largest possible part of a partition of $n$ into exactly $m$ parts?” In this context our answer may be expressed as either $m = n$ and the largest part is $1$ or $m \lt n$ and the largest part is $n-m+1$.

However I think the OP has raised a different question in the Comment below, namely what is the:

Largest possible value of $a_{n-m}$

When $m \gt n$, no solutions of any kind are possible (since the $m$ terms would add up to something more than $n$).

In the case $m = n$, there is exactly one solution, where each of the $m$ terms is one (since if any term were more, the total would exceed $m=n$). Stated differently, $n-m = 0$ and $a_{n-m} = a_0 = n$ is the unique solution.

Finally, if $m \lt n$, there may be multiple solutions, but only one where $a_{n-m} \gt 0$.

This is clear if we remove a single term $n-m+1$ from the summation and put $m’ = m-1$ and $n’ = n-(n-m+1) = m-1$.

As just observed the reduced problem has a unique solution where $n’ = m’$ is expressed as $a_0 = m’$ ones. Putting this together with the single term $n-m+1$ we removed, we get:

$$a_{n-m} = 1 \; , \; a_0 = m-1$$

and this is the unique solution where $a_{n-m} \gt 0$.

A more interesing problem arises if we do not require $j=n-m$ to be the index of the leading term. When $m \lt n$, there may solutions whose leading term’s multiplicity $a_j$ is greater than one. Therefore we may ask in these cases how to determine the largest leading term’s multiplicity $a_j$.

For example, if $n=16$ and $m=6$ the possible partitions include:

$$11 + 1 + 1 + 1 + 1 + 1 = 16$$

$$4 + 4 + 2 + 2 + 2 + 2 = 16$$

$$4 + 4 + 4 + 2 + 1 + 1 = 16$$

$$3 + 3 + 3 + 3 + 3 + 1 = 16$$

So how does one find the partition where such $a_j$ is largest? Here we say with Scheherazade that an answer to this more interesting problem must await a new post.