Question on ascending $k$-tuples of naturals whose sum is less or equal than $S$
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).
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&gt;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.