OliForum Matematico

Sir Yussen ha scritto:Semplicemente valuto le possibili combinazioni considerando ogni volta un capo lettera diversa,e successivamente sottraggo dalla somma le combinazioni uguali in entrambi i casi con capolettera diversa....


Poi non è che è sicuro al 100% quel che dico,può anche darsi che mi sbaglio eh xD

Sì sbagli. Conti combinazioni che non valgono e ne dimentichi altre se ho capito (?) il tuo ragionamento (?)

Ad esempio CBAED l'hai contata?



EDCAB come la ottieni invece?



Clara, il simbolo che hai citato te adesso è il coefficiente binomiale. E "significa" fattoriale del numero sopra fratto il prodotto tra il fattoriale del numero sotto per il fattoriale della differenza dei due numeri

...è più facile vedere la formula

http://it.wikipedia.org/wiki/Coefficiente_binomiale

EDCAB è impossibile, lui l'ha contata?
Se l'assistente parte dalla E le altre 4 lettere ormai sono tutte impilate sotto e non può che fare E D C B A.


Grazie per la dritta!

Clara ha scritto:EDCAB è impossibile, lui l'ha contata?
Se l'assistente parte dalla E le altre 4 lettere ormai sono tutte impilate sotto e non può che fare E D C B A.

Lo so che è impossibile, ma se ho capito il suo ragionamento lui l'ha contata...per quello l'ho citata...

Mentre non ne ha contate altre...sempre che abbia capito il suo ragionamento eh, non son sicuro ^^

Prego, comunque

dario2994 ha scritto: E qui un hint per la soluzione:
deriva più o meno direttamente dalla conoscenza dei numeri di Catalan.
Leggiucchiateli su wiki... è abbastanza facile far corrispondere questo problema con il numero di percorsi sotto la bisettrice in un quadrato 5x5. Inoltre controllando bene su wiki compare anche questo stesso problema al nome stack-sortable permutations.

Non ho capito, puoi spiegarmi come ci entrano Catalan e l'idea del quadrato 5x5?

Grazie!

Alur... dividiamo la giornata in 5 momenti precisi: i momenti in cui viene poggiata una lettera sulla scrivania.
Se la segretaria stampa dopo un momento o subito prima del successiva non cambia nulla... quindi associamo ad ogni momento il numero di lettere stampate tra quel momento e il successivo. Chiamo $ $a_i $ il numero dei documenti stampati all' i-esimo momento.Ad ogni sequenza di $ $a_j $ corrisponde un ordine di scrittura e viceversa. Ora contiamo gli $ $a_i $. Per comodità fisso $ $a_0=0 $.
Sono numeri interi.
Sono crescenti non strettamente.
$ $a_i\le i $
$ $a_5=5 $
Ora disegno sul piano cartesiano la funzione $ $a_x $ (ovviamente negli interi da 0 a 5)... poi connetto in questo modo i punti: da $ $(i,x_i) $ traccio un segmento fino a $ $(i+1,x_i) $ da qui traccio un segmento (se necessario) fino a $ $(i+1,a_{i+1}) $... sembra proprio che abbia disegno un percorso sotto la bisettrice in un quadrato 5x5 Ora è facile far corrispondere ad ogni percorso una sequenza... quindi ora tocca contare i percorsi, fortunatamente l'ha fatto qualcuno al posto mio e risulta incredibilmente essere 42.
Per quest'ultimo fatto vi rimando alla lettura dei numeri di Catalan.

tra l'altro se non mki sbaglio questo stesso problema (o comunque molto simile) l'aveva fatto a roma callegari spiegando appunto i numeri di catalan e partendo dal problema dei percorsi della pulce sotto la bisettrice
mi sembra che con gli stessi numeri si risolva il problema di trovare in quanti modi un poligono convesso può essere diviso in triangoli.

Si Callegari aveva parlato dei numeri di Catalan, affrontandoci vari problemi (non quello dei poligoni) tra cui anche questo... però affrontato in un altro modo, ragionando con gli stack in informatica ;) Che è proprio come ne parla wiki.

Francutio ha scritto:

Sir Yussen ha scritto:Semplicemente valuto le possibili combinazioni considerando ogni volta un capo lettera diversa,e successivamente sottraggo dalla somma le combinazioni uguali in entrambi i casi con capolettera diversa....


Poi non è che è sicuro al 100% quel che dico,può anche darsi che mi sbaglio eh xD

Sì sbagli. Conti combinazioni che non valgono e ne dimentichi altre se ho capito (?) il tuo ragionamento (?)

Ad esempio CBAED l'hai contata?



EDCAB come la ottieni invece?



Clara, il simbolo che hai citato te adesso è il coefficiente binomiale. E "significa" fattoriale del numero sopra fratto il prodotto tra il fattoriale del numero sotto per il fattoriale della differenza dei due numeri

...è più facile vedere la formula

http://it.wikipedia.org/wiki/Coefficiente_binomiale

O_O mi sa proprio che non ho capito la traccia O_O

Ok, io ho provato a fare un ragionamento chilometrico, ma molto facile da capire, sfruttando l'idea di dario.
Il problema è che mi viene 41!!
Intanto lo posto qui, penso che la cosa più probabile, sia che mi sono persa qualcosa...

(Vi ho avvertito, è chilometrico! )

http://img221.imageshack.us/g/immagine1m.png/

Clara ha scritto:Ok, io ho provato a fare un ragionamento chilometrico, ma molto facile da capire, sfruttando l'idea di dario.
Il problema è che mi viene 41!!
Intanto lo posto qui, penso che la cosa più probabile, sia che mi sono persa qualcosa...

(Vi ho avvertito, è chilometrico! )

http://img221.imageshack.us/g/immagine1m.png/

Nella configurazione 3-2-0-0-0 ci sono 5 casi, e non 4


00023
00032
00203
00302
02003

Quello in grassetto è quello che credo tu abbia saltato.

Oh! Perfetto, grazie!
Ci si mette il triplo del tempo, così, ma è più semplice da capire.

Clara ha scritto:Oh! Perfetto, grazie!
Ci si mette il triplo del tempo, così, ma è più semplice da capire.

Ti capisco benissimo, anche io faccio sempre tutto a casi (o a caso, boh?)