Page 1 of 1

Find Combinatorial Interpolation

Posted: Mon Jan 17, 2011 11:49 pm
by Moon
If $n\geq 3$ is an integer. Find a direct combinatorial interpolation of the identity:
\[\binom{ \binom{n}{2} }{2}=3\cdot \binom{n+1}{4}\]

Combinatorial Interpolation means that you can't use algebra, rather you have to use logic to deduce it. :)
500/195

Re: Find Combinatorial Interpolation

Posted: Thu Jan 27, 2011 11:18 am
by Zzzz
Can I use this identity:\[\binom {n}{r}=\binom {n-1}{r} +\binom {n-1}{r-1}\] ?
I can prove this identity using combinatorial interpolation :roll:

Re: Find Combinatorial Interpolation

Posted: Thu Jan 27, 2011 3:53 pm
by Moon
Zzzz wrote:Can I use this identity:\[\binom {n}{r}=\binom {n-1}{r} +\binom {n-1}{r-1}\] ?
I can prove this identity using combinatorial interpolation :roll:
I think you may use this because this identity also has a nice combinatorial interpolation. :)

Re: Find Combinatorial Interpolation

Posted: Thu Jan 27, 2011 6:28 pm
by Zzzz
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}$

গল্পটা কি বেশি গাঁজাখুরি হইল ?