Permutazioni gentili (old imo)

[enomis_costa88]

Una permutazione $ \{x_1,\dots,x_{2n}\} $ dell'insieme $ \{1,2,\dots, 2n\} $ è chiamata gentile se $ |x_i-x_{i+1}|=n $ per almeno un $ i \in \{1,2,1\dots,2n\} $.

Dimostrare che le permutazioni gentili sono più della metà del totale.
Buon lavoro, Simone.

[piever]

Soluzione un po' brutale:
ci sono ovviamente $ n $ coppie di elementi tale che, se hanno indici consecutivi nella permutazione, la rendono gentile.
Posso prendere una coppia di questo tipo e metterla in modo tale che gli indici dei due elementi siano consecutivi e calcolare quante permutazioni ci sono con quella coppia in quella posizione, poi ripetere il lavoro con ogni coppia possibile in ogni posizione possibile. A quel punto avrò ottenuto tutte le permutazioni gentili contando n volte quelle che sono gentili per $ n $ distinti valori di $ i $. La coppia la posso scegliere in n modi, moltiplicato per $ 2n-1 $ posti validi moltiplicato per $ 2 $ (inverto l'ordine degli elementi nella coppia) moltiplicato per $ (2n-2)! $ cioè le possibili permutazioni dei restanti elementi. Il risultato è $ 2n! $
Ora posso fare lo stesso lavoro scegliendo inizialmente $ 2 $ coppie "gentili". Se sottraggo il risultato al risultato precedentemente ottenuto ottengo una volta le permutazioni gentili per un valore di $ i $, una volta le permutazioni gentili per $ 2 $ valori di $ i $, mentre tutte le altre permutazioni gentili non compaiono o sono sottratte. Quindi il numero che troverò sarà inferiore al numero di permutazioni gentili. Per scegliere le postazioni delle $ 2 $ coppie "gentili": la prima in $ 2n-1 $ modi; dopo che l'ho scelta ho escluso $ 3 $ possibilità per mettere la seconda, tranne nel caso in cui la prima coppia sia messa all'inizio o alla fine; ma in questo modo ogni coppia di postazioni la scelgo $ 2 $ volte per cui divido per $ 2 $. Quindi posso scegliere le postazioni in $ \frac {(2n-1)(2n-4)+2}{2}=\frac {(2n-2)(2n-3)}{2} $ modi.
A questo punto moltiplico per $ n(n-1) $ per scegliere le $ 2 $ coppie, poi per $ 4 $, per invertire gli elementi di ciascuna coppia, poi per $ (2n-4)! $ per ordinare i restanti elementi, il risultato è $ (2n-2)!*2n*(n-1) $
Se lo sottraggo al risultato precedentemente ottenuto ottengo $ (2n-2)!*2n^2 $ che è un numero inferiore al numero di permutazioni gentili e superiore alla metà delle permutazioni totali.
Ovviamente questo ragionamento ha senso solo con $ n \geq 2 $
Con $ n=1 $ si vede subito che tutte le permutazioni sono gentili.

[dario2994]

Riesumo questo vecchio post per piazzarci un bel bonus:
Bonus di trebisonda: Quante sono le permutazioni gentili?

[dario2994]

Up per il bonus... con hint, sia mai che attira qualcuno:

Testo nascosto:

Principio d'inclusione esclusione