Funkcje tworzące uporządkowane trójki

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Platypus
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 29 mar 2020, o 19:38
Płeć: Mężczyzna
wiek: 18

Funkcje tworzące uporządkowane trójki

Post autor: Platypus » 29 mar 2020, o 20:30

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]}\).
Ostatnio zmieniony 29 mar 2020, o 21:23 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9084
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1959 razy

Re: Funkcje tworzące uporządkowane trójki

Post autor: Dasio11 » 29 mar 2020, o 22:57

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?

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3972
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 94 razy
Pomógł: 387 razy

Re: Funkcje tworzące uporządkowane trójki

Post autor: arek1357 » 30 mar 2020, o 12:30

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...

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9084
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1959 razy

Re: Funkcje tworzące uporządkowane trójki

Post autor: Dasio11 » 30 mar 2020, o 12:58

A jaki to ma związek z zadaniem?

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3972
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 94 razy
Pomógł: 387 razy

Re: Funkcje tworzące uporządkowane trójki

Post autor: arek1357 » 30 mar 2020, o 13:15

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)...

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9084
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1959 razy

Re: Funkcje tworzące uporządkowane trójki

Post autor: Dasio11 » 30 mar 2020, o 14:30

Takie rozwiązanie jest niepoprawne, bo dla \(\displaystyle{ n=2}\) dwie pary \(\displaystyle{ (\{ 1 \}, \{ 2 \}, \varnothing)}\), \(\displaystyle{ (\{ 2 \}, \{ 1 \}, \varnothing)}\) zlicza jako jedną.

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3972
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 94 razy
Pomógł: 387 razy

Re: Funkcje tworzące uporządkowane trójki

Post autor: arek1357 » 30 mar 2020, o 14:45

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...

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9084
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1959 razy

Re: Funkcje tworzące uporządkowane trójki

Post autor: Dasio11 » 30 mar 2020, o 16:53

arek1357 pisze:
30 mar 2020, o 16:10
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...
Co jest niepoprawne?

arek1357 pisze:
30 mar 2020, o 16:10
ja wyczaiłem Ty proponujesz , żeby układy symetryczne nie rozróżniać między sobą...
To źle "wyczaiłeś". Nic nie proponowałem, tylko uzasadniłem, dlaczego Twoje rozwiązanie nie działa.

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3972
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 94 razy
Pomógł: 387 razy

Re: Funkcje tworzące uporządkowane trójki

Post autor: arek1357 » 30 mar 2020, o 17:44

Nic nie proponowałem, tylko uzasadniłem, dlaczego Twoje rozwiązanie nie działa.
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,
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:
ja wyczaiłem Ty proponujesz , żeby układy symetryczne nie rozróżniać między sobą
Nie wiem czy wiesz co miałem na myśli pisząc to zdanie...

Jan Kraszewski
Administrator
Administrator
Posty: 26507
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4437 razy

Re: Funkcje tworzące uporządkowane trójki

Post autor: Jan Kraszewski » 30 mar 2020, o 18:10

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

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3972
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 94 razy
Pomógł: 387 razy

Re: Funkcje tworzące uporządkowane trójki

Post autor: arek1357 » 30 mar 2020, o 18:13

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...

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9084
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1959 razy

Re: Funkcje tworzące uporządkowane trójki

Post autor: Dasio11 » 30 mar 2020, o 19:05

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.

arek1357 pisze:
30 mar 2020, o 18:25
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...
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}\).

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3972
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 94 razy
Pomógł: 387 razy

Re: Funkcje tworzące uporządkowane trójki

Post autor: arek1357 » 30 mar 2020, o 19:15

Powtórzę: Twoja metoda nie rozróżnia trójek
Tak miało być w zamyśle...

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)

Jan Kraszewski
Administrator
Administrator
Posty: 26507
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4437 razy

Re: Funkcje tworzące uporządkowane trójki

Post autor: Jan Kraszewski » 30 mar 2020, o 20:17

arek1357 pisze:
30 mar 2020, o 18:25
Przecież to właśnie zrobiłem...
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

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3972
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 94 razy
Pomógł: 387 razy

Re: Funkcje tworzące uporządkowane trójki

Post autor: arek1357 » 30 mar 2020, o 20:42

Ale w ostatniej postawiłem kropkę nad "i"...

ODPOWIEDZ