Pagina 1 di 1

permutazioni - decomposizione unica in cicli disgiunti

Inviato: 29 mag 2010, 08:41
da bestiedda
buongiorno a tutti - non l'ho postata in combinatoria perchè credo che sia veramente elementare

dimostrare che ogni permutazione è ottenibile come composizione di cicli disgiunti, e tale composizione è unica a meno dell'ordine

Inviato: 29 mag 2010, 11:56
da Ani-sama
È elementare? :shock:

Forse mi son perso qualcosa, ma la prima (e unica) volta che ho visto dimostrato questo fatto è stato nel corso di Algebra del primo anno di università. C'è anche sul ben noto Herstein, comunque. :)

Inviato: 29 mag 2010, 12:17
da bestiedda
ed in effetti sono al primo anno dell'università :wink: il nostro prof ce l'ha lasciata per esercizio (simpatico, vero?) e la dimostrazione che sono riuscito a produrre è molto contorta....posso trovare in rete questo Herstein?

Inviato: 29 mag 2010, 12:30
da Carlein
Ani-sama ha scritto:È elementare? :shock:

Forse mi son perso qualcosa, ma la prima (e unica) volta che ho visto dimostrato questo fatto è stato nel corso di Algebra del primo anno di università. C'è anche sul ben noto Herstein, comunque. :)
Dai questo mica significa che non può essere elementare,difatti al corso di Algebra1 di solito dimostrano tante cose che sono di fatto elementari;questa in effetti direi che è ampiamente elementare. Magari bestiedda aspetta un pò a vedere se qualche liceale lo prende come esercizio e te lo fa, poi quando ti sei stufato magari posta la tua che probabilmente ,se è giusta, si semplificherà in qualcosa di semplice.
Ciaociao

Inviato: 29 mag 2010, 13:37
da Tibor Gallai
E' un fatto elementare in modo talmente limpido e chiaro che non mi capacito di come possa comparire la parola "algebra" come prima risposta.

Fissa una permutazione f di {1,...,n}. 1 va in f(1), che va in f(f(1)), che va in f(f(f(1))), etc etc. Ad ogni salto troverai sempre un elemento distinto dai precedenti, per iniettività, finché ritornerai in 1. E questo è il primo ciclo. Rimane fuori qualche elemento? Se sì, ripeti, ed ottieni gli altri cicli. Sono disgiunti? Sì, per iniettività. La scomposizione è unica a meno dell'ordine? Ma per favore... Veramente?? No, guarda...

Inviato: 30 mag 2010, 09:42
da bestiedda
Tibor Gallai ha scritto:E' un fatto elementare in modo talmente limpido e chiaro che non mi capacito di come possa comparire la parola "algebra" come prima risposta.

Fissa una permutazione f di {1,...,n}. 1 va in f(1), che va in f(f(1)), che va in f(f(f(1))), etc etc. Ad ogni salto troverai sempre un elemento distinto dai precedenti, per iniettività, finché ritornerai in 1. E questo è il primo ciclo. Rimane fuori qualche elemento? Se sì, ripeti, ed ottieni gli altri cicli. Sono disgiunti? Sì, per iniettività. La scomposizione è unica a meno dell'ordine? Ma per favore... Veramente?? No, guarda...
espliciteresti la parte sull'unicità?

Inviato: 30 mag 2010, 11:06
da Tibor Gallai
I cicli sono disgiunti, quindi la restrizione di f agli elementi di un suo ciclo coincide col ciclo stesso.