Evaluando $\sum_{0\leq k \leq l \leq n}\binom{k}{2}\binom{l}{k}\binom{n}{l}$

Question

Estoy tratando de entender el proceso de evaluar esta suma. Sé que lo anterior es igual a: $$|\{(A,B,C)\mid A\subseteq B \subseteq C \subseteq [n] \wedge |A| = 2\}|$$ ...Sin embargo, ¿cómo puedo expresar esto usando $n$?

Answer 1

Para una prueba combinatoria, nota que hay $\binom{n}{2}$ formas de seleccionar $A$ y luego 3 opciones independientes para cada uno de los elementos restantes $n-2$: estar en $B\setminus A$, $C\setminus B$, o $[n] \setminus C$. Así que la cardinalidad de tu conjunto es $\binom{n}{2}3^{n-2}$.

Answer 2

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

Answer 3

Usa ${n \choose p}{p \choose q}={n \choose q} {n-q \choose p-q}$ dos veces abajo. $$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}.$$ Aquí tomamos $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}$$