liczba relacji

[theoldwest]

Zbiór \(\displaystyle{ A}\) liczy \(\displaystyle{ p}\) elementów (\(\displaystyle{ p \in \mathbb{N_+}}\)). Ile istnieje wszystkich relacji \(\displaystyle{ R,R \subseteq A \times A}\) o dziedzinie \(\displaystyle{ m}\)-elementowej i przeciwdziedzinie \(\displaystyle{ n}\)-elementowej, gdzie \(\displaystyle{ m,n}\) są ustalonymi liczbami spełniającymi założenia \(\displaystyle{ m,n \in \mathbb{N_+}; m \le p; n \le p}\)? Wiem, że każda taka relacja ma \(\displaystyle{ {p \choose m} \cdot {p \choose n}}\) elementów, ale nie wiem jak zliczyć ich ilość.

[octahedron]

Elementów jest \(\displaystyle{ m\cdot n}\), a to co napisałeś to właśnie ilość takich relacji.

[norwimaj]

Dziedzinę i przeciwdziedzinę można wybrać na \(\displaystyle{ \binom pm\cdot\binom pn}\) sposobów. Natomiast liczba takich relacji jest trudniejsza do policzenia. Próbowałeś wzoru włączeń i wyłączeń?

[theoldwest]

Tak, chodziło mi o wybór elementów dla przeciwdziedziny i dziedziny relacji, elementów będzie miała \(\displaystyle{ mn}\)*. Mam go, ale nie wiem jak to do zadania wciągnąć dlatego proszę o jakieś wskazówki. ... 5cze%C5%84

-- 3 mar 2013, o 22:10 --

Tak na oko to ta liczba będzie równa \(\displaystyle{ \binom pm\cdot\binom pn \cdot \sum}\) (razy jakaś tam sumka), ale nie wiem jak ją utworzyć

[norwimaj]

Załóżmy, że chcemy określić relację \(\displaystyle{ R\subseteq X\times Y}\), gdzie zbiór \(\displaystyle{ X}\) ma \(\displaystyle{ m}\) elementów, a zbiór \(\displaystyle{ Y}\) ma ich \(\displaystyle{ l}\). Wszystkich takich relacji jest \(\displaystyle{ 2^{ml}}\). A ile jest takich relacji, że każdy element zbioru \(\displaystyle{ X}\) jest w dziedzinie \(\displaystyle{ R}\)?

\(\displaystyle{ \left|B\setminus \bigcup_{i=1}^m B_i\right|,}\)

gdzie \(\displaystyle{ B}\) jest zbiorem wszystkich relacji, \(\displaystyle{ B_i}\) jest zbiorem takich relacji, że \(\displaystyle{ x_i\in X}\) nie należy do dziedziny. Myślę że ze wzoru włączeń i wyłączeń powinno to łatwo wyjść.

Jeśli to się uda, to potem trzeba będzie jeszcze zrobić tak, aby każdy element \(\displaystyle{ Y}\) należał do przeciwdziedziny.