<ol>
<li><p>Let's add one more number $x_{k+1} = S - \sum_i{x_i}$ and assume none of the $x_i$ is zero. Now $(x_1, \ldots, x_{k+1}$) is what is called an $k+1$-part <a href="http://en.wikipedia.org/wiki/Partition_%28number_theory%29" rel="nofollow">integer partition</a> of $S$. So your tuples are integer partitions of the numbers $0, \ldots, S$ into at most $k$ parts (at most because some $x_i$ could be 0).</p></li>
<li><p>Counting partitions is a big topic but a recurrence is not very hard to formulate. Let $q(n,k)$ be the number of partitions of $n$ into at most $k$ parts. The number of your tuples is then $1 + \sum_{n = 1}^{S}{q(n, k)}$. For the recurrence you have two cases:</p></li>
</ol>

<p>a) There are $k$ nonzero $x_i$. Then if you subtract one from each $x_i$ you get a partition of $n-k$ with at most $k$ parts. So there is a bijection between partitions of $n$ with exactly $k$ parts and partitions of $n-k$ with at most $k$ parts.</p>

<p>b) There are less than $k$ nonzero $x_i$. The number of such tuples is $q(n, k-1)$. </p>

<p>The recurrence you get is $q(n, k) = q(n-k, k) + q(n, k-1)$. The initial conditions are $q(0, k) = 1$ and $q(n, 0) = 0$ for $n&gt;0$.</p>

<p>As to 3., I think $q(n, k)$ is at least on the order of $n^k$ which would imply that there aren't very succinct representations.</p>

CC BY-SA 3.0
2011-10-20T16:56:04.477Z
2011-10-20T17:36:13.740Z
2011-10-20T17:36:13.740Z
Sasho Nikolov
<p>Let $k$ and $S$ be fixed non-negative integers. Let us regard the following set of tuples</p>

<p>$\{ (x_1,\dots,x_k)| x_i \leq x_{i+1}, \sum_j x_j \leq S \}$</p>

<p>I have got some questions on this set.</p>

<ol>
<li>Is there are name for this set? It is similiar to an arbitrary partition of an integer.</li>
<li>Is there a nice formula that provides the number of elements in this set? It may be recursive.</li>
<li>Is there an easy to compute index for each of the elements, such that in turn any element can be computed from the index (easily)?</li>
</ol>

<p>Of course, there are brute force algorithms for the last two questions. I am looking for something neater.</p>

<co.combinatorics><nt.number-theory>
Question on ascending $k$-tuples of naturals whose sum is less or equal than $S$
shuhalo
# Question on ascending $k$-tuples of naturals whose sum is less or equal than $S$

(Asked by: username_0 on 2011-10-20)

Let $k$ and $S$ be fixed non-negative integers. Let us regard the following set of tuples

$\{ (x\_1,\dots,x\_k)| x\_i \leq x\_{i+1}, \sum\_j x\_j \leq S \}$

I have got some questions on this set.

1. Is there are name for this set? It is similiar to an arbitrary partition of an integer.
2. Is there a nice formula that provides the number of elements in this set? It may be recursive.
3. Is there an easy to compute index for each of the elements, such that in turn any element can be computed from the index (easily)?

Of course, there are brute force algorithms for the last two questions. I am looking for something neater.

**Tags:** co.combinatorics, nt.number-theory


---

## 1 answers

### Answer by username_1 on 2011-10-20. Score: 4 | Accepted answer

1. Let's add one more number $x\_{k+1} = S - \sum\_i{x\_i}$ and assume none of the $x\_i$ is zero. Now $(x\_1, \ldots, x\_{k+1}$) is what is called an $k+1$-part [integer partition](http://en.wikipedia.org/wiki/Partition_%28number_theory%29) of $S$. So your tuples are integer partitions of the numbers $0, \ldots, S$ into at most $k$ parts (at most because some $x\_i$ could be 0).
2. Counting partitions is a big topic but a recurrence is not very hard to formulate. Let $q(n,k)$ be the number of partitions of $n$ into at most $k$ parts. The number of your tuples is then $1 + \sum\_{n = 1}^{S}{q(n, k)}$. For the recurrence you have two cases:

a) There are $k$ nonzero $x\_i$. Then if you subtract one from each $x\_i$ you get a partition of $n-k$ with at most $k$ parts. So there is a bijection between partitions of $n$ with exactly $k$ parts and partitions of $n-k$ with at most $k$ parts.

b) There are less than $k$ nonzero $x\_i$. The number of such tuples is $q(n, k-1)$.

The recurrence you get is $q(n, k) = q(n-k, k) + q(n, k-1)$. The initial conditions are $q(0, k) = 1$ and $q(n, 0) = 0$ for $n>0$.

As to 3., I think $q(n, k)$ is at least on the order of $n^k$ which would imply that there aren't very succinct representations.


---

