Module: اعداد کاتالان


Problem

1 /2


تعداد اعداد کاتالان

Theory Click to read/hide

اعداد کاتالان کجا رخ می دهند؟
 

-تعداد psp با تعداد معینی از جفت براکت
-تعداد درختان دوتایی با تعداد برگ معین
-تعداد مسیرهایی از گوشه سمت چپ پایین تا گوشه سمت راست بالا در مربع n * n که با مورب تماس ندارند

-تعداد تقسیمات n-gon به مثلث



چگونه شمارش کنیم؟
 
1) فرمول شماره n کاتالان:



2)
•بیایید یک PSS با طول 2n
داشته باشیم
•بدیهی است که با یک مهاربند باز شروع می شود
•بنابراین، بگویید P = (A)B، جایی که A و B – همچنین psp (علاوه بر این، A و B می توانند خالی باشند)
•اگر طول A = 2k باشد، می توان دنباله A را به روش های Ck ترکیب کرد
•سپس طول B = 2(n – k - 1) و B را می توان به روش های Cn-k-1 ترکیب کرد
•فرمول dp را می بینیم: Cn = مجموع (Ck * Cn-k-1) برای همه k <




مواد استفاده شده:

Problem

خروجی N-امین شماره کاتالان

ورودی
خط اول ورودی حاوی یک عدد N است (\(1 <= N <= 20\)) .
 
خروجی
یک شماره چاپ کنید - Nامین شماره کاتالان
 

 

نمونه‌ها
<سر> <بدن>
# ورودی خروجی
1 1 1

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!