Intereting Posts

Is $\infty / \infty = 1$?
Show that affine varieties are quasi-compact.
How to find $n$'th term of the sequence $3, 7, 12, 18, 25, \ldots$?
How to evaluate these integrals by hand
Real Analysis: Continuity of a Composition Function
Tower property of conditional expectation
How can $\lim_{n\to \infty} (3^n + 4^n)^{1/n} = 4$?
Confused about complex numbers
Why can't ODE's be solved only using algebra?
Formal proof for detection of intersections for constrained segments
prove this :$\sum_1^{100} A_i = \sum_0^{99} C_i $
Finding coefficient of generating function
Proving that $\lim_{n\rightarrow \infty} \frac{n^k}{2^n}=0$
Closed space curves of constant curvature
Does there exist a non-constant entire function $f$ such that $|f(z^3)| \leq 1 + |z|$ for all $z$?

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)$.

- Number of ways to choose 6 objects when they are of 11 different kinds
- Trouble understanding equivalence relations and equivalence classes…anyone care to explain?
- Prove the following equality: $\sum_{k=0}^n\binom {n-k }{k} = F_n$
- Proving that $n \choose k$ is an integer
- Are there any Combinatoric proofs of Bertrand's postulate?
- Secret santa problem

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)$.

- Number of bit strings with 3 consecutive zeros or 4 consecutive 1s
- What is the number of distinct 3 letter words out of different number of given letters?
- Can you determine a formula for this problem?
- Handshaking with no crossovers in minimum number of rounds: has this problem been studied?
- A sum of fractional parts.
- MISSISSIPPI combinations with the S's separated
- Proving $\sum\limits_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$
- Is there a geometrical interpretation of this equality $2\cdot 4\cdot 6\cdot\ldots\cdot(2n)=2^nn!$?
- What function satisfies $F'(x) = F(2x)$?
- Coloring 5 Largest Numbers in Each Row and Column Yields at Least 25 Double-Colored Numbers

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.

- Simple summation problem regarding origin of summand:
- Proof of the definition of cardinal exponentiation
- Can the general septic be solved by infinitely nested radicals?
- Is there a $C^1$ curve dense in the plane?
- Reducing an indicator function summation into a simpler form.
- If $\frac{dy}{dt}dt$ doesn't cancel, then what do you call it?
- How do I understand $e^i$ which is so common?
- Would it be fine to use Serge Lang's two Calculus books as textbooks for freshman as Maths major?
- Spectrum of the $\ell^{1}$ operator $A(x)=(x_{2}+x_{3}+x_{4}+ \dots,x_1,x_2,x_3,\dots)$
- Polynomials irreducible over $\mathbb{Q}$ but reducible over $\mathbb{F}_p$ for every prime $p$
- What is $\int_0^1 \ln (1-x) \ln \left(\ln \left(\frac{1}{x}\right)\right) \, dx$?
- Infinite Integration by Parts
- Expected Value of Maximum of Two Lognormal Random Variables with One Source of Randomness
- How to compare the K-theory and singular cohomology of a classifying space
- Showing that $\int_0^1 \log(\sin \pi x)dx=-\log2$