un problema curioso

[Azarus]

delle permutazioni di n oggetti si scelgono quelle con la seguente proprietà :
<BR>
<BR>preso il k-esimo elemento della serie questo o è maggiore di tutti gli elementi precedenti o minore di tutti gli elementi precedenti.
<BR>
<BR>dato n determinare il numero di combinazioni di questo tipo.
<BR>
<BR>
<BR>ho trovato una soluzione molto semplice ma di cui non sono convinto al 100%.

[FrancescoVeneziano]

Consideriamo le permutazioni di n numeri, l’ultimo numero deve essere, o maggiore di tutti (n) o minore di tutti (1), nel primo caso, il numero di permutazioni che ci interessano sarà uguale alle permutazioni di (n-1) con la stessa proprietà; lo stesso vale per il secondo caso, dal momento che l’ordine è l’unica cosa che ci riguarda, e possiamo quindi rietichettare i numeri in modo da far corrispondere alle permutazioni dei numeri 2…n, quelle dei numeri 1…n-1, mantenendo l’ordine.
<BR>Quindi f(n+1)=2f(n)
<BR>E f(1)=1,
<BR>quindi f(n)=2^(n+1)
<BR>CaO (ossido di calcio)
<BR>

[DD]

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>quindi f(n)=2^(n+1)
<BR>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>f(n)=2^(n-1), direi

[FrancescoVeneziano]

Certamente, scusate <IMG SRC="images/splatt_forum/icons/icon_cool.gif">
<BR>CaO (ossido di calcio)