# Proof about combinations but with a combinatorial argument

Let $\Omega_n={1,2,....,n}$ and for $0 \leq k \leq n$ let $\Omega^{\{k\}}$ be the collection of k element subsets of $\Omega_n$

Define the number $S^{n}_{k}$ as cardinality of $\Omega^{\{k\}}_n$

Prove that $S^{n}_{k}={n \choose k}$ by the method of counting in two different wats. Let X= $\Omega^{\{k\}}_n$ and $Y=\{(n_1, n_2, . . . , n_k)|n_i \in \Omega_{n} \text{ and are distinct}\}$. Use the relation R which is the set of all pairs $(A,(n_1, . . . , n_k))$ such that $\{n_1, n_2, . . . , n_k\} = A$.

Approach: I know that I have to use a combinatorial argument, but I just can't understand the wording of this problem. I am completely blocked from this part: Let X=$\Omega^{\{k\}}_n$ and $Y=\{(n_1, n_2, . . . , n_k)|n_i \in \Omega_{n} \text{ and are distinct}\}$. Use the relation R which is the set of all pairs $(A,(n_1, . . . , n_k))$ such that $\{n_1, n_2, . . . , n_k\} = A$.

what is X, what is Y what is R how do they relate to the problem?

• Please don't deliberately duplicate questions; this is an abuse of the site. Jun 2 '16 at 7:43
• it's not a duplicate. It's a different question with the same title Jun 2 '16 at 7:44
• I went over it twice and I can't spot a single difference in the problem statement; as far as I can tell, you merely added your approach. If you insist that there's a difference, please point it out. Jun 2 '16 at 7:46
• It's saying create $X$ and $Y$ using the definitions given and then use their properties to solve. $Y$ appears to be the elements of $\omega_n$ which are distinct. So it would appear $\omega_n$ can generate duplicate values; you are only to assemble the distinct ones into $Y$. Jun 2 '16 at 7:47
• The problem is very similar. In my last post, I had to use induction. In this post, I have to use a combinatorial argument. Sorry for the inconvenience, but math stack exchange is my only source of help to get my homework done. Jun 2 '16 at 7:48

The idea: first to count the number of tuples $(n_1,\dots,n_k)$ where the $n_i$ are distinct elements of $\Omega_n$. The result of that counting is the cardinality of set $Y$ and it equals $$n(n-1)\cdots(n-k+1)$$

Do you see why?

A tuple $(n_1,n_2\dots,n_k)\in Y$ induces a subset $\{n_1,n_2\dots,n_k\}$ of $\Omega_n$ that has cardinality $k$. However, e.g. tuple $(n_2,n_1\dots,n_k)\in Y$ where $n_1,n_2$ are switched gives the same subset. This indicates overcounting that must be repaired. This by dividing the cardinality of $Y$ by the number of tuples $\tau\in Y$ that satisfy $\tau R(n_1,\cdots,n_k)$.

A tuple $\tau$ that satisfies can be written $(n_{\sigma(1)},\dots,n_{\sigma(k)})$ as where $\sigma$ is a permutation on $\{1,\dots,k\}$.

There are $k!$ permutions so the end result is:$$n(n-1)\cdots(n-k+1)/k!=\binom{n}{k}$$

• Let me see if I understand the first idea. You wanna count different tuples. Does $n_i$ imply difference. How are they different. If they are different, they have to differ at least by one element or they have to differ by the ordering. Jun 2 '16 at 8:09
• If e.g. $n=3$ and $k=2$ then I find the $3\times2=6$ tuples $(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)$. The $n_i$ are demanded to be distinct, so not the tuples $(1,1),(2,2),(3,3)$. This leads to the sets $\{1,2\},\{1,3\},\dots$ but every set is counted $2!=2$ times (note that $\{1,2\}=\{2,1\}$). So to repair you must divide by $2!$. Final result: $3=\binom32$ subsets of $\{1,2,3\}$ that have cardinality $2$. Jun 2 '16 at 9:38
• To find the number of tuples: for $n_1$ there are $n$ choices; for $n_2$ there are $n-1$ choices left then, et cetera. Jun 2 '16 at 9:40