Newsgroup: it.hobby.enigmi
Titolo: La Segretaria

 (Evitare la forza bruta perche' non e' necessaria)
Bel problema!
Avevamo già trattato segretarie e lettere, ma questo non lo conoscevo.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
42
Non ho trovato di meglio che compilare una tabella delle possibili
situazioni, dopo ogni lettera impilata.
inevase |
      5 | ordini
      4 | possibili        1
      3 |              1   4
      2 |          1   3   9
      1 |      1   2   5  14
      0 |  1   1   2   5  14  42
________|________________________
impilate   0   1   2   3   4   5
I numeri di ogni colonna sono la somma dei termini che nella colonna
precedente occupano un livello maggiore, uguale o inferiore di uno rispetto
a quello che stiamo considerando. Per esempio, il 9 della quarta colonna è
somma dei tre termini superiori della terza. Questo perché in ogni momento
possiamo scegliere se lasciare inevasa la lettera appena impilata (e le
inevase aumentano di 1), evadere solo quella (stesso numero di inevase)
oppure evaderla assieme ad una o più di quelle nella pila (le inevase
diminuiscono).
Spero si capisca, in pratica si tratta di collegare ogni numero della
tabella con quelli raggiungibili della colonna successiva (quindi con archi
che al massimo salgono di uno). I numeri della tabella contano i diversi
percorsi che arrivano ad ogni nodo. la tabella si può espandere a
piacimento; dopo aver impilato l'ultima lettera ovviamente dobbiamo evaderle
tutte.
Non sono riuscito a trovare una formula chiusa per f(n) = numero di ordini
possibili con n lettere, ma ho trovato la funzione ricorsiva:
f(1) = 1
f(n+1) = ((4n+2)/(n+2)) * f(n)
Ciao, Silv:o)

 In quanti ordinamenti diversi possono essere battute le 5 lettere?
Come ho fatto a non riconoscerli subito! sono i numeri di Catalan.
Compaiono in un'infinita di problemi del tutto equivalenti a questo.
Per esempio:
a) in qunati modi possibili 2n persone sedute attorno ad un tavolo rotondo
possono stringersi le mani senza incrociarsi?
b) in quanti modi possibili posso formare dei grafici di borsa con n tratti
ascendenti ed n discendenti?
c) in quanti modi posso sezionare in triangoli un poligono di n lati, usando
solo i vertici del poligono?
d) in quanti modi posso scrivere una stringa con n coppie di parentesi in
modo da rispettare la sintassi?
e) quanti risultati diversi puň dare una torre di potenze a^b^c^.. al
variare dell'ordine degli elevamenti?
ed altri che adesso non ricordo, come dimostrano Guy e Conway nel "libro dei
Numeri" riducendo uno all'altro i vari problemi.
I numeri di Catalan hanno a che fare con Pascal. In che modo?
Silv:o)

 f(n+1) = ((4n+2)/(n+2)) * f(n)
Ehila' hai riscoperto i numeri Catalani trovati da Eulero.
Eulero diede: 2*6*10*...*(4n-10) / (n-1)!
Questi numeri (Sloane 577) saltano fuori spesso in problemi
apparentemente differenti, Nel 1976 un certo Goult ha dato riferimenti
su 450 problemi.
E' interessante modificare leggermente la tua tabellina in questo modo:
1
1  1
1  2  2
1  3  5  5
1  4  9 14 14
1  5 14 28 42  42
1  6 20 48 90 132
.........
Dove ogni termine e' la somma "sopra+sinistra" e da' i numeri di
percorsi possibili per una torre che viaggia tra due angoli opposti di
una scacchiera a scalini.  
Sei un preveggente ?
Ho visto la tua risposta, ma non l'enunciato di Massimo.
:) dario

secondo me i modi sono 120 ( se ho capito bene la domanda)!
l'ordine io l'ho dalle disposizioni che sono date da un semplice fattoriale!
se n = 5 allora le disposizioni sono n! cioč 5! cioč 5*4*3*2*1 = 120
Se non č cosě allora non ho capito la domanda.
Ciao ciao!
-- 
Posted from 
smtp3.libero.it
 [193.70.192.53] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 Se non č cosě allora non ho capito la domanda.
La seconda che hai detto!
Leggi i post di Silvio di Dario e la risposta di Massimo
Ciao
Gianni