Permutazioni come prodotto di trasposizioni
Permutazioni come prodotto di trasposizioni
Salve a tutti, spero di non aver sbagliato sezione dove porre questa domanda:
se ogni permutazione può essere scritta come composizione di trasposizioni (in numero pari se la permutazione è pari e il contrario se è dispari),qual è il numero minimo di trasposizioni che occorrono per esprimere in questo modo la permutazione generica $\sigma$ ?
Sono riuscito solo a fare alcune considerazioni del tipo :
se ho una permutazione
$\sigma= \begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
3 & 2 & 1 & 5 & 4
\end{pmatrix}$
allora il numero di permutazioni $n$ sarà sicuramente minore o uguale al numero di elementi "fuori posto" ossia sicuramente in questo caso $n<4$ (dato che solo il 2 è al suo posto); Come procedere?
se ogni permutazione può essere scritta come composizione di trasposizioni (in numero pari se la permutazione è pari e il contrario se è dispari),qual è il numero minimo di trasposizioni che occorrono per esprimere in questo modo la permutazione generica $\sigma$ ?
Sono riuscito solo a fare alcune considerazioni del tipo :
se ho una permutazione
$\sigma= \begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
3 & 2 & 1 & 5 & 4
\end{pmatrix}$
allora il numero di permutazioni $n$ sarà sicuramente minore o uguale al numero di elementi "fuori posto" ossia sicuramente in questo caso $n<4$ (dato che solo il 2 è al suo posto); Come procedere?
Ultima modifica di gilgamesh il 17 gen 2014, 16:46, modificato 1 volta in totale.
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Re: Permutazioni come prodotto di trasposizioni
Se non erro, il numero di trasposizioni dovrebbe essere esattamente il numero di elementi fuori posto: prima di tutto divido la permutazione in cicli (piccola spiegazione di cos'è un ciclo: è un insieme di elementi $i_1...i_k$ scelti tra gli $n$ insiemi da permutare tali che $\sigma(i_1)=i_2, \sigma(i_2)=i_3... \sigma(i_k)=i_1$. Questo ciclo è di lunghezza $k$). Puoi scrivere la permutazione come unione di cicli disgiunti, e notare che per scrivere un ciclo di lunghezza $k$ servono $k$ trasposizioni; i cicli di lunghezza $1$ sono i punti fissi che non scrivi, quindi il numero di trasposizioni è proprio il numero di elementi fuori posto (spero si capisca la spiegazione ).
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
Re: Permutazioni come prodotto di trasposizioni
$\sigma= \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 \\
2 & 3 & 7 & 1 & 5 & 4 & 6
\end{pmatrix}$
Questa permutazione ha 6 elementi fuori posto, ma è chiaramente una permutazione dispari in quanto vi sono 7 inversioni. Inoltre si scrivere come prodotto di 5 trasposizioni. Quindi non è così, o sbaglio?
1 & 2 & 3 & 4 & 5 & 6 & 7 \\
2 & 3 & 7 & 1 & 5 & 4 & 6
\end{pmatrix}$
Questa permutazione ha 6 elementi fuori posto, ma è chiaramente una permutazione dispari in quanto vi sono 7 inversioni. Inoltre si scrivere come prodotto di 5 trasposizioni. Quindi non è così, o sbaglio?
- Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
Re: Permutazioni come prodotto di trasposizioni
Non dovrebbe essere il numero di elementi meno il numero di cicli? Forse mi ricordo male.
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Re: Permutazioni come prodotto di trasposizioni
Ok, si in effetti ora che ci penso una per una cosa del genere:gilgamesh ha scritto:$\sigma= \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 \\
2 & 3 & 7 & 1 & 5 & 4 & 6
\end{pmatrix}$
Questa permutazione ha 6 elementi fuori posto, ma è chiaramente una permutazione dispari in quanto vi sono 7 inversioni. Inoltre si scrivere come prodotto di 5 trasposizioni. Quindi non è così, o sbaglio?
$\sigma= \begin{pmatrix}
1 & 2 & 3 \\
2 & 3 & 1
\end{pmatrix}$
Bastano due trasposizioni invece di tre (cioé la terza segue dalle prime due), quindi se togli la trasposizione di troppo dovrebbe essere "elementi totali-punti fissi-# di cicli".
Poi non capisco a cosa tu ti stia riferendo alla prima parte con le permutazioni dispari e pari...cioè so cosa sono, ma non vedo come c'entrino.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
Re: Permutazioni come prodotto di trasposizioni
Appena ho qualche minuto verifico la formula.Comunque mi riferisco al fatto che essendoci 6 elementi fuori posto , se il numero di trasposizioni necessarie fosse pari a 6 (come affermavi precedentemente) ci sarebbe un assurdo in quanto , dato che il numero di inversioni è dispari, la permutazione è dispari e non può essere scritta come un prodotto di un numero pari di trasposizioni.
Re: Permutazioni come prodotto di trasposizioni
karlosson_sul_tetto ha scritto:Ok, si in effetti ora che ci penso una per una cosa del genere:gilgamesh ha scritto:$\sigma= \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 \\
2 & 3 & 7 & 1 & 5 & 4 & 6
\end{pmatrix}$
Questa permutazione ha 6 elementi fuori posto, ma è chiaramente una permutazione dispari in quanto vi sono 7 inversioni. Inoltre si scrivere come prodotto di 5 trasposizioni. Quindi non è così, o sbaglio?
$\sigma= \begin{pmatrix}
1 & 2 & 3 \\
2 & 3 & 1
\end{pmatrix}$
Bastano due trasposizioni invece di tre (cioé la terza segue dalle prime due), quindi se togli la trasposizione di troppo dovrebbe essere "elementi totali-punti fissi-# di cicli".
Poi non capisco a cosa tu ti stia riferendo alla prima parte con le permutazioni dispari e pari...cioè so cosa sono, ma non vedo come c'entrino.
Nel mio esempio io ho contato 2 cicli : $(4,1,2,3,7,6)$ e $ (5)$
si cui uno quindi è banale in quanto coincide con la permutazione identica. Per cui con questa formula "elementi totali-punti fissi-# di cicli" si ottiene $7-1-1$ (ho considerato il numero di cicli non banali). Dovrebbe andar bene?
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Re: Permutazioni come prodotto di trasposizioni
Si, come dice anche Troleito, puoi pure considerare i punti fissi come cicli di lunghezza 1 semplificandoti la vita.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
Re: Permutazioni come prodotto di trasposizioni
Che poi potrebbe anche andar bene a questo punto:
$p=\sum^{n}_{i=1} l_i -n $
dove $l_i=$ lunghezza del ciclo i-esimo, $n=$ numero di cicli non banali (con banali intendo permutazione identica), $p=$ numero di permutazioni cercato
$p=\sum^{n}_{i=1} l_i -n $
dove $l_i=$ lunghezza del ciclo i-esimo, $n=$ numero di cicli non banali (con banali intendo permutazione identica), $p=$ numero di permutazioni cercato
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Permutazioni come prodotto di trasposizioni
Piccola dimostrazione: scriviamo \(\sigma\) come prodotto di cicli, e sia \((a_1 \ \ \ldots \ \ a_k)\) un ciclo generico di \(\sigma\). Si riesce a realizzare \(n-\#cicli\) (come giustamente dicevate) con l'identità \( (a_1 \ldots a_k ) = (a_1\ \ a_2) (a_1\ \ a_3) \ldots (a_1\ \ a_k)\). D'altronde non si può far meglio, perchè:
1. gli elementi \(a,b\) di ogni trasposizione \((a b)\) devono appartenere allo stesso ciclo;
2. Ogni trasposizione assegna l'immagine \(b\) all'elemento \(a\) e viceversa; possiamo "non cambiare" l'immagine di \(b\), in ogni ciclo, una volta sola, altrimenti la permutazione non sarebbe bigettiva.
Non so se è chiara!
1. gli elementi \(a,b\) di ogni trasposizione \((a b)\) devono appartenere allo stesso ciclo;
2. Ogni trasposizione assegna l'immagine \(b\) all'elemento \(a\) e viceversa; possiamo "non cambiare" l'immagine di \(b\), in ogni ciclo, una volta sola, altrimenti la permutazione non sarebbe bigettiva.
Non so se è chiara!
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe