permutazioni - decomposizione unica in cicli disgiunti

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
bestiedda
Messaggi: 213
Iscritto il: 15 nov 2007, 20:20

permutazioni - decomposizione unica in cicli disgiunti

Messaggio 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
marco
Avatar utente
Ani-sama
Messaggi: 418
Iscritto il: 19 feb 2006, 21:38
Località: Piacenza
Contatta:

Messaggio 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. :)
...
bestiedda
Messaggi: 213
Iscritto il: 15 nov 2007, 20:20

Messaggio 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?
marco
Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio 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
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio 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...
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
bestiedda
Messaggi: 213
Iscritto il: 15 nov 2007, 20:20

Messaggio 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à?
marco
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

I cicli sono disgiunti, quindi la restrizione di f agli elementi di un suo ciclo coincide col ciclo stesso.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
Rispondi