[L03] I turchi mettono a soqquadro i numeri

[Gerald Lambeau]

Trovare il numero di $(a_1, a_2, \dots, a_{2016})$ permutazioni di $(1, 2, \dots, 2016)$ tali che, per tutti gli $1 \le i<j \le 2016$, $i+a_i \le j+a_j$.

[Ale99]

Sinceramente non so come io sia finito qua però già che ci siamo mettiamo un'idea a questo problema innocente e che mi sembra strano venga da una gara turca ...

Errata

[Gerald Lambeau]

Il risultato è sbagliato.

[Ale99]

Ok meglio se lo riguardo con calma ...

[Roob]

Sperando che sia giusto...
Chiamiamo [tex]P_n[/tex] il numero di suddette permutazioni per [tex]n[/tex] qualsiasi.
Osserviamo che per soddisfare la richiesta una qualsiasi permutazione deve avere che
[tex]a_i\leq a_{i+1} +1[/tex] (1)
che segue dalla richiesta sostituendo [tex]j=i+1[/tex]. Questa condizione è necessaria ma anche sufficiente, poiché fa sì che la [tex]n[/tex]-upla degli [tex]i+a_i[/tex] sia debolmente crescente, come richiesto.
Prendendo una qualunque permutazione adatta lunga [tex]n-1[/tex], possiamo ottenerne una lunga [tex]n[/tex] aggiungendo [tex]n[/tex] o alla fine o prima di [tex]n-1[/tex], altrimenti non soddisferemmo (1). Poiché con questo metodo otteniamo tutte le permutazioni lunghe [tex]n[/tex] senza prenderne nessuna 2 volte, e ad ognuna lunga [tex]n-1[/tex] ne abbiamo associate 2, si ha che
[tex]P_n=2P_{n-1}[/tex]
E poiché [tex]P_1=1[/tex], [tex]P_n=2^{n-1}[/tex]
E in particolare [tex]P_{2016}=2^{2015}[/tex]

[Gerald Lambeau]

Giusta!