Permutazioni e parità di cicli

[Tibor Gallai]

Mostrare che, tra tutte le permutazioni di 2n oggetti, quelle che si decompongono in cicli di lunghezze tutte pari sono tante quante quelle che si decompongono in cicli di lunghezze tutte dispari.

[Tibor Gallai]

Hint: mostrare che sono entrambe $ [(2n-1)!!]^2 $.

[io.gina93]

http://www.scienzematematiche.it/forum/ ... hp?f=8&t=8

[Tibor Gallai]

Sì, lo postai pure là perché qui era morto con disonore.
Però speravo che qualcuno provasse a risolverlo... Senza trovarsi il link alla soluzione.

[sasha™]

Che vuol dire "decomporre una permutazione in un ciclo di lunghezza pari/dispari"?

[Tibor Gallai]

Decomporre una permutazione in cicli di lunghezza pari o dispari.
Ovvero: una permutazione è esprimibile come prodotto di cicli disgiunti, in modo unico (esattamente come un intero è prodotto di numeri primi). In generale la somma delle lunghezze dei cicli di una permutazione di n elementi è n, ma i cicli possono avere qualsiasi lunghezza.
Tu vuoi contare le permutazioni che si decompongono in cicli di lunghezze tutte pari, e mostrare che sono tante quante quelle che si decompongono in cicli di lunghezze tutte dispari.

Vedi qui per sapere di più su permutazioni e cicli:
http://en.wikipedia.org/wiki/Cycle_notation
Vedi anche qui per un metodo operativo per calcolare i cicli di una permutazione:
viewtopic.php?t=14960

[sasha™]

Uhm, se non ho capito male un ciclo è una serie di permutazioni (bé, sempre la stessa) di elementi all'interno di una n-upla, finché un elemento non torna alla posizione iniziale.
Se sono tornati tutti alla posizione iniziale, bene, altrimenti rifaccio la stessa cosa finché non torna al suo posto almeno un altro elemento, e così ho un secondo ciclo.
Ripeto il tutto fino a che non sono tutti disposti secondo l'ordine iniziale, e la permutazione che ho applicato si può ottenere come "prodotto" di quei cicli, o sbaglio?
E la lunghezza di un ciclo è il numero di volte che devo ripetere la permutazione prima che l'elemento al quale la sto applicando torni al suo posto, no?

[Tibor Gallai]

Uhm, se non ho capito male un ciclo è una serie di permutazioni (bé, sempre la stessa) di elementi all'interno di una n-upla, finché un elemento non torna alla posizione iniziale.

No, un ciclo è UNA permutazione, che prende k elementi e li permuta ciclicamente secondo qualche ordine. Quindi il periodo di un ciclo di k elementi è k. Il periodo del prodotto di cicli disguinti è il minimo comune multiplo dei singoli periodi.
Nota che qui non ci interessano i periodi vari, ma solo le lunghezze dei cicli.

Esempio con n=2.

Permutazioni con solo cicli di lunghezza pari, scritte in cycle notation:

(12)(34)
(13)(24)
(14)(23)
(1234)
(1243)
(1324)
(1342)
(1423)
(1432)

Totale: 9.

Permutazioni con solo cicli di lunghezza dispari, scritte in cycle notation (per chiarezza non ometto i cicli unari):

(1)(2)(3)(4)
(1)(234)
(1)(243)
(134)(2)
(143)(2)
(124)(3)
(142)(3)
(123)(4)
(132)(4)

Totale: 9.

[io.gina93]

Sì, lo postai pure là perché qui era morto con disonore.
Però speravo che qualcuno provasse a risolverlo... Senza trovarsi il link alla soluzione.

io il link l'ho trovato per caso..
E cmq non ci sarei mai arrivata...
bhe ho capito che ho molte cose da imparare..

[Tibor Gallai]

Sìsì, ma non ti preoccupare! LOL.
Occhio che l'ultimo messaggio di quel thread (la soluzione senza funzioni generatrici) contiene un errore.

[EvaristeG]

Uhm ma se (non leggetelo, se state cercando la soluzione, perché [i) potrebbe essere un hint e] ii) potrebbe essere sbagliato)

(ab)(cd)--->(abc)(d) e così via a coppie

?

[Tibor Gallai]

Come ottieni ad esempio (1)(2)(3)(4)?

[EvaristeG]

hmm ok, rettifico:

(abc)(def)-->(abcf)(de) con a>b>c, d>e>f, a>d in questo modo dovrebbe essere iniettiva

[Tibor Gallai]

E se b<c, etc?
Non sono sicuro di aver capito cosa fa la funzione in tutti i casi.

[EvaristeG]

Diciamo che l'unica condizione che mi serve è a>d.
Posso scrivere ogni permutazione in modo unico con cicli in cui il primo elemento è il più grande, ordinati secondo il loro primo (quindi più grande) elemento, in modo decrescente. E questo modo di farlo è unico.

EDIT: corretta una cazzata.