Funkcje tworzące uporządkowane trójki
Funkcje tworzące uporządkowane trójki
Witam, bardzo potrzebuję pomocy jak najszybciej z takim zadaniem:
Ile jest uporządkowanych trójek \(\displaystyle{ (A_1, A_2, A_3)}\) takich, że \(\displaystyle{ A_1 \cup A_2 \cup A_3 =[n]}\).
Ile jest uporządkowanych trójek \(\displaystyle{ (A_1, A_2, A_3)}\) takich, że \(\displaystyle{ A_1 \cup A_2 \cup A_3 =[n]}\).
Ostatnio zmieniony 29 mar 2020, o 21:23 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- Dasio11
- Moderator
- Posty: 10223
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2361 razy
Re: Funkcje tworzące uporządkowane trójki
Wskazówka: rozważ tabelę o trzech wierszach i \(\displaystyle{ n}\) kolumnach. Trójkę \(\displaystyle{ (A_1, A_2, A_3)}\) można utożsamić z częściowym wypełnieniem tabeli krzyżykami w taki sposób, by w wierszu \(\displaystyle{ i}\)-tym, kolumnie \(\displaystyle{ j}\)-tej znalazł się krzyżyk wtedy i tylko wtedy, gdy \(\displaystyle{ j \in A_i}\). Jakiemu warunkowi odpowiada wtedy równość \(\displaystyle{ A_1 \cup A_2 \cup A_3 = [n]}\) i ile jest tabelek spełniających taki warunek?
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Funkcje tworzące uporządkowane trójki
A nie łatwiej rozwiązać w całkowitych nieujemnych:
\(\displaystyle{ x_{1}+x_{2}+x_{3}+...+x_{7}=n}\)
Przy założeniu , że zbiory mogą być również i puste...
\(\displaystyle{ x_{1}+x_{2}+x_{3}+...+x_{7}=n}\)
Przy założeniu , że zbiory mogą być również i puste...
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Funkcje tworzące uporządkowane trójki
Te trzy zbiory , oraz ich części wspólne podwójne i potrójne dzielą obszar na 7 części , tak jak dwa zbiory dzielą obszar na trzy części:
\(\displaystyle{ A \setminus B, B \setminus A, A \cap B}\)
I teraz sprawdzamy ile elementów zawiera każdy z obszarów...
W przypadku trzech zbiorów mamy siedem części (obszarów)...
\(\displaystyle{ A \setminus B, B \setminus A, A \cap B}\)
I teraz sprawdzamy ile elementów zawiera każdy z obszarów...
W przypadku trzech zbiorów mamy siedem części (obszarów)...
- Dasio11
- Moderator
- Posty: 10223
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2361 razy
Re: Funkcje tworzące uporządkowane trójki
Takie rozwiązanie jest niepoprawne, bo dla \(\displaystyle{ n=2}\) dwie pary \(\displaystyle{ (\{ 1 \}, \{ 2 \}, \varnothing)}\), \(\displaystyle{ (\{ 2 \}, \{ 1 \}, \varnothing)}\) zlicza jako jedną.
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Funkcje tworzące uporządkowane trójki
Według mnie jest to niepoprawne bo jest różnica, czy dwa elementy są tylko w zbiorze A a jeden tylko w B, a czy:
Jeden element w A a dwa tylko w B....Zbiory A i B są w końcu rozróżnialne...
Dodano po 6 minutach 25 sekundach:
ja wyczaiłem Ty proponujesz , żeby układy symetryczne nie rozróżniać między sobą...
Dodano po 27 minutach 33 sekundach:
Na to też mam pewną propozycję dla Twojej propozycji choć się z nią nie zgadzam , przykład np. dla trójki zbiorów:
\(\displaystyle{ x_{1}+x_{2}+x_{3}+y_{1}+y_{2}+y_{3}+t=n}\)
\(\displaystyle{ x_{i}}\) - są to obszary typu:\(\displaystyle{ A \setminus (B \cup C)}\)
\(\displaystyle{ y_{i} }\) - są to obszary typu: \(\displaystyle{ A \cap B \setminus A \cap B \cap C}\)
\(\displaystyle{ t}\) - to obszar: \(\displaystyle{ A \cap B \cap C}\)
I teraz jeżeli by było , że symetria wewnątrz obszarów \(\displaystyle{ x_{i} \wedge y_{i}}\) byłaby niepożądana musielibyśmy użyć partycji pomieszanej z kombinacjami, a dokładniej:
Rozpatrujemy w całkowitych nieujemnych rozwiązania:
\(\displaystyle{ X+Y+t=n}\)
Tu rozwiązań mamy:
\(\displaystyle{ {n+2 \choose 3} }\)
gdzie:
\(\displaystyle{ x_{1}+x_{2}+x_{3}=X , y_{1}+y_{2}+y_{3}=Y, t=t}\)
I teraz dla każdego rozwiązania liczymy partycje:
Wtedy symetryczne układy będą odrzucane...
\(\displaystyle{ P(X,i) i=1,2,3 , P(Y,i) , i=1,2,3}\)...
Dodano po 1 minucie 6 sekundach:
Ale dziwię się, że nie rozróżnia się zbiorów...
Dodano po 21 minutach 21 sekundach:
Pokażę to na przykładzie dwoch zbiorów i \(\displaystyle{ n=3}\)
\(\displaystyle{ A \wedge B}\)
\(\displaystyle{ x_{1}+x_{2}+t=3}\)
\(\displaystyle{ x_{1}+x_{2}=X}\)
Najpierw rozpatrujemy równanie:
\(\displaystyle{ X+t=3}\)
rozpatrujemy przypadki:
\(\displaystyle{ 0+3=3, 1+2=3 , 2+1=3, 3+0=3}\)
pierwszy przypadek \(\displaystyle{ P(0,i)}\) można przyjąć, że zero, lub dla bezpieczeństwa jeden w zależności jak zapiszemy wzór w przypadku ogólnym... odpowiada to: \(\displaystyle{ x_{1}+x_{2}=0}\)
\(\displaystyle{ P(1,1)=1}\) więc drugie równanie będzie też tylko jedno , odpowiada to: \(\displaystyle{ x_{1}+x_{2}=1}\)
\(\displaystyle{ P(2,1)=1, P(2,2)=1}\) więc w trzecim przypadku będzie dwa równania , odpowiada to: \(\displaystyle{ x_{1}+x_{2}=2}\)
\(\displaystyle{ P(3,1)=1, P(3,2)=1}\) - mamy tu razem 2 przypadki , odpowiada to: \(\displaystyle{ x_{1}+x_{2}=3}\)
Co razem da sześć niesymetrycznych rozwiązań co daje wynik...
Dodano po 11 minutach 13 sekundach:
Zamieszanie małe bierze się stąd, że musimy przewidywać rozwiązania zerowe i dlatego trzeba partycje rozpatrywać osobno dla każdego \(\displaystyle{ i}\), bo ściśle zera w partycjach nie istnieją...
Dodano po 2 minutach 38 sekundach:
Ale i tak w zadaniu jest podać uporządkowane trójki, czylijednak zbiory są rozróżnialne, więc symetria pozostaje we wzorach choć nie ma jej w zadaniu...
Dodano po 15 minutach 26 sekundach:
"ładnie" zapisane powinno wyglądać tak:
\(\displaystyle{ \sum_{X+Y+t=n}^{}\left[ P(X,1)+P(X,2)+P(X,3)\right] \cdot \left[ P(Y,1)+P(Y,2)+P(Y,3)\right]\left[ \cdot P(t,1)\right] }\)
W razie gdy:
\(\displaystyle{ X \vee Y \vee t=0}\) - wtedy przyjmujemy , że cały kwadratowy nawias wynosi jeden, żeby uniknąć nieporozumień...
Można to rozszerzyć na dowolną ilość zbiorów...
Jeden element w A a dwa tylko w B....Zbiory A i B są w końcu rozróżnialne...
Dodano po 6 minutach 25 sekundach:
ja wyczaiłem Ty proponujesz , żeby układy symetryczne nie rozróżniać między sobą...
Dodano po 27 minutach 33 sekundach:
Na to też mam pewną propozycję dla Twojej propozycji choć się z nią nie zgadzam , przykład np. dla trójki zbiorów:
\(\displaystyle{ x_{1}+x_{2}+x_{3}+y_{1}+y_{2}+y_{3}+t=n}\)
\(\displaystyle{ x_{i}}\) - są to obszary typu:\(\displaystyle{ A \setminus (B \cup C)}\)
\(\displaystyle{ y_{i} }\) - są to obszary typu: \(\displaystyle{ A \cap B \setminus A \cap B \cap C}\)
\(\displaystyle{ t}\) - to obszar: \(\displaystyle{ A \cap B \cap C}\)
I teraz jeżeli by było , że symetria wewnątrz obszarów \(\displaystyle{ x_{i} \wedge y_{i}}\) byłaby niepożądana musielibyśmy użyć partycji pomieszanej z kombinacjami, a dokładniej:
Rozpatrujemy w całkowitych nieujemnych rozwiązania:
\(\displaystyle{ X+Y+t=n}\)
Tu rozwiązań mamy:
\(\displaystyle{ {n+2 \choose 3} }\)
gdzie:
\(\displaystyle{ x_{1}+x_{2}+x_{3}=X , y_{1}+y_{2}+y_{3}=Y, t=t}\)
I teraz dla każdego rozwiązania liczymy partycje:
Wtedy symetryczne układy będą odrzucane...
\(\displaystyle{ P(X,i) i=1,2,3 , P(Y,i) , i=1,2,3}\)...
Dodano po 1 minucie 6 sekundach:
Ale dziwię się, że nie rozróżnia się zbiorów...
Dodano po 21 minutach 21 sekundach:
Pokażę to na przykładzie dwoch zbiorów i \(\displaystyle{ n=3}\)
\(\displaystyle{ A \wedge B}\)
\(\displaystyle{ x_{1}+x_{2}+t=3}\)
\(\displaystyle{ x_{1}+x_{2}=X}\)
Najpierw rozpatrujemy równanie:
\(\displaystyle{ X+t=3}\)
rozpatrujemy przypadki:
\(\displaystyle{ 0+3=3, 1+2=3 , 2+1=3, 3+0=3}\)
pierwszy przypadek \(\displaystyle{ P(0,i)}\) można przyjąć, że zero, lub dla bezpieczeństwa jeden w zależności jak zapiszemy wzór w przypadku ogólnym... odpowiada to: \(\displaystyle{ x_{1}+x_{2}=0}\)
\(\displaystyle{ P(1,1)=1}\) więc drugie równanie będzie też tylko jedno , odpowiada to: \(\displaystyle{ x_{1}+x_{2}=1}\)
\(\displaystyle{ P(2,1)=1, P(2,2)=1}\) więc w trzecim przypadku będzie dwa równania , odpowiada to: \(\displaystyle{ x_{1}+x_{2}=2}\)
\(\displaystyle{ P(3,1)=1, P(3,2)=1}\) - mamy tu razem 2 przypadki , odpowiada to: \(\displaystyle{ x_{1}+x_{2}=3}\)
Co razem da sześć niesymetrycznych rozwiązań co daje wynik...
Dodano po 11 minutach 13 sekundach:
Zamieszanie małe bierze się stąd, że musimy przewidywać rozwiązania zerowe i dlatego trzeba partycje rozpatrywać osobno dla każdego \(\displaystyle{ i}\), bo ściśle zera w partycjach nie istnieją...
Dodano po 2 minutach 38 sekundach:
Ale i tak w zadaniu jest podać uporządkowane trójki, czylijednak zbiory są rozróżnialne, więc symetria pozostaje we wzorach choć nie ma jej w zadaniu...
Dodano po 15 minutach 26 sekundach:
"ładnie" zapisane powinno wyglądać tak:
\(\displaystyle{ \sum_{X+Y+t=n}^{}\left[ P(X,1)+P(X,2)+P(X,3)\right] \cdot \left[ P(Y,1)+P(Y,2)+P(Y,3)\right]\left[ \cdot P(t,1)\right] }\)
W razie gdy:
\(\displaystyle{ X \vee Y \vee t=0}\) - wtedy przyjmujemy , że cały kwadratowy nawias wynosi jeden, żeby uniknąć nieporozumień...
Można to rozszerzyć na dowolną ilość zbiorów...
- Dasio11
- Moderator
- Posty: 10223
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2361 razy
Re: Funkcje tworzące uporządkowane trójki
Co jest niepoprawne?
To źle "wyczaiłeś". Nic nie proponowałem, tylko uzasadniłem, dlaczego Twoje rozwiązanie nie działa.
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Funkcje tworzące uporządkowane trójki
Absolutnie nie uzasadniłeś tylko podałeś kontrprzykład, który nie wiem czemu miałby być prawdziwy, te dwa przykłady które uważasz za identyczne,Nic nie proponowałem, tylko uzasadniłem, dlaczego Twoje rozwiązanie nie działa.
one identyczne być nie muszą...Nie wiem czym się kierujesz?
Dodano po 4 minutach 50 sekundach:
Lecz potem idąc za Twoim tokiem rozumowania(którego nie podzielam) zaproponowałem inne rozwiązanie , które być może jest zgodne z tym co masz na myśli...
Dodano po 9 minutach 15 sekundach:
Może uzasadnię czemu nie podzielam , podam mały przykład, to może się zrozumiemy bo jak na razie nie działa
Przykład:
Pani Krysia kupiła: autko i lalkę, A Pani Marysia kupiła widelec...
jak widać kupiły razem trzy elementy A - zbiór zakupów Pani Krysi, B zbiór zakupów Pani Marysi...
część wspólna ich zakupów jest jak widać zbiorem pustym...
a teraz na odwrót:
Pani Krysia kupiła Rowerek ( jeden element) a Pani Marysia kupiła (nóż i widelec) (dwa elementy) I znowu częśc wspólna ich zakupów to zbiór pusty...
I czy można powiedzieć , że te przykłady są równoważne...??
Raczej nie rozróżniasz Pani Krysi od Pani Marysi...
Dodano po 3 minutach 34 sekundach:
Więc w związku z powyższym na razie nie uzasadniłeś błędu w moim pierwszym rozumowaniu...
Dodano po 5 minutach 17 sekundach:
Nie wiem czy wiesz co miałem na myśli pisząc to zdanie...ja wyczaiłem Ty proponujesz , żeby układy symetryczne nie rozróżniać między sobą
-
- Administrator
- Posty: 34240
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Funkcje tworzące uporządkowane trójki
Arku, ćwicz trochę dyscyplinę wypowiedzi. Zamiast raczyć nas zapisem Twojego strumienia świadomości, NAJPIERW zastanów się, co chcesz napisać, POTEM jak to chcesz napisać i dopiero NA KOŃCU napisz to.
JK
JK
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Funkcje tworzące uporządkowane trójki
Przecież to właśnie zrobiłem...
jasno się wyrażam, że przypadki , które Dasio zapodaje jako nierozróżnialne ja widzę jako rozróżnialne...I na razie nikt mnie nie przekonał, że jest inaczej...
Zakładam też , że mogę nie mieć racji ale na razie brak argumentów ...
Ale potem "przestawiając" się jak mniemam na Jego tryb rozumowania wskazałem gdzie powinna być "zaburzona" symetria...
Dodano po 11 minutach 25 sekundach:
Może tak, żeby uprościć, powiedz ile powinno być rozwiązań dla tego przypadku:
\(\displaystyle{ A, B}\) i \(\displaystyle{ n=3}\)... to może się zrozumiemy...
jasno się wyrażam, że przypadki , które Dasio zapodaje jako nierozróżnialne ja widzę jako rozróżnialne...I na razie nikt mnie nie przekonał, że jest inaczej...
Zakładam też , że mogę nie mieć racji ale na razie brak argumentów ...
Ale potem "przestawiając" się jak mniemam na Jego tryb rozumowania wskazałem gdzie powinna być "zaburzona" symetria...
Dodano po 11 minutach 25 sekundach:
Może tak, żeby uprościć, powiedz ile powinno być rozwiązań dla tego przypadku:
\(\displaystyle{ A, B}\) i \(\displaystyle{ n=3}\)... to może się zrozumiemy...
- Dasio11
- Moderator
- Posty: 10223
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2361 razy
Re: Funkcje tworzące uporządkowane trójki
Powtórzę: Twoja metoda nie rozróżnia trójek \(\displaystyle{ (\{ 1 \}, \{ 2 \}, \varnothing)}\), \(\displaystyle{ (\{ 2 \}, \{ 1 \}, \varnothing)}\), bo przypisuje im jednakowe rozwiązanie \(\displaystyle{ x_1 = x_2 = 1, x_3 = \ldots = x_7 = 0}\) równania \(\displaystyle{ x_1 + \ldots + x_7 = 2}\). Natomiast w kontekście zadania powyższe trójki są rozróżnialne i dlatego Twój sposób jest błędny.
Jeśli pytasz o liczbę par zbiorów \(\displaystyle{ (A, B)}\) spełniających \(\displaystyle{ A \cup B = \{ 1, 2, 3 \}}\), to poprawnym wynikiem jest \(\displaystyle{ 27}\).
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Funkcje tworzące uporządkowane trójki
Tak miało być w zamyśle...Powtórzę: Twoja metoda nie rozróżnia trójek
Dodano po 21 minutach 15 sekundach:
Tak już teraz wiem elementy i zbiory są rozróżnialne, a ja robiłem najpierw, że zbiory rozróżnialne a elementy nierozróżnialne, a potem jeszcze zmniejszyłem stopień rozróżnialności , I oczywiście teraz już jestem przekonany bo jak najbardziej jest to logiczne, że i zbiory i elementy są rozróżnialne, pozdrawiam...
Dodano po 14 minutach 35 sekundach:
Ale i na to jest odpowiedź bo będziemy mieć suriekcje
I tak w tym ostatnim przypadku:
\(\displaystyle{ A \cup B=\left\{ 1,2,3\right\} }\)
Mamy:
\(\displaystyle{ S(3,3)+3 \cdot S(3,2)+3 \cdot S(3,1)=3!+3 \cdot 6+3 \cdot 1=6+18+3=27}\)
Dla tych trzech powinno w takim razie być:
\(\displaystyle{ \sum_{i=1}^{7} {7 \choose i} S(n,i)}\)
Gdzie \(\displaystyle{ S}\) to suriekcje...
Dodano po 17 minutach 31 sekundach:
Zresztą nie ma złego co by nie wyszło na dobre do tych dwóch rozwiązań , które pisałem powyżej można ułożyć taką treść zadania aby rozwiązaniem tegoż zadania były te moje rozwiązania...(dobre co hahaha)
-
- Administrator
- Posty: 34240
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Funkcje tworzące uporządkowane trójki
Wręcz przeciwnie - każda Twoja wypowiedź to chaotyczna seria kolejnych dopisków. Powtarzam - najpierw pomyśl, co chcesz napisać, a dopiero potem pisz, nie na odwrót.
JK