Surjekcja zbioru X na Y

[Honzik18]

Wyznaczyć liczbę surjekcji ze zbioru \(\displaystyle{ X =\{ 1; 2; 3; 4; 5; 6; 7 \}}\) na zbiór \(\displaystyle{ Y = \{1; 2; 3\}}\).

Czytałem teorię oraz patrzyłem rozwiązania surjekcji, ale nadal nie rozumiem. Mógł by ktoś rozjaśnić?

\(\displaystyle{ X \rightarrow Y}\)

[rafalpw]

Chodzi o to:

Ile będzie funkcji \(\displaystyle{ f:X \rightarrow Y}\) , których zbiorem wartości będzie cały zbiór \(\displaystyle{ Y}\) ?

[Honzik18]

Nie mam pojęcia, napisałem polecenie jakie jest w zadaniu.

[rafalpw]

Ojej, nie zrozumiałeś mnie.

Wyznaczyć liczbę surjekcji ze zbioru \(\displaystyle{ X =\{1; 2; 3; 4; 5; 6; 7\}}\) na zbiór \(\displaystyle{ Y = \{1; 2; 3\}}\) \(\displaystyle{ \Leftrightarrow}\) Wyznaczyć liczbę funkcji \(\displaystyle{ X \rightarrow Y}\) , których zbiorem wartości jest cały zbiór \(\displaystyle{ Y}\).

[Honzik18]

Dla każdego \(\displaystyle{ X}\) są 3 wartości \(\displaystyle{ Y}\) czyli \(\displaystyle{ 3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3= 3 ^{7}}\)

Takie coś?

[rafalpw]

Tak nie może być, bo wtedy dopuszczasz sytuację, w której zbiorem wartości jest tylko jedna liczba.

[Honzik18]

Hmm nie za bardzo rozumiem, \(\displaystyle{ 3 ^{7 \cdot 3}}\) ?

[rafalpw]

Najpierw wybierasz trzy liczby ze zbioru \(\displaystyle{ X}\) , którym się przyporządkuje trzy liczby ze zbioru \(\displaystyle{ Y}\) (trzeba uwzględnić wszystkie kombinacje), a pozostałe liczby ze zbioru \(\displaystyle{ X}\) można przyporządkować dowolnie.

[Honzik18]

Niestety nie rozumiem, jeszcze prowadzącego zapytam, może mi wytłumaczy -- 19 lut 2013, o 12:13 --Edit Czy może prawidłowa odpowiedź to 1806 surjekcji?

[Majeskas]

Do wyznaczenia liczby surjekcji ze zbioru skończonego w zbiór skończony korzysta się z zasady włączeń i wyłączeń. Oznaczmy:
\(\displaystyle{ A_n=\left\{f\in Y^X:\ n\notin f(X)\right\}}\)

Wówczas \(\displaystyle{ A_1\cup A_2\cup A_3}\) to zbiór wszystkich funkcji z \(\displaystyle{ X}\) w \(\displaystyle{ Y}\), które surjekcjami nie są.
Teraz korzystamy z zasady włączeń i wyłączeń:
\(\displaystyle{ |A_1\cup A_2\cup A_3|=|A_1|+|A_2|+|A_3|-|A_1\cap A_2|-|A_2\cap A_3|-|A_1\cap A_3|+|A_1\cap A_2\cap A_3|=3\cdot2^7-3}\)

Aby uzyskać liczbę wszystkich surjekcji, musimy odjąć wynik od liczby wszystkich funkcji z \(\displaystyle{ X}\) w \(\displaystyle{ Y}\).

\(\displaystyle{ 3^7-3\cdot2^7+3=1806}\)-- 7 grudnia 2013, 16:32 --

Najpierw wybierasz trzy liczby ze zbioru \(\displaystyle{ X}\) , którym się przyporządkuje trzy liczby ze zbioru \(\displaystyle{ Y}\) (trzeba uwzględnić wszystkie kombinacje), a pozostałe liczby ze zbioru \(\displaystyle{ X}\) można przyporządkować dowolnie.

Taki sposób liczenia nie zadziała. Sytuacje będą się powtarzać.

[arek1357]

Wzór na suriekcje:

\(\displaystyle{ \sum_{i=0}^{m}(-1)^i {m \choose i}(m-i)^n=1806}\)


gdzie:

\(\displaystyle{ n=7, m=3}\)