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?

  • 2
    $\begingroup$ Sort the representation of the subset... Then it forms a $k$-sequence, right? $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.