Liczba funkcji oraz relacji.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
Emiel Regis
Gość Specjalny
Gość Specjalny
Posty: 1495
Rejestracja: 26 wrz 2005, o 17:01
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 71 razy
Pomógł: 225 razy

Liczba funkcji oraz relacji.

Post autor: Emiel Regis » 25 paź 2007, o 20:40

Prosze o sprawdzenie poprawnosci moich wyników. Ewentualnie korektę wraz z komentarzem.
Co prawda zbiory X lub Y niekoniecznie są dyskretne jednak zamieściłem to w tym dziale gdyż liczyłem to w sposób kombinatoryczny.

1. Moc zbioru wszystkich funkcji z X do Y
\(\displaystyle{ |\{f| \ f: X \to Y\}| = |Y|^{|X|}}\)

2. Moc zbioru wszystkich relacji
\(\displaystyle{ |\{R: R X Y\}|=2^{|Y|} |X|}\)

\(\displaystyle{ |\{R: R X ... \X =X^n\}|=(2^{|X|})^n |X|}\)
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

andkom
Użytkownik
Użytkownik
Posty: 636
Rejestracja: 10 paź 2007, o 12:57
Płeć: Mężczyzna
Lokalizacja: Łódź
Pomógł: 350 razy

Liczba funkcji oraz relacji.

Post autor: andkom » 25 paź 2007, o 23:04

1. O.K.
2. Powinno raczej być
\(\displaystyle{ |\{R: R X Y\}|=2^{|Y|\cdot |X|}}\)
oraz
\(\displaystyle{ |\{R: R X ... \X =X^n\}|=2^{|X|^n}}\)

Awatar użytkownika
Emiel Regis
Gość Specjalny
Gość Specjalny
Posty: 1495
Rejestracja: 26 wrz 2005, o 17:01
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 71 razy
Pomógł: 225 razy

Liczba funkcji oraz relacji.

Post autor: Emiel Regis » 26 paź 2007, o 08:22

Tak czułem że coś źle robię bo znalazłem wynik w wikipedii i mi się nie zgodził... (choć zawsze jest nadzieja że u nich błąd: p )

Natomiast nie sam wynik a rozumowanie jest dla mnie ważniejsze, napisze jak sam to liczyłem na przykladzie X i Y dyskretnych. Mamy tak:
\(\displaystyle{ X=\{1, 2, ..., m\} \\ Y = \{1, 2, ..., n\}}\)

No to zajmijmy się liczbą relacji z X do Y.
\(\displaystyle{ |\{R: R X Y\}|=2^{|Y|} |X|}\)
Pierwszemu punktowi z X mogę przyporządkować wszystkie możliwe podzbiory ze zbioru Y, a tych jest mianowicie \(\displaystyle{ 2^n}\), z kolei wiedząc że w X punktów mam m to rozumuję że różnych relacji moge otrzymać \(\displaystyle{ m 2^n}\).

Kolejne:
\(\displaystyle{ |\{R: R X ... \X =X^n\}|=(2^{|X|})^n |X|}\)
Biorę sobie pierwszy punkt z X, mogę mu przyporządkować \(\displaystyle{ 2^m}\) punktów z kolejnego zbioru a także z każdego nastepnego czyli mam już możliwosci \(\displaystyle{ (2^m)^n}\), no i teraz podobnie, punktów w X mam m czyli wszystkich relacji mi wychodzi \(\displaystyle{ (2^m)^n m}\)

No i pytania:
1. Gdzie tu jest błąd?
2. Nawet gdyby powyższe rozumowanie było dobre to czy w ogóle mogę je przenieść na przypadek ciagły poprzez zastąpienie m i n mocami zbiorów X i Y...

(w pierwszym pytaniu z pierwszego postu liczyłem dokładnie na tej samej zasadzie wiec teraz nie wiem czy to przypadek że się zgodziło... Punktów w X jest m, każdemu mogę przypisać n punktów z Y, więc liczba funkcji to jest \(\displaystyle{ n^m}\))

andkom
Użytkownik
Użytkownik
Posty: 636
Rejestracja: 10 paź 2007, o 12:57
Płeć: Mężczyzna
Lokalizacja: Łódź
Pomógł: 350 razy

Liczba funkcji oraz relacji.

Post autor: andkom » 26 paź 2007, o 23:09

Drizzt pisze:No to zajmijmy się liczbą relacji z X do Y.
\(\displaystyle{ |\{R: R X Y\}|=2^{|Y|} |X|}\)
Pierwszemu punktowi z \(\displaystyle{ X}\) mogę przyporządkować wszystkie możliwe podzbiory ze zbioru \(\displaystyle{ Y}\), a tych jest mianowicie \(\displaystyle{ 2^n}\), z kolei wiedząc że w \(\displaystyle{ X}\) punktów mam \(\displaystyle{ m}\) to rozumuję że różnych relacji moge otrzymać \(\displaystyle{ m 2^n}\).
Relacja, to podzbiór produktu \(\displaystyle{ X\times Y}\). Produkt ten ma \(\displaystyle{ m\cdot n}\) elementów, a więc \(\displaystyle{ 2^{m\cdot n}}\) podzbiorów. I już. O żadnym przyporządkowywaniu punktom \(\displaystyle{ X}\) podzbiorów \(\displaystyle{ Y}\) nie trzeba mówić. Jeśli jednak koniecznie chcemy tak robić, to dostaniemy nie \(\displaystyle{ m\cdot2^n}\), lecz \(\displaystyle{ 2^n\cdot2^n\cdot\cdots\text{($m$ razy)}\cdots\cdot2^n\cdot2^n=(2^n)^m=2^{m\cdot n}}\)

Awatar użytkownika
Emiel Regis
Gość Specjalny
Gość Specjalny
Posty: 1495
Rejestracja: 26 wrz 2005, o 17:01
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 71 razy
Pomógł: 225 razy

Liczba funkcji oraz relacji.

Post autor: Emiel Regis » 27 paź 2007, o 01:31

No faktycznie! Od razu idzie. Dziekuje za pomoc.

ODPOWIEDZ