Ilosc relacji na zbiorze n elementowym
Monika: Hej, mam takie zadanie:
Ile jest relacji spójnych na zbiorze n elementowym?
Relacja spójna: Dla dowolnego x,y ze zbioru na którym okreslona jest relacja, x jest w relacji
z y, lub y jest w relacji z x, lub x = y.
Ja zrobiłam to zadanie w taki sposób, że zauważyłem, kiedy relacja na pewno nie będzie spójna.
Będzie to wtedy, gdy na elementy na przekątnej (1,1) (2,2) itd. nie będą ze sobą w relacji,
oraz gdy dowolna inna para (x,y) oraz (y,x) nie będzie ze sobą w relacji.
Wyszło mi cos takiego: n
2 − n − (n(n−1)/2 −1) = (n
2−n−2)/2
To pierwsze n, to elementy z przekątnej, a druga częsc, to elementy nad przekątną − jeżeli
będzie chociaż jedna taka para elementów, że (x,y) oraz (y,x) nie są ze sobą w relacji, to
cała relacja nie będzie spójna.
Zatem od wszystkich możliwych musiałam odjąć jeden, bo bez tego mogłaby być sytuacja, że
wszystkie elementy nad przekątną są ze sobą w relacji i wtedy już nie ma znaczenia, co jest
pod.
Nie wiem czy dobrze to wytłumaczyłam ani czy to rozumowanie jest poprawne, chętnie posłucham
innych pomysłów na to zadanie.
Pozdrawiam
