یک درخت $n$ راسی را که یک راس در آن به عنوان ریشه تعیین شده باشد، «درخت ریشه‌دار» می‌نامیم. در این درخت، هر راس به‌جز ریشه یک پدر دارد و اگر برگ نباشد، یک سری فرزند خواهد داشت.

اگر در یک درخت ریشه‌دار برای هر راس، ترتیبی خاص روی فرزندان آن راس در نظر بگیریم، یک «نمایش مرتب» از این درخت را ارائه داده‌ایم. مثلا درختی با سه راس ۲،۱ و ۳ در نظر بگیرید که راس ۱ به ۲ و ۳ وصل باشد. اگر ۱ ریشه‌ی این درخت باشد٬ یک نمایش مرتب این درخت به این صورت است که ۱ بالا، ۲ بچه‌ی سمت چپ و ۳ بچه‌ی سمت راست ۱ باشند و یک نمایش مرتب دیگر این درخت آن است که ۱ بالا، ۲ فرزند سمت راست و ۳ فرزند سمت چپ ۱ باشند.

فرض کنید رئوس یک درخت ریشه‌دار را با شماره‌های ۱ تا $n$ برچسب گذاشته باشیم. در این صورت این درخت را «جالب» می‌نامیم اگر به ازای هر دو راس با شماره‌های $i$ و $j$، شماره‌ی تمامی رئوسی از درخت که در مسیر بین $i$ و $j$ آمده اند (به جز خود $i$ و $j$) کم‌تر از ماکزیمم $i$ و $j$ باشد.

تعداد کل نمایش‌های مرتب برای درخت‌های ریشه‌دار جالب $n$ راسی چقدر است؟(یک رابطه‌ی صریح (غیر بازگشتی) بر حسب $n$ به علاوه‌ی اثبات درستی آن، لازم و کافی است).

• سوال بعد
• سوال قبل