מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים/תרגילים/נוסחת נסיגה למספר עצי שונים/תשובה

הוכחה: ֲנבחר איבר כלשהו כשורש העץ, ונגדיר כ$\displaystyle i$ את גודל תת-העץ השמאלי (כלומר, האיבר שבחרנו הוא מספר $\displaystyle i+1$ בגדלו בקבוצה). לפי ההגדרה, יש $\displaystyle T(i)$ אפשרויות שונות לתת-העץ השמאלי. עבור כל אחת מאפשרויות אלה, יש $\displaystyle T(n-i-1)$ אפשרויות לסדר את תת-העץ הימני (המכיל $\displaystyle n-i-1$ איברים). כלומר, כאשר יש $\displaystyle i$ איברים בתת-העץ השמאלי, יש $\displaystyle T(i)\cdot T(n-i-1)$ עצים שונים.

נותר רק לחבר את כל האפשרויות עבור כל ערכי $\displaystyle i$ השונים, ו$\displaystyle i$ יכול לקבל את הערכים $\displaystyle 0,1,\ldots ,n-1$.