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?

  • $\begingroup$ Please don't deliberately duplicate questions; this is an abuse of the site. $\endgroup$
    – joriki
    Jun 2 '16 at 7:43
  • $\begingroup$ it's not a duplicate. It's a different question with the same title $\endgroup$ Jun 2 '16 at 7:44
  • $\begingroup$ 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. $\endgroup$
    – joriki
    Jun 2 '16 at 7:46
  • $\begingroup$ 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$. $\endgroup$ Jun 2 '16 at 7:47
  • $\begingroup$ 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. $\endgroup$ 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}$$

  • $\begingroup$ 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. $\endgroup$ Jun 2 '16 at 8:09
  • $\begingroup$ 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$. $\endgroup$
    – drhab
    Jun 2 '16 at 9:38
  • $\begingroup$ 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. $\endgroup$
    – drhab
    Jun 2 '16 at 9:40

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.