szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 13 cze 2015, o 23:14 
Użytkownik

Posty: 16
Lokalizacja: Koszalin
Takie zadanko: ile jest permutacji zbioru \left\{  1,...,n \right\} o 3 inwersjach?

Doszłam do tego że nie mniej niż dla zbioru \left\{1,...,n-1\right\} (bo można nową liczbę dopisać na koniec i inwersji będzie tyle samo) i nie więcej niż \frac{n!}{2} bo nieparzyste, ale znaleźć jakiegoś konkretnego schematu nie potrafie, do tego sprawdzanie ręczne juz przy n=5 robi się dość rozległe. Jakieś pomysły?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 13 cze 2015, o 23:52 
Użytkownik

Posty: 1390
Lokalizacja: Poznań
W jaki sposób można utworzyć inwersję w permutacji takiego zbioru? Ano tylko poprzez przesunięcie k-tego elementu o jedno miejsce w lewo.. W ten sposób elementy a_{k-1} oraz a_k utworzą inwersję.. Zauważmy dodatkowo, że przesunięcie danej liczby w ciągu o 2 miejsca w lewo utworzy nam dwie inwersje, a przesunięcie o 3 miejsca w lewo trzy inwersje..

Jak mogę zatem utworzyć 3 inwersje w takim zbiorze?
Mam 3 możliiwości:
1 - przesunięcie jednego elementu o 3 miejsca w lewo - mogę to zrobić na n-3 sposobów gdyż wyrazów 1, 2 i 3 nie mogę przesunąć aż o tyle miejsce w lewo.

2 - przesunięcie k-tego elementu o 2 miejsca w lewo i przesunięcie innego elementu o 1 miejsce w lewo..
Wybieram element do przesunięcia o 2 miejsca na n-2 sposobów, następnie wybieram element do przesunięcia o 1 miejsce na n-1 sposobów.. Muszę jednak pamiętać, że nie mogę przesunąć w lewo elementu a_{k-1} gdyż w ten sposób zamiast zyskać stracę jedną inwersję. Mam zatem n-2 wyborów na drugi element. Łącznie jest ich (n-2)^2

3 - przesunięcie trzech różnych elementów o 1 miejsce w lewo.. Robię to na (n-1)(n-2)(n-3) sposobów..

Posumować i powinno być ok.
Góra
Kobieta Offline
PostNapisane: 14 cze 2015, o 19:18 
Użytkownik

Posty: 16
Lokalizacja: Koszalin
W 3 punkcie podzielić to wszystko przez 6, tak mi się wydaje. Wtedy tych inwersji wychodzi \frac{n(n^2-7)}{6} co by się zgadzało, dzięki.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Permutacje miejsca  wektorek  3
 Permutacje - składniki sumy wyznacznika.  Venly  0
 Kombinatoryka, Permutacje, Lancuch Markowa  mki01  0
 permutacje zbioru - zadanie 2  21mat  1
 Permutacje - bieg na orientacje  zanstaszek9  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl