Jaka jest moc zbioru

[valverde12345]

Zadanie 1: Jaka jest moc zbioru \(\displaystyle{ \left\{ \left( A,B,C\right)\in P\left( \left[ n\right] \right) ^{3} : A = B \cap C \right\}}\)
\(\displaystyle{ \left[ n\right] = \left\{ 1, ..., n\right\}}\)

\(\displaystyle{ D = \left\{ \left( A,B,C\right)\in P\left( \left[ n\right] \right) \times P\left( \left[ n\right] \right) \times P\left( \left[ n\right] \right) : A = B \cap C \right\}}\)
Zbiór \(\displaystyle{ A}\) zalezy od zbiorow \(\displaystyle{ B}\) i \(\displaystyle{ C}\) wiec prawda jest:
\(\displaystyle{ \left| D\right| = \left\{ \left( B,C\right)\in P\left( \left[ n\right] \right) \times P\left( \left[ n\right] \right) \right\} = 2 ^{n} \cdot 2 ^{n} = 4 ^{n}}\)

Czy moje rozwiązanie jest poprawne?

Zadanie 2: Podaj zwartą postać sumy:
\(\displaystyle{ \sum_{k=0}^{n}k ^{2} {n \choose k} = \sum_{k=1}^{n}k ^{2} \frac{n}{k} {n-1 \choose k-1}=n \sum_{k=1}^{n}k {n-1 \choose k-1}=n \sum_{k=1}^{n}k \frac{n-1}{k-1} {n-2 \choose k-2} = n(n-1) \sum_{k=1}^{n} \frac{k}{k-1} {n-2 \choose k-2}}\)
Dalej niestety nie wiem jak to pociągnąć..

[Medea 2]

Ad 1: wyobraź sobie, że zbioru \(\displaystyle{ A}\) nie ma, wtedy zliczasz \(\displaystyle{ B, C \subseteq \{1, \dots, n\}}\).

Ad 2: skreśl wszystko, to nie jest właściwa droga do celu. Myśl kom-bi-na-to-rycz-nie. Z \(\displaystyle{ n}\) osób wybierasz \(\displaystyle{ k}\) i... i co dalej? Podpowiem, że odpowiedź to \(\displaystyle{ 2^{n-2} n (n+1)}\).

[valverde12345]

Napisałem właśnie wyżej coś takiego. Czy to jest dobrze?

[Medea 2]

Może i dobrze (jak teraz patrzę), ale z formalnego punktu widzenia... myślę, że chociażby Jan Kraszewski będzie miał Ci coś do powiedzenia.

[valverde12345]

\(\displaystyle{ \sum_{k=0}^{n}k ^{2} {n \choose k}}\)
Nie mam pomysłu jak to rozpisać ten kwadrat wszystko komplikuje, ani z wzoru Newtona nie jestem w stanie, ani w taki sposób jak próbowałem wyżej.

[Premislav]

\(\displaystyle{ k^{2}=k(k-1+1)=k(k-1)+k}\) i można rozbić na dwie sumy, które liczy się np. tak:
ze wzoru dwumianowego Newtona mamy \(\displaystyle{ (x+1)^{n}= \sum_{k=0}^{n}{n \choose k}x^{k}}\). Różniczkując tę tożsamość stronami raz, mamy \(\displaystyle{ n(x+1)^{n-1}= \sum_{k=1}^{n}{n \choose k}kx^{k-1}}\). Natomiast różniczkując drugi raz, dostajemy \(\displaystyle{ n(n-1)(x+1)^{n-2}= \sum_{k=2}^{n}{n \choose k}k(k-1)x^{k-2}}\)
Podstawiamy teraz \(\displaystyle{ x=1}\). No i trzeba uważać na zerowy i pierwszy wyraz.

Była też jakaś ładna interpretacja kombinatoryczna, której nie pamiętam, a wymyślić nie potrafię.

[valverde12345]

