Permutazioni

Definizione Una permutazione su n oggetti é una funzione biunivoca p:{1,2,...,n}® {1,2,...,n} Il gruppo delle permutazioni su n oggetti (dove l'operazione é la composizione) viene denotato con Sn e si dice il gruppo simmetrico.

Proposizione Sn contiene n! elementi.

Dimostrazione Per definire p:{1,2,...,n}® {1,2,...,n} biunivoca ho a disposizione n scelte per p(1). Fatta questa scelta, rimangono (n-1) scelte per p(2). Fatte queste due scelte rimangono (n-2) scelte per p(3). Procedendo in questo modo ottengo alla fine n(n-1)(n-2)...1=n! possibilitá.

Esercizi

  1. In quanti modi diversi cinque ragazzi possono andare in discoteca indossando cinque giacche?
    Risposta: 5!=120
  2. In quanti modi si possono disporre i 25 alunni di una classe che contiene 25 sedie?
    Risposta: 25!=15511210043330985984000000
  3. In quanti modi si puó mescolare un mazzo di 40 carte?
    Risposta: 40!=815915283247897734345611269596115894272000000000
  4. In quanti modi diversi si possono disporre 8 torri sulla scacchiera in modo che nessuna possa mangiarne un'altra?
    Risposta: 8!=40320
  5. In quanti modi si puó mescolare un mazzo di 40 carte in modo che le prime 10 carte siano sempre di cuori?
    Risposta: 10!30!=962549577686478913579436212224000000000
  6. Qual é la probabilitá che mescolando 40 carte a caso le prime 10 siano di cuori?
    Risposta: [ 10!30!/40!] = [ 10/40][ 9/39]¼[ 1/31] @ 1,17*10-9
Definizione Uno scambio o trasposizione é una permutazione s Î Sn tale che esistono i,j Î {1,2,...,n},i ¹ j tali che
ì
ï
í
ï
î
s(i)=j
s(j)=i
s(k)=k
per k ¹ i,j

Proposizione Ogni permutazione si puó ottenere come composizione di scambi.

Dimostrazione (facoltativa, solo per chi non ritiene evidente la proposizione) Sia p una permutazione.

Se 1 ¹ p(1) considero lo scambio s1 tra 1 e p(1) (e 1 é andato a posto). Altrimenti pongo s1=1Sn.

Se s1(2) ¹ p(2) applico successivamente lo scambio s2 tra s1(2) e p(2) (e 1 e 2 sono andati a posto). Altrimenti pongo s2=1Sn.

Se s2s1(3) ¹ p(3) applico successivamente lo scambio s3 tra s2s1(3) e p(3) (e 1, 2 e 3 sono andati a posto). Altrimenti pongo s3=1Sn.

Continuando in questo modo sn....s1 coincide con p.

Teorema della paritá La paritá del numero di scambi (cioé il numero di scambi modulo 2) con cui si ottiene una permutazione dipende solo dalla permutazione stessa.

Per la dimostrazione del teorema precedente rimandiamo al corso di Algebra, dove le permutazioni verranno approfondite.

Definizione Una permutazione p si dice pari se il numero di scambi con cui si ottiene é pari ed il suo segno e(p) viene posto uguale a 1. Una permutazione p si dice dispari se il numero di scambi con cui si ottiene é dispari ed il suo segno e(p) viene posto uguale a -1.

Notiamo che e(p) é uguale a (-1) elevato al numero degli scambi con cui si ottiene p.

Le permutazioni pari sono [ n!/2] e formano un sottogruppo che si dice gruppo alterno e si denota con An. A5 ha ordine 60 ed ha una importanza storica notevole perché venne studiato da Galois nel suo lavoro intorno alla risolubilitá delle equazioni di quinto grado.



File translated from TEX by TTH, version 3.01.
On 16 Nov 2001, 19:36.