OliForum Matematico

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 ?

?

No, già se prendi n=3 hai 2 permutazioni ...

?
(non so perché mi viene accavallato)

Yes adesso metti la tua dimostrazione

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$.

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.