How many ways we can choose an increasing and a strictly increasing subsequence of length $k$ from the first $n$ natural numbers? Let $S:=\{1 \dots n\}.$ We want to choose
i) increasing subsequences of $S$ length $k \le n.$ and
ii) strictly increasing subsequences of $S$ length $k \le n.$
How many ways can we choose them in i) and ii)? I'm a bit confused where even to start, but detailed answers will be appreciated!
 A: 
How many increasing subsequences of length $k \leq n$ can be formed using the elements of $S := \{1, 2, 3, \ldots, n\}$?

A particular subsequence is determined by how many times each element in $S$ appears.  For instance, if $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ and $k = 6$, then if $3$ appears once, $6$ appears twice, and $9$ appears three times, the resulting subsequence must be $(3, 6, 6, 9, 9, 9)$ since the elements of the subsequence must appear in increasing order.
Hence, if we let $x_i$ represent the number of times the number $i$ appears in the subsequence, the number of ways a subsequence of length $k \leq n$ can be formed from $S$ is the number of solutions of the equation
$$x_1 + x_2 + x_3 + \cdots + x_n = k$$
in the nonnegative integers.

How many strictly increasing subsequences of length $k \leq n$ can be formed using the elements of $S = \{1, 2, 3, \ldots, n\}$?

A particular subsequence is determined by which $k$ elements appear in the subsequence since they must appear in strictly increasing order. For instance, if $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ and $k = 6$, then if we select the numbers $2, 3, 4, 5, 7, 8$, the resulting subsequence must be $(2, 3, 4, 5, 7, 8)$.  Hence, the number of strictly increasing subsequences of length $k$ is the number of ways we can select $k$ elements from a set with $n$ elements.
A: For the first question, consider the $k+1$ gaps in the sequence $1,x_1,x_2,\ldots,x_k,n$... all are $\ge 0$ and they must sum to $n-1$.  For the second, consider the $k+1$ gaps in $0,x_1,x_2,\ldots,x_k,n+1$... all are $\ge 1$ and they must sum to $n+1$.  Can you take it from there?
A: For the first part, any choices made using Theorem 1 of stars and bars can always be arranged in ascending order, thus  $\binom{n-1}{k-1}$
For the second part, any distinct choices of $k$ can always be arranged in strictly ascending order, thus $\binom{n}{k}$
