# Sets, Sequences, and counting

Let $A$ denote all $k$-subets of $\{1,\dots,n\}$ where $0 < k \le n$ and let $B$ denote all increasing $k$ sequences on $\{1,\dots,n\}$. Show that the number of $k$-subsets in $A$ equals the number of $k$-sequences in $B$.

How do I do that?

• Sort the representation of the subset... Then it forms a $k$-sequence, right? – String Oct 9 '13 at 8:50

Denote $\{1,2,3,\ldots,n\}$ as $[n]$. The number of subsets of $[n]$ of length $k$ we can easily represent as ${n \choose k}$, as to create a subset of size $k$ from $n$ is to just choose $k$ elements from $n$. So $|A| = {n \choose k}$.
Now we want to choose $k$ elements from $[n]$ such that the $k$ elements form an increasing sequence. We note that the set $B$ will be a subset of $A$, because $A$, containing all possible subsets of size $k$ from $[n]$, must also contain all possible sequences of size $k$ from $[n]$, because a sequence is just an ordered subset. In other words, $B \subseteq A$.
So to construct $B$, we will throw out the elements of $A$ from which we can't construct an increasing sequence. Noting that $[n]$ is a set of unique elements, it must be that there is no element of $A$ that contains repeated elements. (This might get confusing: remember that elements of $A$ are subsets of $[n]$. Elements of elements of $A$ are elements of $[n]$. Take the set $\{1,2,3\}$ and draw it out all out, if necessary.) So for all elements $a$ of $A$, by trichotomy it must be that any element of $a$ is either larger or smaller than some other element in $a$. In other words, the elements of every $a \in A$ can be ordered, and so every $a \in A$ represents an increasing sequence. So $\forall a\in A, a \in B$. so $A \subseteq B$. We know $B \subseteq A$, so $A=B$.