Quanti alberi binari propri si possono formare con n nodi?

[Patras]

Ciao a tutti conoscete per caso qualche formula o forse vi viene in mente qualche idea matematica per trovare il numero di alberi binari propri diversi strutturalmente che si possono costruire con n nodi?
Per albero proprio intendo albero binario i cui nodi hanno due soli figli (a parte le foglie che non ce li hanno).

L'ho messo in informatica perché ho scritto un algoritmo ricorsivo (java) che lo risolve ma non so se è giusto perché ho perso un'ora a farlo facendo varie correzioni con questo magari rendendolo efficiente solo per i primi casi che sono riuscito a verificare a mano sul foglio. (n=3, n=5, n=7, n=9) però per esempio per n=9 non andava e ho dovuto fare una correzione. Per n>9 ormai non ho voglia di verificare a mano.
Se volete verificarlo guardando il codice è dura spiegarvelo ma sicuramente le sue prestazioni temporali fanno pellagra. Si basa sul fatto che togliendo ogni volta 2*k nodi da uno dei sottoalberi rimango con 2*k+1 nodi dall'altro sottoalbero e le combinazioni che si creano a loro volta se moltiplicate e sommate mi danno il risultato totale. Siccome tanti casi i ripetono per simmetria li moltiplico per 2. Quelli invece in cui l'albero (o sottalbero preso) sono "bilanciati" cioè stesso numeri di nodi, mi sono accorto che non conviene moltiplicarli per 2 perché non si ripetono. Insomma se qualcuno riesce a verificarlo per numeri più grandi di 9 o conosce qualche formula mi aiuta molto:

Codice: Seleziona tutto

public static int getQ(int n)
{
   if(n<=3)
      return 1;
   int s=0, r=0;
   for(int i=1; 2*i<=(n+1)/2; i++)
   {
      r = getQ(n-2*i)*getQ(2*i-1);
        if(2*i-1 != n-2*i)
         r *= 2;
         s+=r;
   }
   return s;
}


[IlGuru]

Tiro a indovinare:
floor( ( n - 1 ) / 2 )

[Patras]

Non credo proprio. Quello che hai messo mi sembra il numero di foglie.
Forse per chi è bravo con la combinatoria magari dando un'occhiata anche ai miei risultati sperimentali... ma comunque vada mi basta anche una conferma se il codice potrebbe andare... o se mi offriste i vostri risultati per n=11, n=13... magari sapete come metterci di meno...

Miei risultati che verificano anche il programma
n=3 ovviamente 1
n=5 -> 2
n=7 -> 5
n=9 -> 14

[IlGuru]

Allora non ho capito la definizione di albero proprio

[PietroBaima]

Se ho fatto i conti giusti per n=11 mi viene 42 e per n=13 mi viene 132.
Ti torna?
Non ho guardato il tuo programma.

[Patras]

n=11 mi viene 42, e per n=13 mi viene 132

WOW! I conti tornano! Grazie mille come hai fatto? moltiplicando i casi più semplici?

[rugweri]

Il numero di alberi propri con N nodi (foglie escluse) è il N-esimo numero di Catalan, Patras...

https://it.wikipedia.org/wiki/Numero_di_Catalan

[PietroBaima]

perché ho fatto un plot della tua sequenza e l'ho sovrapposta a e^x/x.

Più o meno ci siamo asintoticamente, quindi ho pensato che la tua successione fosse una dismutazione semplice.

Untitled-1.jpg (8.18 KiB) Osservato 6242 volte

Però non ci siamo localmente, all'inizio, dove la crescita è più lenta.

poiché per Stirling il problema è l'n^n.

Devo trovare quindi una successione che stia nel mezzo, tipo un set di Mandelbrot o di Catalan.

Molto subdolamente e trassando alla grande le ho provate entrambe e Catalan verifica la tua sequenza

Codice: Seleziona tutto

f[n_] = (2 n)!/(n! (n + 1)!);
Table[f[n], {n, 1, 6}]

Out[1]= {1, 2, 5, 14, 42, 132}

Così hai anche la formula.

Eh, era bello quando mi potevo occupare di queste cose tranquillamente, senza altri grattacapi per la testa...

EDIT: rugweri conosce la teoria degli alberi binari meglio! Sorry per la sovrapposizione

[rugweri]

Conoscere la teoria degli alberi binari meglio di un fisico-matematico-genioassoluto? Ma assolutamente no
In realtà, c'è il trucco: pochi giorni fa ho finito di leggere questo, dove la correlazione tra numeri di Catalan ed alberi binari propri è citata esplicitamente un bel po' di volte

[Patras]

infatti mi veniva il dubbio di metterla nella sezione di matematica perché mi sembrava più opportuno però d'altra parte avevo scritto il programma Sta di fatto che mi sono accorto di aver svolto sempre oggi un altro problema con un algoritmo completamente diverso dietro al quale però c'era questo numero di Catalan (problema delle parentesi)... è questo il bello dell'informatica, a volte puoi saltare la matematica

Comunque volevo ringraziarvi per le risposte