Matematyka.pl

\(\displaystyle{ \sum_{A, B \subseteq X} |A \cap B|}\), gdzie \(\displaystyle{ |X| = n}\)

Wydaje mi się, że to jest:
\(\displaystyle{ \sum_{k=0}^{n} k {n\choose k} \sum_{i=0, j=0}^{n-k} {n-k\choose i} {n-k -i\choose j}}\)

Wybieramy k elementów wspólnych elementów, potem z n-k elementów wybieramy i elementow zbioru A i z n-k-i wybieramy j elementów zbioru B. moc każdego \(\displaystyle{ |A \cap B|}\) wynosi k.

Pytanie, czy to dobrze oraz jak to wysumować. Próbowałem tą sumę po i,j rozdzielić na dwie i ale potrafię pozbyć się tylko jednej sumy.

Ja do zadania podszedłbym tak:

Niech \(\displaystyle{ X=\{1,2,\ldots , n\}}\). Zastanówmy się ile razy w zbiorach postaci \(\displaystyle{ A \cap B}\) pojawi się jedynka. Zbiór \(\displaystyle{ A}\) musi być postaci \(\displaystyle{ A=\{1\} \cup A'}\), a zbiór \(\displaystyle{ B}\) postaci \(\displaystyle{ B=\{1\} \cup B'}\), gdzie \(\displaystyle{ 1\notin A', B'}\). Zbiory \(\displaystyle{ A',B'}\) można wybrać na \(\displaystyle{ 2^{n-1}\cdot 2^{n-1}=4^{n-1}}\) sposobów (dlaczego?), zatem tyle razy pojawi się jedynka. Dokładnie tyle samo razy pojawi się każda z pozostałych \(\displaystyle{ n}\) liczb, dlatego szukana suma to \(\displaystyle{ n\cdot 4^{n-1}}\).

Q.

Interesuje nas liczność zbiorów, stąd jest ta potęga. Mam rację?