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.


3 Answers 3


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,


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


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.


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.


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


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.