دنباله اعداد کاتالان (Catalan Numbers) یکی از دنباله‌های عددی مشهور ریاضیات است که برای عدد نامنفی n به صورت Cn نمایش داده می‌شود.


کد:
Cn:    1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...
این دنباله کاربردهای بسیاری در مسائل شمارشی دارد. از جمله:
1- تعداد درخت‌های دودویی با n راس داخلی برابر Cn است:

2- تعداد درخت‌ها با n یال برابر Cn است:

3- تعداد پرانتزبندی‌های صحیح با استفاده از n جفت پرانتز باز و بسته برابر Cn است:

کد:
n = 1:    ( )

 n = 2:    ( ( ) )    ,    ( ) ( )
 n = 3:    ( ( ( ) ) )    ,    ( ( ) ) ( )    ,    ( ) ( ( ) )    ,    ( ( ) ( ) )    ,    ( ) ( ) ( )
4- تعداد پرانتزبندی‌های صحیح n عبارت ریاضی برابر Cn-1 است:

کد:
n = 1:    ( A )

 n = 2:    ( A B )
 n = 3:    ( ( A B ) C )    ,    ( A ( B C ) )
 n =  4:    ( ( ( A B ) C ) D )    ,    ( ( A ( B C ) ) D )    ,    ( ( A B )  ( C D ) )    ,    ( A ( ( B C ) D )    ,     ( A ( B ( C D ) ) )
5- تعداد روش‌های مثلث‌بندی یک چندضلعی محدب با n + 2 ضلع برابر Cn است:

6- ...
با بررسی تحلیلی این مسائل، رابطه بازگشتی زیر برای محاسبه جملات دنباله اعداد کاتالان به دست آمده است:

این تعریف، مقدار جمله nام دنباله را به مقادیر تمام جملات قبلی وابسته می‌کند. به عنوان مثال:

کد:
C1 = C0 x C0 = 1 x 1 = 1

 C2 = C0 x C1 + C1 x C0 = 1 x 1 + 1 x 1 = 2
 C3 = C0 x C2 + C1 x C1 + C2 x C0 = 1 x 2 + 1 x 1 + 2 x 1 = 5
پیاده‌سازی محاسبه اعداد کاتالان
اولین و ساده‌ترین پیاده‌سازی برای محاسبه اعداد کاتالان، پیاده‌سازی بازگشتی رابطه فوق است:
کد:
 long catalan_1( int n )
 {
   if( n == 0 )
   {
     return 1;
   }
   long i, sum = 0;
   for( i = 0 ; i < n ; i++ )
   {
     sum += ( catalan_1( i ) * catalan_1( n - i - 1 ) );

   }
   return sum;
 }
این قطعه کد یک پیاده‌سازی تقسیم و غلبه برای محاسبه است که تعداد اعمال ضرب و جمع مورد نیاز آن از مرتبه اجرای نمایی ( Θ( 3n است (چرا؟). چنین مرتبه‌ای نشان از عدم کارایی محاسبه با این روش دارد.
روش تقسیم و غلبه را کنار گذاشته، و روش برنامه‌نویسی پویا را امتحان می‌کنیم. در این روش به جای حرکت از کل به جزء و محاسبه بازگشتی، از جزء به کل حرکت کرده و جملات دنباله از مقادیر کوچکتر به مقادیر بزرگتر محاسبه می‌شود:

کد:
long catalan_2( int n, long catalan[ ] )

 {
   int i, j;
   catalan[ 0 ] = 1;
   for( i = 1 ; i <= n ; i++ )
   {
     catalan[ i ] = 0;
     for( j = 0 ; j < i ; j++ )
     {
       catalan[ i ] += catalan[ j ] * catalan[ i - j - 1 ];
     }

   }
   return catalan[ n ];
 }
همانگونه که از ساختار حلقه‌های تکرار مشخص است، مرتبه اجرای این پیاده‌سازی ( Θ( n2 است، که در مقایسه با تابع قبلی بهبود چشم‌گیری دارد. علاوه بر این، با استفاده از این تابع تمام جملات کوچکتر یا مساوی n محاسبه شده و در آرایه catalan ذخیره می‌شود.

رابطه غیربازگشتی اعداد کاتالان
تا به این جا با تعریف بازگشتی دنباله کاتالان سر و کار داشتیم. اما این دنباله بازگشتی را می‌توان با استفاده از روابط ریاضی حل کرده، و به یک رابطه غیربازگشتی دست یافت.
حل تحلیلی دنباله کاتالان با استفاده از توابع مولد رابطه زیر را نتیجه می‌دهد:

این رابطه اعداد کاتالان را مستقل از جملات قبلی محاسبه می‌کند. اما نیاز به محاسبه ترکیب دو عدد دارد:

کد:
long catalan_3( int n )

 {
   long c = combination( 2 * n, n );
   return ( c / n + 1 );
 }
پیاده‌سازی تابع combination روش‌های مختلفی دارد که ترکیب ( C( 2n, n را در بهترین حالت از مرتبه اجرای ( Θ( n2 محاسبه می‌کند. در نتیجه این روش مزیتی نسبت به روش برنامه‌نویسی پویا ندارد. اما بر اساس این رابطه، می‌توان رابطه بازگشتی زیر را نتیجه گرفت:

و آنرا به صورت زیر پیاده‌سازی کرد:

کد:
long catalan_4( int n )

 {
   if( n == 0 )
   {
     return 1;
   }
   return ( ( ( 4 * n - 2 ) * catalan_4( n - 1 ) ) / ( n + 1 ) );
 }
چنین تابعی اعداد کاتالان را به صورت بازگشتی و با مرتبه اجرای ( Θ( n محاسبه می‌کند. این بهبود در مرتبه را می‌توان با پیاده‌سازی به روش برنامه‌نویسی پویا تعمیم داد و علاوه بر پیاده‌سازی غیربازگشتی، تمامی جملات کوچکتر یا مساوی n را ذخیره کرد:

کد:
long catalan_5( int n, long catalan[ ] )

 {
   int i;
   catalan[ 0 ] = 1;
   for( i = 1 ; i <= n ; i++ )
   {
     catalan[ i ] =  ( ( ( 4 * i - 2 ) * catalan[ i - 1 ] ) / ( i + 1 ) );
   }
   return catalan[ n ];
 }
به این ترتیب تمامی جملات دنباله کاتالان تا یک n دلخواه با مرتبه اجرای ( Θ( n محاسبه می‌شود.