Quante permutazioni?
Quante permutazioni?
Sia $ \sigma = (a_1, a_2,\cdots , a_n) $ una permutazione di (1,2,...,n) . Una coppia $ (a_i, a_j) $ corrisponde ad un'inversione di $\sigma$ se i<j ma $ a_i>a_j $ . Quante permutazioni di (1,2,...,n) con n>2 hanno esattamente 2 inversioni ?
-
zeitgeist505
- Messaggi: 96
- Iscritto il: 26 feb 2012, 18:49
Re: Quante permutazioni?
Testo nascosto:
Re: Quante permutazioni?
No, già se prendi n=3 hai 2 permutazioni ...
Re: Quante permutazioni?
Testo nascosto:
(non so perché mi viene accavallato)
Re: Quante permutazioni?
Yes 
adesso metti la tua dimostrazione
adesso metti la tua dimostrazioneRe: Quante permutazioni?
Chiamo $f(n)$ il numero di permutazioni con due inversioni con un insieme di cardinalità $n$. (dobbiamo trovare $f(n)$)
Divido in casi a seconda di come si comporta l'ultimo termine.
1) Resta fermo dove sta. Allora né crea né infastidisce le inversioni tra le altre coppie. Abbiamo $f(n-1)$ permutazioni buone.
2) Lo mettiamo come terzultimo elemento. Per avere esattamente 2 inversioni tutti gli altri elementi devono stare in ordine, altrimenti ne creeremmo in più. Quindi una sola permutazione che va bene.
3) Lo mettiamo in penultima posizione. Esso crea già esattamente un'inversione (con quello che mettiamo per ultimo). Ne manca esattamente solo un'altra, il che si può ottenere solo invertendo due termini adiacenti qualsiasi della sequenza considerata senza il termine $a_n$. Questa coppia da invertire si sceglie in $n-2$ modi. Ad ognuna di queste scelte corrisponde una e una sola permutazione buona.
4) Se lo mettiamo in posizioni precedenti alla terzultima otteniamo almeno 3 inversioni: abbiamo 0 ulteriori permutazioni buone.
Abbiamo esaminato tutti i casi. Sommando: $f(n)=f(n-1)+n-1=f(n-2)+(n-2)+(n-1)=...=f(3)+3+4+...+(n-1)=2+3+4+...+(n-1)$
Che è la somma dei primi $n-1$ interi positivi, a cui si sottrae $1$.
Divido in casi a seconda di come si comporta l'ultimo termine.
1) Resta fermo dove sta. Allora né crea né infastidisce le inversioni tra le altre coppie. Abbiamo $f(n-1)$ permutazioni buone.
2) Lo mettiamo come terzultimo elemento. Per avere esattamente 2 inversioni tutti gli altri elementi devono stare in ordine, altrimenti ne creeremmo in più. Quindi una sola permutazione che va bene.
3) Lo mettiamo in penultima posizione. Esso crea già esattamente un'inversione (con quello che mettiamo per ultimo). Ne manca esattamente solo un'altra, il che si può ottenere solo invertendo due termini adiacenti qualsiasi della sequenza considerata senza il termine $a_n$. Questa coppia da invertire si sceglie in $n-2$ modi. Ad ognuna di queste scelte corrisponde una e una sola permutazione buona.
4) Se lo mettiamo in posizioni precedenti alla terzultima otteniamo almeno 3 inversioni: abbiamo 0 ulteriori permutazioni buone.
Abbiamo esaminato tutti i casi. Sommando: $f(n)=f(n-1)+n-1=f(n-2)+(n-2)+(n-1)=...=f(3)+3+4+...+(n-1)=2+3+4+...+(n-1)$
Che è la somma dei primi $n-1$ interi positivi, a cui si sottrae $1$.
Re: Quante permutazioni?
Right 
Io l'avevo fatto dicendo che esattamente due permutazioni si possono ottenere in due modi:
- invertendo due coppie disgiunte;
- considerando un sottoinsieme di 3 elementi e invertendo in uno dei due modi:
- l'ultimo in prima posizione , il primo in seconda e il secondo in terza;
-il secondo in prima posizione il terzo in seconda posizione e il primo in ultima.
Nel primo caso abbiamo (n-3)*(n-2)/2 e nel secondo caso 2(n-2) modi , sommando si ottengono $ \frac{(n-2)(n+1)}{2} $ permutazioni.
Io l'avevo fatto dicendo che esattamente due permutazioni si possono ottenere in due modi:
- invertendo due coppie disgiunte;
- considerando un sottoinsieme di 3 elementi e invertendo in uno dei due modi:
- l'ultimo in prima posizione , il primo in seconda e il secondo in terza;
-il secondo in prima posizione il terzo in seconda posizione e il primo in ultima.
Nel primo caso abbiamo (n-3)*(n-2)/2 e nel secondo caso 2(n-2) modi , sommando si ottengono $ \frac{(n-2)(n+1)}{2} $ permutazioni.