Unread post
by Zzzz » Thu Jan 27, 2011 6:28 pm
Just got another proof that doesn't need that identity.
Let $A$ be set of $n$ elements. Now, how many subsets are there which contain $3$ or $4$ elements? Let $m$ be the answer.
If we take any $2$ subsets of $2$ elements, their union will be either a $3$-element subset or a $4$-element subset. $\binom {n}{2}$ is the number of $2$-element subset. We can choose $2$ of them in $\binom {\binom {n}{2}}{2}$ ways. But we will get each of $3$ or $4$- element subsets for $3$ times if we count this way. For example a $3$ element subset $\{a,b,c\}$ can be obtained by $\{a,b\} \cup \{b,c\}$ or $\{c,a\} \cup \{b,c\}$ or $\{a,b\} \cup \{c,a\}$.
A $4$-element subset $\{a,b,c,d\}$ can also be obtained by $\{a,b\} \cup \{c,d\}$ or $\{a,c\} \cup \{b,d\}$ or $\{a,d\} \cup \{b,c,\}$.
So, $\binom {\binom {n}{2}}{2} = 3m$ ... $(1)$
Now, add an extra element in set $A$ called 'Zzzz'. Now choose a $4$-element subset of this new set. We can do this in $\binom {n+1}{4}$ ways. If 'Zzzz' is in the set then we will consider it as 'nothing' and it will be a $3$-element subset of $A$. If 'Zzzz' isn't there then it will be a $4$-element subset of $A$.
So, $m= \binom {n+1}{4}$
From $(1)$, $\binom{ \binom{n}{2} }{2}=3\cdot \binom{n+1}{4}$
গল্পটা কি বেশি গাঁজাখুরি হইল ?