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

Question

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

Answer 1

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<i$ 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$.

Answer 2

First, note that $$ \sum_{0\leq j<i\leq n}\binom{n}{i}\binom{i}{j}=\sum_{0\leq j\leq i\leq n}\binom{n}{i}\binom{i}{j}-\sum_{0\leq j=i\leq n}\binom{n}{i}\binom{i}{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}. $$