Moc zbioru

[Nuna]

Niech \(\displaystyle{ X_{i} = [n] \times \{i\}}\), gdzie \(\displaystyle{ [n] = \{1,2,3,...,n\}}\) oraz \(\displaystyle{ S_{n} = \left\{ A \in P([n] \times [n]) : (\forall i) (A \cap X_{i} = \emptyset)\right\}}\). Oblicz moc \(\displaystyle{ S_{n}}\).
Moja propozycja wygląda tak:
Ustalmy \(\displaystyle{ i \in [n]}\). Wtedy \(\displaystyle{ A \in P([n] \times ([n] \setminus \{i\}))}\) (wtedy te zbiory są rozłączne). Zatem mamy \(\displaystyle{ 2^{n(n-1)}}\) takich różnych \(\displaystyle{ A}\). Ponieważ \(\displaystyle{ i}\) może przyjąć \(\displaystyle{ n}\) wartości to \(\displaystyle{ \left| S_{n}\right| = n \cdot 2^{n(n-1)} }\).
Proszę o krytykę

[FasolkaBernoulliego]

Jak dla mnie to \(\displaystyle{ 1}\). Skoro dla każdego \(\displaystyle{ i}\) ma być \(\displaystyle{ A \cap X_i = \emptyset}\), to znaczy, że do \(\displaystyle{ A}\) nie mogą należeć żadne elementy postaci \(\displaystyle{ (1,i), (2,i), \ldots (n,i)}\) dla żadnego \(\displaystyle{ i}\), czyli nie może należeć żaden element z \(\displaystyle{ [n] \times [n]}\), czyli jedyny taki zbiór to \(\displaystyle{ \emptyset}\).

Ale pewnie coś nie ogarniam.

[Nuna]

Skoro dla każdego \(\displaystyle{ i}\) ma być \(\displaystyle{ A \cap X_i = \emptyset}\), to znaczy, że do \(\displaystyle{ A}\) nie mogą należeć żadne elementy postaci \(\displaystyle{ (1,i), (2,i), \ldots (n,i)}\) dla żadnego \(\displaystyle{ i}\), czyli nie może należeć żaden element z \(\displaystyle{ [n] \times [n]}\), czyli jedyny taki zbiór to \(\displaystyle{ \emptyset}\).

Zgadzam się, ale według mnie wystarczy urozłącznić te zbiory. Niech \(\displaystyle{ i = 1 }\). Wtedy np. do A mogą należeć punkty (1,2), (1,3)... byle na drugiej współrzędnej nie pojawiła się jedynka. Nie wiem czy dobrze myślę

[FasolkaBernoulliego]

Patrząc na Twoje rozwiązanie, wydaje mi się, że w definicji \(\displaystyle{ S_n}\) powinno być \(\displaystyle{ \exists}\) zamiast \(\displaystyle{ \forall}\).

Wówczas Twój sposób rozumowania nie jest poprawny, gdyż niektóre z podzbiorów \(\displaystyle{ [n] \times ([n] \backslash \{i\})}\) pokrywają się z podzbiorami \(\displaystyle{ [n] \times [n] (\backslash \{j\})}\). Np. dla \(\displaystyle{ i=1, j=2}\) można wziąć zbiór jednoelementowy \(\displaystyle{ \{ (1,3) \}}\). Będziesz go liczyć więcej, niż raz (dokładnie to \(\displaystyle{ n-1}\) razy).

[Nuna]

Faktycznie, błędem jest wybieraniem A oddzielnie dla każdego \(\displaystyle{ X_{i} }\). Rozumiem też błąd w moim rozumowaniu, szukamy A, który jest uniwersalny, tzn. dobry dla każdego \(\displaystyle{ X_{i} }\), a takie A nie istnieje... Pytanie czy błąd w zadaniu, czy tak ma być. Drugi podpunkt to policzenie \(\displaystyle{ \lim_{ n\to \infty } \frac{\left| S_{n}\right| }{2^{n^{2}} }}\), trochę dziwnie gdyby sprowadzało się to do tak trywialnej granicy.

[FasolkaBernoulliego]

Myślę, że w zadaniu trzeba brać "istnieje i" (czyli tak jak robisz do tej pory), wtedy jest ciekawe. Spróbuj naprawić wytknięty przeze mnie błąd rozumowania, jak będą problemy to daj znać, może coś podpowiem.

[Nuna]

