# Evaluating $\mathop{\sum\sum}_{0\leq j< i\leq n}\binom{n}{i}\binom{i}{j}$ using combinatorial method

Evaluation of $$\mathop{\sum\sum}_{0\leq j< i\leq n}\binom{n}{i}\binom{i}{j}$$

Try: Let $$S=^nC_{1}\bigg( ^1 C_{0} \bigg)+^nC_{2}\bigg(^2C_{0}+^2C_{1}\bigg)+\cdots +^nC_{n}\bigg(^nC_{0}+^nC_{1}+^nC_{2}+\cdots \bigg)$$

$$S=^nC_{1}(2-1)+^nC_{2}(2^2-1)+\cdots ^nC_{n}(2^n-1)=3^n-2^n$$

Actually i want to solve it using Combinatorail argument

Could some help me how can i prove using Combinational method, thanks

• This might be helpful: $\sum_{0\leq j<i\leq n}f(i,j)=\sum_{0\leq j\leq i\leq n}f(i,j)-\sum_{0\leq i\leq n}f(i,i)$ – parsiad Feb 26 '19 at 6:51
• When $n=2,$ I get $5$, not $8.$ Isn't the sum the same as $$\sum_{j=0}^{n-1}\sum_{i=j+1}^n{n\choose i}{i\choose j}?$$ – saulspatz Feb 26 '19 at 6:53
• Your question needs more words to adequately explain the context. Relatedly what is a combinatorial method in this context? What possible solution to this problem wouldn't be combinatorial? Also do you want $j<i$ in the sum, or $j\le i$, which is what you have in your attempted solution. Also, generally speaking, your proof should have words in it, justifying what you're doing, and to prevent yourself from making careless errors. – jgon Feb 26 '19 at 6:58

The sum is counting labeled partitions of a set with $$n$$ elements into sets $$A$$, $$B$$, and $$C$$ with $$B\ne\varnothing$$. (Specifically, it's counting them by counting the ways to choose a set $$D$$ with $$i$$ elements, and $$A$$ with $$j elements from $$D$$. $$B=D\setminus A$$, $$C$$ is the complement of $$A$$ and $$B$$.)
The number of ways to partition the set into three labeled partitions is $$3^n$$, and if $$B=\varnothing$$, there are $$2^n$$ ways to partition the elements into the other two sets. Thus we have that our sum is $$3^n-2^n$$.
First, note that $$\sum_{0\leq j By the binomial theorem, $$\sum_{0\leq j=i\leq n}\binom{n}{i}\binom{i}{j}=\sum_{0\leq i\leq n}\binom{n}{i}\binom{i}{i}=\sum_{0\leq i\leq n}\binom{n}{i}=\sum_{0\leq i\leq n}\binom{n}{i}1^{i}1^{n-i}=(1+1)^{n}=2^{n}.$$ Once again, by the binomial theorem, $$\sum_{0\leq j\leq i\leq n}\binom{n}{i}\binom{i}{j}=\sum_{i=0}^{n}\binom{n}{i}\sum_{j=0}^{i}\binom{i}{j}=\sum_{i=0}^{n}\binom{n}{i}2^{i}=\sum_{i=0}^{n}\binom{n}{i}2^{i}1^{n-i}=\left(2+1\right)^{n}=3^{n}.$$ In conclusion, your sum is equal to $$3^{n}-2^{n}.$$