Newsgroup: it.hobby.enigmi
Titolo: Alberi

Supponiamo di avere r1 alberi di ordine 2 con 1 foglia (" | " ), r2 alberi
di ordine 3 con 2 foglie ( "/\") ed infine r3 alberi di ordine 4 con 3
foglie ("/|\").Unendoli tutti quanti alberi si possono formare?Es:
r1=2,r2=1,r3=0 abbiamo 6 alberi.







Scusate tanto.Non era mia intenzione.Ho già chiamato padre Karras per
esorcizzare l'outlook.>8-[
Scusatemi spesso,scusate Onoff.  <:-{

Onoff chiede

Bellissimo problema, mi ha fatto impazzire!
Sono nientepopodimeno che:
                   (3r3+2r2+r1)!
N(r1,r2,r3) = -----------------------
              r1! r2! r3! (2r3+r2+1)!
Ancora mi fuma il cervello, non credo di riuscire a ricostruire per intero
il procedimento.
Come quasi sempre mi succede la soluzione è arrivata grazie ad un mix di
tecniche, che comprendono soluzione a mano dei casi più semplici,
programmazione per riempire una tabella con qualche risultato di ordine
maggiore, molti scarabocchi, alcune considerazioni preliminari, molte altre
suggerite dall'evolversi dei risultati, qualche chilo di semplificazioni ed
un po' di fortuna. Alla fine sembra tutto molto semplice, ma ancora non
riesco a venirne a capo.
Per esempio, guardate questo approccio, che avevo tentano ed abbandonato:
tramite un algoritmo di visita (ad esempio la classica visita in profondità,
prima i figli poi il padre) possiamo rappresentare un albero tramite una
stringa:
Es.:
    1
    |
    2
   / \
  1   0
  |
  3
 /|\
1 0 2
|  / \
0 0   0
01000231021
Ogni albero genera una stringa, ma non tutte le stringhe sono
sintatticamente corrette, ad esempio il parsing di "0210" genera un errore
pur essendo corretto il numero di foglie.
Con a=r1+r2+r3 caratteri "1,2,3" e f=2*r1+r2+1 foglie "0" quante stringhe,
anche non legali, si possono formare?
Bisogna prima provvedere ad assegnare i posti per le foglie (es.:
0x0000xxx0xx)
e si può farlo in C(a+f,f) modi diversi, e per ogni assegnamento disporre
gli a nodi interni al posto delle x (es: 123121), e questo lo si fa
D(a)=a!/(r1!r2!r3!) modi diversi (alberi dello stesso ordine non sono
distinguibili). In totale sono S=C(a+f,f)*D(a)
Poiché risulta
N = S/(a+f)
questo suggerisce che solo una percentuale di 1/(a+f) di stringhe risutano
"ben formate", nel nostro esempio 1 su 10. Qualcuno riesce a giustificare la
cosa?
Intanto un notevole risultato che si ricava dalla formula trovata è il
seguente, generalizzazione di un problema noto nel caso degli alberi binari
(numeri Catalani):
N(r,0,0) = (r)!/(r!) = 1
N(0,r,0) = (2r)!/(r!*r!)
N(0,0,r) = (3r)!/(r!*(2r)!)
Credo si possa generalizzare tranquillamente ad alberi di ordine qualsiasi
(nr)!/(r!((n-1)r)!)
Silv:o)

"Silvio Sergio" ha scritto nel messaggio

Bravissimo!Credevo che non interessasse a nessuno,invece immancabilmente c'è
la risposta di Silv:o) !!Anche a me è costato molto risolverlo,solo che io
partivo con 100 km di vantaggio .....conoscevo la formula risolutiva.:-}Io
ho utilizzato il lemma di Raney che recita:
data una soluzione dell'equazione x1+x2+....+xn= -1 esiste solo uno
spostamento ciclico dei numeri a1,a2,..,an (soluzioni prima citate)per cui
tutte le somme parziali x1+...+xk  con k=[1..n-1] sono non negative.Da qui
si può passare alle stringhe ( oppure multinsiemi).
Onoff