Find Combinatorial Interpolation

For students of class 11-12 (age 16+)
User avatar
Moon
Site Admin
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Location: Dhaka, Bangladesh
Contact:

Find Combinatorial Interpolation

Unread post by Moon » Mon Jan 17, 2011 11:49 pm

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

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

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

Re: Find Combinatorial Interpolation

Unread post by Zzzz » Thu Jan 27, 2011 11:18 am

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:
Every logical solution to a problem has its own beauty.
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)

User avatar
Moon
Site Admin
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Location: Dhaka, Bangladesh
Contact:

Re: Find Combinatorial Interpolation

Unread post by Moon » Thu Jan 27, 2011 3:53 pm

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

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

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

Re: Find Combinatorial Interpolation

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

গল্পটা কি বেশি গাঁজাখুরি হইল ?
Every logical solution to a problem has its own beauty.
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)

Post Reply