Ordinare gli interi

[Pachisi]

In quanti modi possiamo ordinare gli interi da $1$ a $n$ tale che, a parte il primo intero a sinistra, ogni intero ha come differenza $1$ da qualche intero alla sua sinistra.

[Erasmus_First]

Cosa intendi con: «n ha differenza 1 da m»?
Intendi $n - m = 1$ (cioè $n = m+1$) o invece $!n - m| = 1$ (cioè $n = m+1$ ∨ $m = n+1$ ?
Nel primo caso, ad occhio, mi parrebbe 2(n-1) modi.
Per esempio, per n = 5:
1) [1, 2, 3, 4, 5]; 2) [2, 1, 3, 4, 5];
3) [1, 5, 2, 3, 4]; 4) [5, 1, 2, 3, 4];
5) [1, 4, 5, 2, 3]; 6) [4, 1, 5, 2, 3]
7) [1, 3, 4, 5, 2]; 8) [3, 1, 4, 5, 2].
Ma in questi tipi di quiz non sono affatto bravo.

________

[Vincent46]

consideriamo un ordinamento dei primi $n$ numeri che soddisfi la condizione richiesta. supponiamo che il primo numero sia $m$. se ora, nella sequenza, guardiamo solo i numeri strettamente maggiori di $m$, è chiaro che questi devono comparire in ordine crescente (ad esempio non può comparire $m+2$ se alla sua sinistra non si trova $m+1$). invece i numeri minori di $m$ devono comparire in ordine decrescente. d'altra parte tutti gli ordinamenti di questo tipo soddisfano le richieste del problema. dunque i modi di ordinare i primi $n$ numeri, dato che il primo numero della sequenza è $m$, sono i modi di scegliere le posizioni degli $m-1$ numeri ${0, 1, ... , m-1}$ fra le $n-1$ posizioni possibili, cioé $((n-1),(m-1))$.

Dunque il numero totale di sequenze buone è

$\sum_{m=1}^{n} ((n-1),(m-1)) = 2^{n-1}$

[Pachisi]

@Erasmus_First: intendo la seconda.
@Vincent46: