Podzbiory, suriekcja oraz liczby Stirlinga

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
GypsyHatter
Użytkownik
Użytkownik
Posty: 21
Rejestracja: 26 lis 2015, o 17:22
Płeć: Mężczyzna
Podziękował: 3 razy

Podzbiory, suriekcja oraz liczby Stirlinga

Post autor: GypsyHatter »

Hej, mam takie zadanie i chciałbym wiedzieć czy dobrze je rozwiązałem.
Niech \(\displaystyle{ X = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}}\).
a) Oblicz liczbę wszystkich podzbiorów zbioru \(\displaystyle{ X}\), których liczba elementów przystaje do \(\displaystyle{ 1\pmod{3}}\).
b) Wyznacz liczbę surjekcji ze zbioru \(\displaystyle{ X}\) na jego podzbiór \(\displaystyle{ \{1, 2, 3, 4, 5, 6, 7, 8, 9\}}\), które sa funkcjami niemalejącymi.
c) Wyznacz liczbę wszystkich podziałów zbioru \(\displaystyle{ X}\) na \(\displaystyle{ 3}\) podzbiory. Przytocz odpowiednie wlasności rekurencji liczb Stirlinga II rodzaju.

\(\displaystyle{ a)\ {10 \choose 1} + {10 \choose 4} + {10 \choose 7} + {10 \choose 10} = 341\\
b)\ 2\\
c)\ 9330\\}\)


Czy w c) na egzaminie trzeba liczyć wszystko na piechotę?

--13.08.2017, 21:20--
Przepraszam za błąd w poleceniu, w podpunkcie b) miały być po prostu funckje niemalejące.
Ostatnio zmieniony 13 sie 2017, o 21:19 przez GypsyHatter, łącznie zmieniany 2 razy.
Kartezjusz
Użytkownik
Użytkownik
Posty: 7330
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 6 razy
Pomógł: 961 razy

Podzbiory, suriekcja oraz liczby Stirlinga

Post autor: Kartezjusz »

a) Dobrze
b) Mi na oko wygląda, że takich przyporządkowań nie ma, bo z racji, że nasze funkcje są niemalejącymi suriekcjami wynika,że muszą istnieć \(\displaystyle{ a,b \in \left\{ 1,2,3,4,5,6,7,8,9,10 \right\}}\), że \(\displaystyle{ f(a)=f(b)}\), co jest niemożliwe, bo funkcje muszą być ściśle malejące.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Podzbiory, suriekcja oraz liczby Stirlinga

Post autor: Premislav »

Kartezjusz, to, że funkcja nie jest niemalejąca, nie znaczy, że jest ona malejąca

Np. jeśli \(\displaystyle{ f(1)=f(10)=1, f(k)=k}\) dla \(\displaystyle{ k=2\ldots9}\), to \(\displaystyle{ f}\) jest funkcją o żądanych własnościach. Oczywiście jest to surjekcja, ponadto \(\displaystyle{ f(10)=1<f(9)=9}\), czyli \(\displaystyle{ f}\) nie jest niemalejąca.-- 13 sie 2017, o 20:10 --Moja sugestia co do rozwiązania b):
od liczby wszystkich surjekcji, na którą mamy znany wzór, odejmujemy liczbę niemalejących surjekcji.
A te policzyć można dość łatwo w tym przypadku. Taka surjekcja \(\displaystyle{ f}\) na zbiór jak w zadaniu ze zbioru jak w zadaniu musi spełniać \(\displaystyle{ f(x)=f(x+1)}\) dokładnie dla jednego \(\displaystyle{ x \in X, x \le 9}\) (bo mamy dziesięć argumentów, a dziewięć wartości).
ODPOWIEDZ