# Given a positive number n, how many tuples $(a_1,…,a_k)$ are there such that $a_1+..+a_k=n$ with two extra constraints

The problem was: Given a positive integer $n$, how many tuples $(a_1,...,a_k)$ of positive integers are there such that $a_1+a_2+...+a_k=n$. And $0< a_1 \le a_2 \le a_3 \le...\le a_k$. Also, $a_k-a_1$ is either $0$ or $1$.

Here is what I did:

For $n=1$, there is one way $1=1$.

For $n=2$, there are $2$ ways, $2=1+1,2=2$

For $n=3$, there are $3$ ways, $3=1+1+1,3=1+2,3=3$

For $n=4$, there are $4$ ways, $4=1+1+1+1,4=1+1+2,4=2+2,4=4$

So it seems that there are $n$ tuples that satisfies the three conditions for each $n$. But I'm not sure how to prove it.

Every solution is a tuple in order of increasing integers. Also, $a_k=a_1$ or $a_k=a_1+1$. Therefore, we have all of the $a_1$s at the beginning and $a_1+1$s at the end. We can say there are $l$ instances of $a_1$ and thus $k-l$ instances of $a_1+1$. Since the sum of the tuples is $n$, we find: $$l*a_1+(k-l)*(a_1+1)=n$$ Simplify the left side: $$a_1k+k-l=n$$ Now, $l$ is the number of instances of $a_1$ in the sequence. Thus, $l$ is at least $1$ and at most $k$. Therefore, $k-l$ is at least $0$ and at most $k-1$, so $k-l$ is basically the remainder of $n$ when divided by $k$ and $a_1$ is the quotient. Thus, by the Division Theorem, we know there are unique integer solutions of $a_1$ and $l$ for this equation for any $k$ and $n$.

However, the problem says that $a_1 > 0$, so we need to exclude the solutions where $a_1=0$. When $a_1=0$, we get: $$0k+k-l=n \implies k-l=n$$ Since $k-l$ is at most $k-1$, this means $n$ is at most $k-1$ and thus $n < k$. Therefore, exclude all solutions where $k > n$.

Also, obviously, $k \geq 1$. This leaves us with the solutions $k \geq 1$ and $k \leq n$, so there are $n$ solutions.

The answer is $n$.

Given $n$, you need to proof that for each $k$, where$k\leq n$, there exists exactly one tuple.

First, you can proof that for each $k$, there exists at least one tuple.

$n=kt+r$

where $r<k$.

Make the tuple $(a_1,...,a_k)=(t,...,t)$. Then add to the last $r$ components $1$ unit to get a valid tuple.

Secondly, you need to prove that the constructed tuple is unique, for each $k$ and $n$. If there is another tuple, such that its elements add to $n$, then you can get it from the first constructed tuple, by moving units between components. But, if you move a single unit, then you destroy the increasing order of components.

Finally, you just need to know how many possible $k$ you can have for a number $n$, which is $n$.

This can also be done with a simple generating function. Call the desired quantity $T_n.$ We first choose the value $a_1$ and then the gaps between successive values among the $a_q$ which are either zero or one. We will have $1\le k\le n$ but for $k=1$ there is just one possibility so we may assume $2\le k\le n.$ We get for $a_1,$ which is positive,

$$\frac{z}{1-z}$$

but it contributes to all $k$ terms so we have in fact

$$\frac{z^k}{1-z^k}.$$

We combine this with $k-1$ gaps of either zero or one. The first gap contributes to $k-1$ terms, the next one to $k-2$ and so on. Using the variable $u$ to mark gaps we thus obtain

$$\bbox[5px,border:2px solid #00A000]{ 1 + \sum_{k=2}^n \frac{z^k}{1-z^k} \prod_{q=1}^{k-1} \left(1+uz^{k-q}\right).}$$

Now from the constraint that $a_k-a_1$ be either zero or one it follows we need the coefficient on $[u^0]$ and $[u^1].$ We set $u=0$ for the first one and get

$$\sum_{k=2}^n \frac{z^k}{1-z^k}.$$

We differentiate and set $u=0$ for the second one and obtain

$$\left.\sum_{k=2}^n \frac{z^k}{1-z^k} \prod_{q=1}^{k-1} \left(1+uz^{k-q}\right) \sum_{q=1}^{k-1} \frac{z^{k-q}}{1+uz^{k-q}}\right|_{u=0} \\ = \sum_{k=2}^n \frac{z^k}{1-z^k}\sum_{q=1}^{k-1} z^{k-q}.$$

It follows that the desired result is given by

$$\bbox[5px,border:2px solid #00A000]{ 1 + [z^n] \sum_{k=2}^n \frac{z^k}{1-z^k}\sum_{q=1}^{k} z^{k-q}.}$$

Evaluating this we initially obtain

$$1 + [z^n] \sum_{k=2}^n \frac{z^{2k}}{1-z^k}\sum_{q=1}^{k} z^{-q} = 1 + [z^n] \sum_{k=2}^n \frac{z^{2k}}{1-z^k} \frac{1}{z} \sum_{q=0}^{k-1} z^{-q} \\ = 1 + [z^n] \sum_{k=2}^n \frac{z^{2k}}{1-z^k} \frac{1}{z} \frac{1-1/z^k}{1-1/z} = 1 + [z^n] \sum_{k=2}^n \frac{z^{2k}}{1-z^k} \frac{1-1/z^k}{z-1} \\ = 1 + [z^n] \sum_{k=2}^n \frac{z^k}{1-z^k} \frac{z^k-1}{z-1} = 1 - [z^n] \sum_{k=2}^n \frac{z^k}{z-1}.$$

Now we may extend $k$ to infinity because the terms for $k\gt n$ do not contribute to the coefficient on $[z^n],$ getting

$$1 + [z^n] \frac{1}{1-z} \sum_{k\ge 2} z^k = 1 + [z^n] \frac{z^2}{(1-z)^2} \\ = 1 + [z^{n-2}] \frac{1}{(1-z)^2} = 1 + {n-2+1\choose 1}.$$

This yields the end result

$$\bbox[5px,border:2px solid #00A000]{T_n = n.}$$

I do think this computation is interesting and perhaps different from what one might have expected.