Evaluating $\sum_{0\leq k \leq l \leq n}\binom{k}{2}\binom{l}{k}\binom{n}{l}$ I'm trying to understand the process of evaluating this sum. I know the above equals to:
$$|\{(A,B,C)\mid A\subseteq B \subseteq C \subseteq [n] \wedge |A| = 2\}|$$
...Yet, how can I express this using $n$?
 A: For a combinatorial proof, note that there are $\binom{n}{2}$ ways to select $A$ and then 3 independent choices for each of the remaining $n-2$ elements: be in $B\setminus A$, $C\setminus B$, or $[n] \setminus C$.  So the cardinality of your set is $\binom{n}{2}3^{n-2}$.
A: $$
\eqalign{
  & \sum\limits_{0\, \le \,k \le \,l\, \le \,n\;} {\left( \matrix{
  k \cr 
  2 \cr}  \right)\left( \matrix{
  l \cr 
  k \cr}  \right)\left( \matrix{
  n \cr 
  l \cr}  \right)}  =   \cr 
  &  = \sum\limits_{2\, \le \,k \le \,l\, \le \,n\;} {\left( \matrix{
  k \cr 
  k - 2 \cr}  \right)\left( \matrix{
  l \cr 
  l - k \cr}  \right)\left( \matrix{
  n \cr 
  n - l \cr}  \right)}  =   \cr 
  &  = \sum\limits_{2\, \le \,k \le \,l\, \le \,n\;} {{{k!} \over {2!\left( {k - 2} \right)!}}{{l!}
 \over {k!\left( {l - k} \right)!}}{{n!} \over {l!\left( {n - l} \right)!}}}  =   \cr 
  &  = \sum\limits_{2\, \le \,k \le \,l\, \le \,n\;} {{1 \over {2!\left( {k - 2} \right)!}}
{1 \over {\left( {l - k} \right)!}}{{n!} \over {\left( {n - l} \right)!}}}  =   \cr 
  &  = {{n!} \over {2!\left( {n - 2} \right)!}}\sum\limits_{2\, \le \,k \le \,l\, \le \,n\;}
 {{{\left( {n - 2} \right)!} \over {\left( {k - 2} \right)!\left( {l - k} \right)!\left( {n - l} \right)!}}}  =   \cr 
  &  = \left( \matrix{
  n \cr 
  2 \cr}  \right)\sum\limits_{\scriptstyle \left\{ {\matrix{
   {a,b,c}  \cr 
   {a + b + c = n - 2}  \cr 
 } } \right. \atop 
  \scriptstyle \;}  {{{\left( {n - 2} \right)!} \over {a!b!c!}}}  =   \cr 
  &  = \left( \matrix{
  n \cr 
  2 \cr}  \right)3^{\,n - 2}  \cr} 
$$
A: Use ${n \choose p}{p \choose q}={n \choose q} {n-q \choose p-q}$ two times below.
$$S=\sum_{0 \le k\le l \le n}{k \choose 2} {n \choose l}{k \choose k}=\sum_{0 \le k\le l \le n} {k \choose 2} {n\choose k}{n-k \choose l-k}$$
$$\implies S=\sum_{k=0}^{n} {k\choose 2} {n \choose k} \sum_{l=k}^{n} {n-k \choose l-k}=\sum_{k=0}^{n} {k\choose 2} {n \choose k} \sum_{j=0}^{n-k} {n-k \choose j}.$$
Here we took $l-k=j$
$$\implies S=\sum_{k=0}^{n}  {k\choose 2} {n \choose k} 2^{n-k}=\sum_{k=0}^{n}  {n\choose k} {k \choose 2} 2^{n-k}.$$
$$\implies {n \choose 2} \sum_{k=0}^{n}{n-2 \choose k-2}2^{n-k} =\implies 2^{n+2}{n \choose 2} \sum_{m=0}^{n-2}{n-2 \choose m} 2^{-m}={n \choose 2}2^{n-2}(1+1/2)^{n-2}= {n \choose 2} 3^{n-2}$$
