Find Combinatorial Interpolation

For students of class 11-12 (age 16+)
Moon
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Contact:

Find Combinatorial Interpolation

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.
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

learn how to write equations, and don't forget to read Forum Guide and Rules.

Zzzz
Posts: 172
Joined: Tue Dec 07, 2010 6:28 am
Location: 22° 48' 0" N / 89° 33' 0" E

Re: Find Combinatorial Interpolation

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
Every logical solution to a problem has its own beauty.

Moon
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Contact:

Re: Find Combinatorial Interpolation

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
I think you may use this because this identity also has a nice combinatorial interpolation.
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

learn how to write equations, and don't forget to read Forum Guide and Rules.

Zzzz
Posts: 172
Joined: Tue Dec 07, 2010 6:28 am
Location: 22° 48' 0" N / 89° 33' 0" E

Re: Find Combinatorial Interpolation

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}$

গল্পটা কি বেশি গাঁজাখুরি হইল ?
Every logical solution to a problem has its own beauty.