W takim wypadku mamy na początku:
\(\displaystyle{ \sum_{k=0}^{n}\left( k\left( k-1\right) + k\right) {n \choose k} = \sum_{k=0}^{n}k {n \choose k} + \sum_{k=0}^{n} k\left(k-1 \right) {n \choose k}}\)
Wynik pierwszej sumy to \(\displaystyle{ n \cdot 2^{n-1}}\)
Drugiej sumy \(\displaystyle{ n\left( n-1\right)2 ^{n-2}}\) (Rozwiązałem to w taki sposób jak na początku próbowałem, ale teraz wszystko ładnie się skróciło)
Ostatecznie: \(\displaystyle{ n \cdot 2^{n-1} + n\left( n-1\right)2 ^{n-2}}\)
Po doprowadzeniu do ostatecznej postaci mamy:

Podpowiem, że odpowiedź to \(\displaystyle{ 2^{n-2} n (n+1)}\)

Nigdzie się nie pomyliłem?

[Premislav]

Jest w porządku.

[Medea 2]

Nie, Twoją sumę można zwinąć do mojej przez \(\displaystyle{ n \cdot 2^{n-1} = 2 \cdot 2^{n-2}}\). To teraz obiecana interpretacja kombinatoryczna.

Po lewej wybierasz z \(\displaystyle{ n}\) osób \(\displaystyle{ k}\)-osobową grupę i dajesz im dwa cukierki (jeden pomarańczowy, drugi limonkowy, może tej samej osobie, może nie). Po prawej zaś (\(\displaystyle{ 2^{n-2} n (n+1)}\) rozbite tak, jak u Ciebie) możesz wybrać jedną osobę (z dwoma cukierkami) i dowolny podzbiór z pozostałych \(\displaystyle{ n-1}\) (oni, razem z cukierkową, będą tworzyć \(\displaystyle{ k}\)-grupę) lub dwie osoby (każda ze swoim cukierkiem) i dowolny podzbiór z pozostałych \(\displaystyle{ n-2}\) osób.

[valverde12345]

Wracając do zadania 1, intersuję mnie teraz poprawny zapis rozumowania w tym zadaniu.
Zadanie 1: Jaka jest moc zbioru \(\displaystyle{ \left\{ \left( A,B,C\right)\in P\left( \left[ n\right] \right) ^{3} : A = B \cap C \right\}}\)

Niech:
\(\displaystyle{ D = \left\{ \left( A,B,C\right)\in P\left( \left[ n\right] \right) ^{3} : A = B \cap C \right\}}\)
\(\displaystyle{ E = \left\{ \left( B,C\right)\in P\left( \left[ n\right] \right) ^{2}\right\}}\)

\(\displaystyle{ \left| E\right|=\left| \left\{ B \in P([n])\right\} \times \left\{ C \in P([n])\right\}\right|}\)

(W tym momencie nie jestem pewien czy nie powiniem to przejście jakoś zaargumentować)

\(\displaystyle{ \left| E\right|=2 ^{n} \cdot 2 ^{n} = 4 ^{n}}\)

Zauważmy, że \(\displaystyle{ \left| D\right| = \left| E\right|}\), ponieważ w rodzinie zbiorów \(\displaystyle{ D}\) zbiór \(\displaystyle{ A}\) całkowicie zależy od \(\displaystyle{ B,C}\), więc nie generuje żadnych nowych kombinacji. Stąd:
\(\displaystyle{ \left| D\right| = 4 ^{n}}\)

Czy coś takiego jest akceptowalne?

[Medea 2]

To przejście znane jest jako twierdzenie o mnożeniu (z kombinatoryki). Równość \(\displaystyle{ |D| = |E|}\) uzasadniłabym wskazując bijekcję \(\displaystyle{ D \to E}\), \(\displaystyle{ (A, B, C) \mapsto (B, C)}\).

[valverde12345]

Co do przejścia \(\displaystyle{ |D| = |E|}\) trzeba napisać ze na podstawie twierdzenia o mnożeniu albo coś w stylu ze zbiory są parami rozłączne i dopiero do kroku z zwykłym mnożeniem czy poprostu bez wspominania o tym?