OliForum Matematico

Come si risolve senza un milione di conti questo problema?


"Un capoufficio mette nell'ordine su un tavolo cinque fogli, ognuno con una lettera. Le lettere nell'ordine sono A, B, C, D, E. [in questo modo se nessuno toccasse i fogli, alla fine la lettera sopra la pila sarebbe la E, sotto ci sarebbe la D...]. La sua segretaria prende il foglio in cima alla pila e lo toglie ogni volta che ha tempo. In quanti modi può prendere i fogli la segretaria del capofficio?"

Generalizziamo il problema a n lettere $ \{a_1,a_2,\dots,a_n\} $.
Sia $ f(n) $ la risposta al quesito con n lettere.

Sia $ g(n,k) $ il numero di configurazioni di n lettere che inizino con a_k.
Definisco come $ g(n,0)=0 $

Suppongo che la prima lettera presa dalla segretaria sia $ a_{k+1} $.
In questa situazione mi rimangono ordinatamente le prime k lettere sul tavolo e il capoufficio potrà eventualmente portare altre (al massimo altre $ n+1-(k+1) $) lettere.
Ma questa è esattamente la situazione che si viene a creare in una qualsiasi configurazione di n lettere iniziante con $ a_i $ (con i che va da k a n).

Quindi: $ g(n+1,k+1)=\sum_{i=k}^n g(n,i) $

Da cui facilmente: $ g(n+1,1)= g(n+1,2)=f(n) $
$ g(n+1,n+1)=1 $
$ g(n+1,n)=n $

$ f(2)=2;g(2,1)=1=g(2,2) $
$ f(3)=2g(3,1)+g(3,3)=1+2+2 $
$ f(4)=f(3)+f(3)+3+1=14 $
$ f(5)=f(4)+f(4)+4+1+g(5,3) $ $ =g(4,2)+g(4,3)+g(4,4)+28+5 = $ $ 1+3+f(3)+28+5 = 4+38 =42 $.