0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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)$ $\endgroup$ – parsiad Feb 26 '19 at 6:51
  • 2
    $\begingroup$ 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}?$$ $\endgroup$ – saulspatz Feb 26 '19 at 6:53
  • $\begingroup$ 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. $\endgroup$ – jgon Feb 26 '19 at 6:58
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.