Question on ascending $k$-tuples of naturals whose sum is less or equal than $S$

Question

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.

Answer 1

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