szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 13 cze 2015, o 22: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?
Góra
Mężczyzna Offline
PostNapisane: 13 cze 2015, o 22: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 18: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, z pewnym warunkiem  matinf  1
 permutacje - zadanie 4  Matka Chrzestna  7
 Permutacje zbioru [10]  patryk007  2
 permutacje, oblicz mozliwe ustawienia liczb  Cecylia  4
 zbiory permutacje kankan  lightinside  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl