Ordinare gli interi: base $n$

[Pachisi]

Trovare il numero di interi positivi la cui scrittura in base $n$ è formata da interi distinti tale che, a parte il primo intero a sinistra, ogni intero ha come differenza $\pm1$ da qualche intero alla sua sinistra.

[Vincent46]

Ci provo.

Diciamo numeri buoni quelli che soddisfano la condizione richiesta. Un numero buono ha al più $n$ cifre. Inoltre, in ogni numero buono di $c$ cifre, devono comparire tutte e sole le cifre da $i$ a $i+c-1$, per qualche $i \in {0, ..., n-c}$; cioé nessuna cifra può essere "saltata".

Avendo a disposizione le cifre da $0$ a $n-1$, per ogni $c \in {1, ..., n}$ ci sono in tutto $n-c+1$ $c$-uple composte di $c$ cifre consecutive. Ognuna di tali $c$-uple può essere ordinata in maniera buona in $2^{c-1}$ modi, in base al risultato dell'ultimo esercizio che hai postato. Però dobbiamo ricordarci di escludere i riordinamenti buoni che cominciano per $0$. Ovviamente, per ogni $c$, c'è un solo riordinamento di tale tipo da escludere.

Quindi il numero che stiamo cercando è

\begin{align*}
\sum_{c=1}^{n}[(n-c+1)2^{c-1}-1] & = \sum_{c=0}^{n-1}[(n-c)2^{c}]-n
\end{align*}

Così su due piedi non mi viene in mente nessuna semplificazione ulteriore.

[Pachisi]

Ok
Per la somma

prova a dividerla:
$\sum_{c=1}^{n} n2^(c-1)-\sum_{c=1}^{n} (c-1)2^(c-1)-\sum_{c=1}^{n} 1 $.