Ilość permutacji + pozycja w porządku lexykograficznym

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Ilość permutacji + pozycja w porządku lexykograficznym

Post autor: matinf »

Witam,

Oblicz ile jest permutacji \(\displaystyle{ \pi}\) elementów zbioru \(\displaystyle{ \left\{ 1,...6\right\}}\) takich, że jednocześnie \(\displaystyle{ |\pi(1) - 1| > 1}\) i \(\displaystyle{ \pi(2) - 2 > 1}\). Znajdź liczbę permutacji takich oraz pozycję w porządku leksykograficznym pierwszej takiej permutacji.
\(\displaystyle{ \pi < \sigma \Leftrightarrow \exists_{1\le i\le 6}\forall_{1\le j<i} \pi(j)=\sigma(j) \wedge \pi(i) < \sigma(i)}\)


Jeśli chodzi o ilość:
\(\displaystyle{ 3 *4! + 2 * 4! = 120}\)
Jeśli chodzi o pozycję:
najpierw policzyć te, które jaką pierwszą cyfrę mają jedynkę albo dwójkę, a potem jeszcze te, które mają na początku
\(\displaystyle{ 31}\) lub \(\displaystyle{ 32}\)
Ostatecznie:
\(\displaystyle{ 5!+5! + 4!+4! = 288}\)
Czyli odpowiedź to \(\displaystyle{ 289}\)

Dobrze to jest ?
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

Ilość permutacji + pozycja w porządku lexykograficznym

Post autor: Kartezjusz »

Celowo nie ma modułu w drugiej nierówności?
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Ilość permutacji + pozycja w porządku lexykograficznym

Post autor: matinf »

Kartezjusz pisze:Celowo nie ma modułu w drugiej nierówności?
Słuszne pytanie, bo przegapiłem tam moduł.

Ale zwróć uwagę na jedno. To bez znaczenia czy tam jest moduł czy nie.

Bo:

\(\displaystyle{ |\pi(2) - 2 | > 1 \Leftrightarrow \pi(2) > 3 \vee \pi(2) < 1}\)

Widać, że 2gie skrzydło alternatywy i tak nic nie wnosi.
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

Ilość permutacji + pozycja w porządku lexykograficznym

Post autor: Kartezjusz »

1.Pokaż jak liczyłeś. Moim zdaniem powinno być 2 razy więcej permutacji
2.Dobrze
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Ilość permutacji + pozycja w porządku lexykograficznym

Post autor: matinf »

1.Pokaż jak liczyłeś. Moim zdaniem powinno być 2 razy więcej permutacji
Ilość rzeczywiście źle wyszła, pokażę teraz jak liczę:

Na pierwszej pozycji musi \(\displaystyle{ 3, 4, 5, 6}\)
Na drugiej pozycji musi być \(\displaystyle{ 4, 5, 6}\)

Więc tak:
1szy przypadek jest taki:
na pierwszej pozycji stoi trójka:
Następnie na drugiej pozycji może stać \(\displaystyle{ 4}\), albo \(\displaystyle{ 5}\), albo \(\displaystyle{ 6}\). Na pozostałych pozycjach wszystko dozwolone:
Stąd : \(\displaystyle{ 1 * 3 * 4! = 72}\)

2gi przypadek:

Na pierwszej pozycji stoi coś większego niż trójka. Może tam coś stać na \(\displaystyle{ 3}\) sposoby. Wtedy na drugim miejscu jest tylko dwie możliwości. Na reszcie dowolność:
\(\displaystyle{ 3 * 2 * 4! = 144}\)

I sumując to dostajemy \(\displaystyle{ 144 + 72 = 216}\)

2.Dobrze
Dotyczy to pozycji \(\displaystyle{ 289}\) ?
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

Ilość permutacji + pozycja w porządku lexykograficznym

Post autor: Kartezjusz »

tak
ODPOWIEDZ