How to split numbers into a sorted array with a set number of elements in the array?

Question

so let's say there is an array x of integers with k elements (e.g., int x[k]), where each entry in the array has a distinct integer value between 1 and n, inclusive, and the array is sorted in increasing order. So, 1 ≤ x[i] ≤ n, for all i = 0, 1, 2, . . ., k − 1, and the array is sorted, and therefore x[0] < x[1] < . . . < x[k-1]. In this case, how many such sorted arrays are possible?

EDIT: Straight out of the bat i thought: n! but then I realized there could be cases where numbers aren't incremental by 1 (0, 2, 3, 5). How do I account for these cases also?

Answer 1

Once the numbers in the array have been chosen, there is only one possible array, because there is only one way to sort them. So the number of arrays is just the number of $k$-element subsets of $\{1,2,\dots,n\}$, that is, $\binom nk$.

Answer 2

Since the entries are in increasing order, the array can be viewed as a cumulative sum of the entries of another array (which I'll refer to as the base array).

For example, consider the array $[3, 4, 6, 9]$ $(k = 4, n = 10)$. This is the cumulative sum of the elements of the array $[3, 1, 2, 3]$ $(3 = 3, 4 = 3 + 1, 6 = 3 + 1 + 2, 9 = 3 + 1 + 2 + 3)$.

Every base array with integer entries has a unique cumulative sum, and therefore, it is sufficient to consider integer arrays with no restriction on the order of the elements.

The original question mentions that every element must be between $1$ and $n$, which is equivalent to the condition that the last element of the array must be between $1$ and $n$ (since the elements are in increasing order). This last element is the sum of the elements of the base array; for a fixed value of this total sum, there is a well-known approach for finding the possible base arrays (Stars and Bars). By varying the total sum over all possible values, one can obtain the total number of integer arrays in increasing order with the final term less than $n$.