Witam,
Oblicz ile jest permutacji zbioru \(\left\{ 1,2,3,4,5\right\}\)t.że
\(\sigma(i)\) jest względnie pierwsza z \(i\) dla \(i=1,2,3,4,5\)
Przede wszystkim. Co oznacza ten symbol sigmy ? Może ktoś pod spojlerem ukryć wskazówkę ?
Obliczyć ilość permutacji
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
Panko
- Fachowiec
- Posty: 2946
- Rejestracja: 20 gru 2013, 21:41
- Lokalizacja: Radom
- Otrzymane podziękowania: 1556 razy
- Płeć:
Re: Obliczyć ilość permutacji
Sprytnie nie potrafię tego policzyć.
Dobra permutacja to taka , \(\\) \(\forall\)\(\\)\(i \in \left\{ 1,2,3,4,5\right\}\) \(\\)\(( \sigma(i),i))=1\).
Przykład dobrej permutacji : \({1\ 2\ 3\ 4\ 5\choose1\ 3\ 2\ 5\ 4}\) czyli \(\sigma(1)=1, \sigma(2)=3,\sigma(3)=2,\sigma(4)=5,\sigma(5)=4\).
......................................................................
Permutacja jest dobra \(\iff\)\(\\)\(\sigma(1) \in \left\{ 1,2,3,4,5\right\} \wedge \sigma(2) \in \left\{ 1,3,5\right\} \wedge \sigma(3) \in \left\{ 1,2,4,5\right\} \wedge \sigma(4)= \left\{ 1,3,5\right\} \wedge \sigma(5) \in \left\{1,2,3,4 \right\}\).
.....................................................................
Można więc wprost narysować 5-ć drzew przyjmując kolejno \(\sigma(1) \in \left\{ 1,2,3,4,5\right\}\)
Przykładowo dla \(\sigma(1)=1\) drzewko daje \(6\) dobrych permutacji.
Przykładowo dla \(\sigma(1)=2\) drzewko daje \(8\) dobrych permutacji.
Narysowanie tych pięciu drzewek to czas \(5\) minut.
I przynajmniej wiemy dokładnie ile jest tych dobrych permutacji.
Dobra permutacja to taka , \(\\) \(\forall\)\(\\)\(i \in \left\{ 1,2,3,4,5\right\}\) \(\\)\(( \sigma(i),i))=1\).
Przykład dobrej permutacji : \({1\ 2\ 3\ 4\ 5\choose1\ 3\ 2\ 5\ 4}\) czyli \(\sigma(1)=1, \sigma(2)=3,\sigma(3)=2,\sigma(4)=5,\sigma(5)=4\).
......................................................................
Permutacja jest dobra \(\iff\)\(\\)\(\sigma(1) \in \left\{ 1,2,3,4,5\right\} \wedge \sigma(2) \in \left\{ 1,3,5\right\} \wedge \sigma(3) \in \left\{ 1,2,4,5\right\} \wedge \sigma(4)= \left\{ 1,3,5\right\} \wedge \sigma(5) \in \left\{1,2,3,4 \right\}\).
.....................................................................
Można więc wprost narysować 5-ć drzew przyjmując kolejno \(\sigma(1) \in \left\{ 1,2,3,4,5\right\}\)
Przykładowo dla \(\sigma(1)=1\) drzewko daje \(6\) dobrych permutacji.
Przykładowo dla \(\sigma(1)=2\) drzewko daje \(8\) dobrych permutacji.
Narysowanie tych pięciu drzewek to czas \(5\) minut.
I przynajmniej wiemy dokładnie ile jest tych dobrych permutacji.
-
tukan
- Fachowiec
- Posty: 985
- Rejestracja: 18 paź 2010, 20:45
- Podziękowania: 509 razy
- Otrzymane podziękowania: 4 razy
- Płeć:
Ok, to fajny pomysł.
Policzyłem Twoimi drzewkami, wychodzi 28.
......................................................................
Aczkolwiek ten wynik można uzyskać szybciej:
Zliczamy nieporządki: 44
Do nich musimy doliczyć/odliczyć niewiele sytuacji:
Musimy odjąć przypadki następujących nieporządków:
\(\sigma(2) = 4 \vee \sigma(4) = 2\)
\(=20\)
Oraz dodać nieporządki:
\(\sigma(1) = 1\)
\(= 4\)
\(44 - 20 + 4 = 28\)
I tym sposobem z racji charakteru zliczania mamy szybciej wynik.
..........................................................................
Można by Twój sposób jeszcze przyspieszyć, zauważając, że pokryją nam się ilościowo przypadki zliczania, a wtedy to już wynik dostaniemy ultra szybko.
Policzyłem Twoimi drzewkami, wychodzi 28.
......................................................................
Aczkolwiek ten wynik można uzyskać szybciej:
Zliczamy nieporządki: 44
Do nich musimy doliczyć/odliczyć niewiele sytuacji:
Musimy odjąć przypadki następujących nieporządków:
\(\sigma(2) = 4 \vee \sigma(4) = 2\)
\(=20\)
Oraz dodać nieporządki:
\(\sigma(1) = 1\)
\(= 4\)
\(44 - 20 + 4 = 28\)
I tym sposobem z racji charakteru zliczania mamy szybciej wynik.
..........................................................................
Można by Twój sposób jeszcze przyspieszyć, zauważając, że pokryją nam się ilościowo przypadki zliczania, a wtedy to już wynik dostaniemy ultra szybko.