Ok, to drugie podejście.
Jeśli np. \(\displaystyle{ A = [n] \times \left\{ 1,2,3\right\} }\), to \(\displaystyle{ X_{4} = [n] \times \left\{ 4\right\} }\) będzie działał. I będzie on działał również dla \(\displaystyle{ A = \{1\} \times\left\{ 1,2,3\right\} }\). Widać, że \(\displaystyle{ A \neq [n] \times [n]}\), bo wówczas taki \(\displaystyle{ X}\) nie istnieje. Zatem dla każdego \(\displaystyle{ A}\) z wyjątkiem tego jednego istnieje taki zbiór \(\displaystyle{ X}\), że \(\displaystyle{ A \cap X_{i} = \emptyset}\). I teraz tak, chcę uniknąć zliczania \(\displaystyle{ X}\), jak widać z nimi sprawa jest bardziej skomplikowana. Dlatego zajmę się problemem ile jest takich \(\displaystyle{ A}\) dla których jest "dobry" \(\displaystyle{ X_{i}}\). Będzie ich \(\displaystyle{ 2^{n(n-1)}}\) ( \(\displaystyle{ \left| P([n] \times ([n] \setminus \left\{ n\right\} )\right| }\)).

[FasolkaBernoulliego]

Widać, że \(\displaystyle{ A \neq [n] \times [n]}\), bo wówczas taki \(\displaystyle{ X}\) nie istnieje.

To prawda.

Zatem dla każdego \(\displaystyle{ A}\) z wyjątkiem tego jednego istnieje taki zbiór \(\displaystyle{ X}\), że \(\displaystyle{ A \cap X_{i} = \emptyset}\).

To już nie, np. \(\displaystyle{ \{(1,1), (2,2), (3,3), \ldots, (n,n) \} \neq [n] \times [n]}\), ale nie znajdziesz dla niego \(\displaystyle{ X_i}\).

I teraz tak, chcę uniknąć zliczania \(\displaystyle{ X}\), jak widać z nimi sprawa jest bardziej skomplikowana. Dlatego zajmę się problemem ile jest takich \(\displaystyle{ A}\) dla których jest "dobry" \(\displaystyle{ X_{i}}\). Będzie ich \(\displaystyle{ 2^{n(n-1)}}\) ( \(\displaystyle{ \left| P([n] \times ([n] \setminus \left\{ n\right\} )\right| }\)).

No dobra, tu się zgadza, \(\displaystyle{ X_i}\) będzie "dobry" dla \(\displaystyle{ 2^{n(n-1)}}\) zbiorów \(\displaystyle{ A}\). Tylko teraz pytanie ile z nich będzie również "dobre" dla \(\displaystyle{ X_j}\)?

Podpowiedź (nie korzystaj, jak chcesz samodzielnie):

Ukryta treść:    

Ja jak liczyłem, to rozdzieliłem sobie wszystkie podzbiory zbioru \(\displaystyle{ [n] \times [n]}\) na:
zbiór pusty,
niepuste zbiory, które mają elementy tylko w jednym wierszu (czyli tylko z jedną wartością na drugim indeksie)
niepuste zbiory, które mają elementy dokładnie w dwóch wierszach
...
niepuste zbiory, które mają elementy dokładnie w (n-1) wierszach
niepuste zbiory, które mają elementy dokładnie w n wierszach

Wszystkie poza tymi ostatnimi pasują do naszej definicji A. Może to coś pomoże?

[Nuna]

niepuste zbiory, które mają elementy dokładnie w (n-1) wierszach
niepuste zbiory, które mają elementy dokładnie w n wierszach

Wszystkie poza tymi ostatnimi pasują do naszej definicji A. Może to coś pomoże?

Nie rozumiem czemu przedostatni jest zły. Jeśli \(\displaystyle{ A = \left[ n\right] \times \left\{ n-1\right\} }\), to dobrym X będzie \(\displaystyle{ X_{n} = \left[ n\right] \times \left\{ n\right\} }\), jeżeli dobrze rozumiem co chcemy osiągnąć.
W każdym razie...
Takich A w postaci niepusty zbiór i jeden wiersz mamy \(\displaystyle{ {n \choose 1} \cdot 2^{n}}\), dla dwóch wierszy \(\displaystyle{ {n \choose 2} \cdot 2^{ n} }\) itd.
Więc ogólnie takich A, dla których istnieje X byłoby \(\displaystyle{ \sum_{k=0}^{n-2} \left( {n \choose k} 2^{n} -1\right)}\). Nie wiem dlaczego n-2, ale chyba tak to by wyglądało; odejmuję 1, bo nie chcę mieć już tam zbioru pustego.

[FasolkaBernoulliego]

Nie rozumiem czemu przedostatni jest zły.

Przez "ostatnie" miałem na myśli tylko te, które mają elementy we wszystkich \(\displaystyle{ n}\) wierszach.

Jeśli \(\displaystyle{ A = \left[ n\right] \times \left\{ n-1\right\} }\), to dobrym X będzie \(\displaystyle{ X_{n} = \left[ n\right] \times \left\{ n\right\} }\), jeżeli dobrze rozumiem co chcemy osiągnąć.

Podany przykład ma elementy tylko w \(\displaystyle{ (n-1)}\)-szym wierszu, chodziło chyba raczej o \(\displaystyle{ A = \left[ n\right] \times \left[n - 1 \right] }\)?

Takich A w postaci niepusty zbiór i jeden wiersz mamy \(\displaystyle{ {n \choose 1} \cdot 2^{n}}\)

Liczysz \(\displaystyle{ n}\) razy zbiór pusty...

dla dwóch wierszy \(\displaystyle{ {n \choose 2} \cdot 2^{ n} }\) itd.

To nie jest prawda. Wybór wierszy ok \(\displaystyle{ {n \choose 2}}\), ale potem nie. Mogłoby być \(\displaystyle{ 2^{2n}}\), ale wtedy z kolei byłyby liczone (wielokrotnie) zbiory puste i zbiory mające elementy tylko w 1 wierszu. Rzecz w tym, żeby mieć pewność, że nie policzymy żadnego zbioru więcej niż raz.

odejmuję 1, bo nie chcę mieć już tam zbioru pustego.

Ok, ale musisz to zrobić już wcześniej.

[Nuna]

Podany przykład ma elementy tylko w \(\displaystyle{ (n-1)}\)-szym wierszu, chodziło chyba raczej o \(\displaystyle{ A = \left[ n\right] \times \left[n - 1 \right] }\)?

Tak, właśnie oto mi chodziło. Wtedy ten X jest dobry.

Ok, to jeszcze raz
Jeśli mam A w postaci \(\displaystyle{ B \times \left\{ a\right\} }\), gdzie \(\displaystyle{ B \subseteq \left[ n\right], a,b \in \left[ n\right] }\) to wówczas mogę wybrać a na \(\displaystyle{ {n \choose 1} }\) sposobów. Zbiorów A w takiej postaci mam \(\displaystyle{ 2^{n}}\), bez pustego \(\displaystyle{ 2^{n} - 1}\). Zatem takich różnych A \(\displaystyle{ {n \choose 1} \cdot \left(2^{n} - 1 \right) }\). Dla "dwóch wierszy" \(\displaystyle{ {n \choose 2} \cdot \left(2^{n} - 1 \right) }\) itd. Mam cały czas \(\displaystyle{ 2^{n}}\), bo ta druga część jest "na sztywno", liczba elementów cały czas jest taka sama. Jeśli dobrze myślę, to muszę oddzielić przypadek zbioru pustego, wzór tutaj nie zadziała. Zatem \(\displaystyle{ 1 + \sum_{k=1}^{n-1} {n \choose k} \left( 2^{n}-1\right) }\)

[FasolkaBernoulliego]

Chyba już rozumiem na czym polega problem. Nie wszystkie podzbiory iloczynu kartezjańskiego dwóch zbiorów można zapisać w postaci iloczynu kartezjańskiego, np. \(\displaystyle{ \{(1,1), (2,2)\} \subset [2] \times [2]}\) nie zapiszesz jako iloczyn kartezjański, no bo jak?

Dlatego dla dwóch wierszy odpowiedni zbiór \(\displaystyle{ A}\) nie musi być postaci \(\displaystyle{ B \times \{a,b\}}\), np. dla pierwszego i drugiego wiersza możemy rozważać zbiór taki jak wyżej \(\displaystyle{ \{(1,1), (2,2)\}}\). Na \(\displaystyle{ 2^n -1}\) sposobów wybierasz elementy leżące w jednym wierszu i na \(\displaystyle{ 2^n -1}\) leżące w drugim, więc ogólnie takich zbiorów, które mają elementy w pierwszym i drugim wierszu, i nigdzie indziej, będziesz mieć \(\displaystyle{ (2^n -1)^2}\).

[Nuna]

No to robi się coraz ciekawiej...
Faktycznie A nie musi tak wyglądać, przecież to może być dowolna konfiguracja par liczb naturalnych...
Dziękuję za pomoc

[FasolkaBernoulliego]

Zauważ tylko, że nie musisz liczyć tej sumy po kolei. Znasz liczbę wszystkich podzbiorów, wystarczy, że wyznaczysz liczbę wszystkich podzbiorów mających elementy w każdym możliwym wierszu i odejmiesz.