Ile jest permutacji

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
valverde12345
Użytkownik
Użytkownik
Posty: 86
Rejestracja: 12 sty 2014, o 13:37
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 14 razy

Ile jest permutacji

Post autor: valverde12345 »

Zadanie: Niech \(\displaystyle{ n \ge ­ 3.}\) Ile jest permutacji π zbioru \(\displaystyle{ [n]}\) takich, że \(\displaystyle{ \pi(1) < \pi(2) < \pi(3)}\)

Wybieramy \(\displaystyle{ \pi(1)}\) na \(\displaystyle{ n-2}\) sposoby bo conajmniej 2 elementy muszą pozostać większe
Wybieramy \(\displaystyle{ \pi(2)}\) na \(\displaystyle{ n-2}\) sposoby bo 1 już wybraliśmy i conajmniej 1 element musi pozostać większy
Wybieramy \(\displaystyle{ \pi(3)}\) na \(\displaystyle{ n-2}\) sposoby bo 2 już wybraliśmy
Pozostałe wybieramy na \(\displaystyle{ (n-3)!}\) sposobów.

Ostatecznie mamy : \(\displaystyle{ (n-2) ^{3} \cdot (n-3)!}\)

Czy moje rozumowanie jest poprawne?

Zadanie 2: Ile jest surjekcji ze zbioru \(\displaystyle{ [5]}\) na zbiór \(\displaystyle{ [3]}\)?

Surjekcji z \(\displaystyle{ [n]}\) na \(\displaystyle{ [k]}\) jest \(\displaystyle{ k! \cdot S _{2} (n, k)}\)
Więc z \(\displaystyle{ [5]}\) na zbiór \(\displaystyle{ [3]}\) jest \(\displaystyle{ 3! \cdot S _{2} (5, 3) = 6 \cdot 25 = 150}\) Coś za dużo, się wydaje czyżby ta silnia była nadmiarowa w moim wzorze?

Zadanie 3: Ile jest odwzorowań monotonicznych ze zbioru \(\displaystyle{ [5]}\) w zbiór \(\displaystyle{ [10]}\)?

Tutaj już nie mam pomysłu..
Ostatnio zmieniony 17 cze 2015, o 13:37 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Awatar użytkownika
Medea 2
Użytkownik
Użytkownik
Posty: 2491
Rejestracja: 30 lis 2014, o 11:03
Płeć: Kobieta
Podziękował: 23 razy
Pomógł: 479 razy

Ile jest permutacji

Post autor: Medea 2 »

Pierwsze niestety źle. Co jeżeli \(\displaystyle{ n = 10}\), \(\displaystyle{ \pi(1) = 8}\)? Wtedy jestem zmuszona do określenia \(\displaystyle{ \pi(2) = 9}\), a Ty twierdzisz, że nadal mam osiem wyborów. Proponuję takie podejście do zadania: wybierz podzbiór \(\displaystyle{ [n]}\) o trzech elementach i "posortuj" go.

Jeżeli w zadaniu drugim \(\displaystyle{ S_2(5,3)}\) oznacza liczbę podziałów zbioru \(\displaystyle{ \{1,2,3,4,5\}}\) na trzy niepuste podzbiory i nie masz żadnego błędu rachunkowego, to wynik jest poprawny: żeby liczyć surjekcje wystarczy policzyć, na ile sposobów można "wybrać" przeciwobrazy. Całość mnoży się przez \(\displaystyle{ k!}\), bo elementy przeciwdziedziny są rozróżnialne.

Co do trzeciego: to akurat jest proste. Czy jeżeli podpowiem Ci, że dowolne przekształcenie monotoniczne jest jednoznacznie wyznaczone przez swój obraz, to będzie Ci łatwiej? Chyba, że masz na myśli przekształcenia słabo monotoniczne. Wtedy trzeba zastosować inne podejście.
ODPOWIEDZ