FA
All
Articles
Dictionary
Quotes
Map

Wikiwand ❤️ Wikipedia

PrivacyTerms

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

From Wikipedia, the free encyclopedia

اعداد کاتالان
تعریفخواصکاربرد در ترکیبیاتاثبات فرمولماتریس هانکلتاریخچهپیوندهای مفیدمنابع

اعداد کاتالان در ریاضیات ترکیبی، یک سری از اعداد طبیعی هستند که در مسائل شمارشی متنوع که معمولاً اشیا به صورت بازگشتی تعریف شده را در بر می‌گیرند، رخ می‌دهند. این اعداد به افتخار ریاضیدان بلژیکی شارل کاتالان (۱۸۹۴-۱۸۱۴) اعداد کاتالان نامیده می‌شوند. وی استنتاج مقدماتی از فرمول را کشف کرد. کاتالان مقالات متعددی در زمینه آنالیز، ترکیبیات، جبر، هندسه، احتمالات و نظریه اعداد منتشر کرد. درستی حدس او که اعداد ۰، ۱، ۸، ۹ تنها زوج اعداد توان کامل متوالی است که به صورت توانی می‌باشد در دهه ۱۹۷۰ ثابت شد.

nاُمین عدد کاتالان عبارت است از:

C n = 1 n + 1 ( 2 n n ) = ( 2 n ) ! ( n + 1 ) ! n !  for  n ≥ 0. {\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\mbox{ for }}n\geq 0.} {\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\mbox{ for }}n\geq 0.}

چند عدد اولیه کاتالان عبارتند از:

۱، ۲، ۵، ۱۴، ۴۲، ۱۳۲، ۴۲۹، ۱۴۳۰، ۴۸۶۲، ۱۶۷۹۶، ۵۸۷۸۶، ۲۰۸۰۱۲، ۷۴۲۹۰۰، ۲۶۷۴۴۴۰، ۹۶۹۴۸۴۵، ۳۵۳۵۷۶۷۰، ۱۲۹۶۴۴۷۹۰، ۴۷۷۶۳۸۷۰۰، ۱۷۶۷۲۶۳۱۹۰، ۶۵۶۴۱۲۰۴۲۰، ۲۴۴۶۶۲۶۷۰۲۰، ۹۱۴۸۲۵۶۳۶۴۰، ۳۴۳۰۵۹۶۱۳۶۵۰، ۱۲۸۹۹۰۴۱۴۷۳۲۴، ۴۸۶۱۹۴۶۴۰۱۴۵۲
Thumb
مثلث شماره کاتالان

یک عبارت دیگر برای C n {\displaystyle C_{n}} {\displaystyle C_{n}} به صورت زیر است:

C n = ( 2 n n ) − ( 2 n n − 1 )  for  n ≥ 1. {\displaystyle C_{n}={2n \choose n}-{2n \choose n-1}\quad {\mbox{ for }}n\geq 1.} {\displaystyle C_{n}={2n \choose n}-{2n \choose n-1}\quad {\mbox{ for }}n\geq 1.}

عبارت فوق نشان می‌دهد که C n {\displaystyle C_{n}} {\displaystyle C_{n}} یک عدد طبیعی است که این نتیجه از فرمول اول چندان بدیهی نبود. این عبارت اساس اثبات آندره در مورد صحت فرمول را تشکیل می‌دهد. هم چنین اعداد کاتالان از رابطه بازگشتی زیر نیز به دست می‌آیند:

C 0 = 1 and C n + 1 = ∑ i = 0 n C i C n − i for  n ≥ 0. {\displaystyle C_{0}=1\quad {\mbox{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\mbox{for }}n\geq 0.} {\displaystyle C_{0}=1\quad {\mbox{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\mbox{for }}n\geq 0.}

و همچنین:

C 0 = 1 and C n + 1 = 2 ( 2 n + 1 ) n + 2 C n , {\displaystyle C_{0}=1\quad {\mbox{and}}\quad C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n},} {\displaystyle C_{0}=1\quad {\mbox{and}}\quad C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n},}

که می‌تواند برای محاسبه آن‌ها کاراتر باشد.

به‌طور مجانبی اعداد کاتالان به صورت C n ∼ 4 n n 3 / 2 π {\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}} {\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}} رشد می‌کنند که نشان می‌دهد که عبارت سمت راست برای ∞ →n به سمت یک میل می‌کند.(این عبارت می‌تواند با استفاده از تقریب استرلینگ برای !n اثبات شود) تنها اعدادی از دنباله کاتالان فرد هستند که به صورت n = 2 k − 1 {\displaystyle n={2^{k}}-1} {\displaystyle n={2^{k}}-1} هستند. بقیه همگی زوج می‌باشند.

تعداد زیادی از مسائل شمارشی در ترکیبیات هستند که راه حلی با استفاده از اعداد کاتالان برای آن‌ها ارائه شده‌است. کتاب ترکیبیات شمارشی جلد دوم اثر ریچارد استانلی شامل مجموعه‌ای از تمرین هاست که ۶۶ تفسیر مختلف از اعداد کاتالان را شرح می‌دهد. در زیر چند نمونه آمده‌است.

- C n {\displaystyle C_{n}} {\displaystyle C_{n}} تعداد کلمات Dyck به طول ۲n است. یک کلمه Dyck یک رشته است که n تاX و n تا Y دارد؛ به گونه‌ای که تعداد Xها در هر بخش آغازین آن بیشتر از تعداد Yهاست. برای مثال در زیر کلمات Dyck با طول ۶ آمده اند:

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY

- چنانچه هر نماد X را به صورت یک پرانتز باز ببینیم و هر نماد Y را یک پرانتز بسته آنگاه C n {\displaystyle C_{n}} {\displaystyle C_{n}} تعداد عباراتی که شامل n جفت پرانتزگذاری صحیح هستند را نشان می‌دهد.

((())) ()(()) ()()() (())() (()())

- C n {\displaystyle C_{n}} {\displaystyle C_{n}} تعداد راه‌های مختلفی است که n+۱ عامل می‌توانند پرانتزگذاری شوند. برای n=۳ به عنوان مثال ۵ پرانتزگذاری مختلف برای چهار عامل را داریم:

( ( a b ) c ) d ( a ( b c ) ) d ( a b ) ( c d ) a ( ( b c ) d ) a ( b ( c d ) ) {\displaystyle ((ab)c)d\quad (a(bc))d\quad (ab)(cd)\quad a((bc)d)\quad a(b(cd))} {\displaystyle ((ab)c)d\quad (a(bc))d\quad (ab)(cd)\quad a((bc)d)\quad a(b(cd))}

- C n {\displaystyle C_{n}} {\displaystyle C_{n}}تعداد درخت‌های دودویی غیر هم ریخت با n راس است که بچه دارند که معمولاً رئوس داخلی یا شاخه گفته می‌شوند.

- C n {\displaystyle C_{n}} {\displaystyle C_{n}} تعداد راه‌های مختلفی است که یک چندضلعی محدب با n+۲ ضلع می‌تواند با وصل کردن رأس‌ها با خطوط مستقیم مثلث بندی شود. شش گوشه زیر برای n=۴ نشان می‌دهد:

Thumb

چندین راه برای نشان دادن اینکه چرا فرمول C n = 1 n + 1 ( 2 n n ) {\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}} {\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}} مسائل ترکیبیاتی ذکر شده را حل می‌کند وجود دارد. اولین اثبات از تابع مولد استفاده می‌کند. دومین و سومین اثبات مثال‌هایی از اثبات نگاشت‌های دوطرفه هستند.

می بینیم که تعداد زیادی از مسائل ترکیبیاتی فوق از راه بازگشتی حل می‌شوند.

با استفاده از فرمول C 0 = 1 and C n + 1 = ∑ i = 0 n C i C n − i for  n ≥ 0. {\displaystyle C_{0}=1\quad {\mbox{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\mbox{for }}n\geq 0.} {\displaystyle C_{0}=1\quad {\mbox{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\mbox{for }}n\geq 0.} می‌توانیم با استفاده از تکنیک‌های شناخته شده برای توابع مولد یک فرمول واضح برای اعداد کاتالان به دست بیاوریم. با تعریف f ( z ) {\displaystyle f(z)} {\displaystyle f(z)} که همه اعداد کاتالان را شامل می‌شود شروع می کنیم: f ( z ) = C 0 + C 1 z + C 2 z 2 + C 3 z 3 + . . . = C n + 1 = c ( x ) = ∑ n = 0 ∞ C n x n {\displaystyle f(z)=C_{0}+C_{1}z+C_{2}z^{2}+C_{3}z^{3}+...=C_{n+1}=c(x)=\sum _{n=0}^{\infty }C_{n}x^{n}} {\displaystyle f(z)=C_{0}+C_{1}z+C_{2}z^{2}+C_{3}z^{3}+...=C_{n+1}=c(x)=\sum _{n=0}^{\infty }C_{n}x^{n}}

اگر (f(z را در خودش ضرب کنیم و [ f ( z ) ] 2 {\displaystyle [f(z)]^{2}} {\displaystyle [f(z)]^{2}} را به دست بیاوریم، نخستین جملات این چنین هستند:

...+ [ f ( z ) ] 2 = C 0 C 0 + ( C 1 C 0 + C 0 C 1 ) z + ( C 2 C 0 + C 1 C 1 + C 0 C 2 ) z 2 {\displaystyle [f(z)]^{2}=C_{0}C_{0}+(C_{1}C_{0}+C_{0}C_{1})z+(C_{2}C_{0}+C_{1}C_{1}+C_{0}C_{2})z^{2}} {\displaystyle [f(z)]^{2}=C_{0}C_{0}+(C_{1}C_{0}+C_{0}C_{1})z+(C_{2}C_{0}+C_{1}C_{1}+C_{0}C_{2})z^{2}}

ضرایب برای توان‌های z همانهایی هستند که از معادله C n = 1 n + 1 ( 2 n n ) {\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}} {\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}} بر می‌آید

...+ [ f ( z ) ] 2 = C 1 + C 2 z + C 3 z 2 + C 4 z 3 {\displaystyle [f(z)]^{2}=C_{1}+C_{2}z+C_{3}z^{2}+C_{4}z^{3}} {\displaystyle [f(z)]^{2}=C_{1}+C_{2}z+C_{3}z^{2}+C_{4}z^{3}}

اگر که (f(z رادر z ضرب کنیم و به آن C 0 {\displaystyle C_{0}} {\displaystyle C_{0}} را بیفزاییم به دست می آوریم:

f ( z ) = C 0 + z [ f ( z ) ] 2 {\displaystyle f(z)=C_{0}+z[f(z)]^{2}} {\displaystyle f(z)=C_{0}+z[f(z)]^{2}}

معادله فوق یک معادله درجه دو است که می‌توانیم ان را حل کنیم. آن را به صورت z f 2 − f − C 0 = 0 {\displaystyle zf^{2}-f-C_{0}=0} {\displaystyle zf^{2}-f-C_{0}=0} می نویسیم. بنابراین به دست می آوریم:

f ( z ) = 1 − 1 − 4 x 2 x ( 8 ) {\displaystyle f(z)={\frac {1-{\sqrt {1-4x}}}{2x}}\quad (8)} {\displaystyle f(z)={\frac {1-{\sqrt {1-4x}}}{2x}}\quad (8)}

توجه کنید که ما علامت منفی را برگزیدیم. چون میدانیم که f ( 0 ) = C 0 = 1 {\displaystyle f(0)=C_{0}=1} {\displaystyle f(0)=C_{0}=1}؛ بنابراین اگر علامت مثبت را جایگذاری کنیم وقتی z→0، آنگاه f ( z ) → ∞ {\displaystyle f(z)\to \infty } {\displaystyle f(z)\to \infty }

برای بسط از فرمول دوجمله‌ای استفاده می‌کنیم؛ اگر که با استفاده از فرمول دوجمله‌ای با نماهای اعشاری آشنا نیستید، نگران نباشید. دقیقاً همانگونه است؛ با این تفاوت که هیچگاه تمام نمی‌شود. بیایید به فرمول دوجمله‌ای برای یک نمای صحیح نگاهی بیندازیم و همان محاسبات را برای یک عدد اعشاری انجام دهیم. اگر n یک عدد صحیح باشد، فرمول دوجمله‌ای به این قرار است:

... ( a + b ) n = a n + n 1 a n − 1 b 1 + n ( n − 1 ) 2.1 a n − 2 b 2 + n ( n − 1 ) ( n − 2 ) 3.2.1 a n − 3 b 3 + {\displaystyle (a+b)^{n}=a^{n}+{\frac {n}{1}}a^{n-1}b^{1}+{\frac {n(n-1)}{2.1}}a^{n-2}b^{2}+{\frac {n(n-1)(n-2)}{3.2.1}}a^{n-3}b^{3}+} {\displaystyle (a+b)^{n}=a^{n}+{\frac {n}{1}}a^{n-1}b^{1}+{\frac {n(n-1)}{2.1}}a^{n-2}b^{2}+{\frac {n(n-1)(n-2)}{3.2.1}}a^{n-3}b^{3}+}

اگرn یک عدد صحیح باشد، صورت کسر سرانجام یک عبارت به صورت (n-n)خواهد داشت؛ بنابراین آن جمله و تمام جملات بعد ازآن صفر خواهند بود. اگر nعدد صحیح نباشد و مثلاً برای مثال ما 1 2 {\displaystyle {\frac {1}{2}}} {\displaystyle {\frac {1}{2}}} باشد، صورت کسر صفر را خواهد گذراند و ادامه خواهد یافت. در زیر تعدادی از نخستین جملات بسط آمده اند:

( 1 − 4 x ) ( 1 2 ) = 1 − ( 1 2 ) 1 4 z + ( 1 2 ) ( − 1 2 ) 2.1 ( 4 z ) 2 − ( 1 2 ) ( − 1 2 ) ( − 3 2 ) 3.2.1 ( 4 z ) 3 + ( 1 2 ) ( − 1 2 ) ( − 3 2 ) ( − 5 2 ) 4.3.2.1 ( 4 z ) 4 − ( 1 2 ) ( − 1 2 ) ( − 3 2 ) ( − 5 2 ) ( − 7 2 ) 5.4.3.2.1 ( 4 z ) 5 + . . . {\displaystyle (1-4x)^{({\frac {1}{2}})}=1-{\frac {({\frac {1}{2}})}{1}}4z+{\frac {({\frac {1}{2}})(-{\frac {1}{2}})}{2.1}}(4z)^{2}-{\frac {({\frac {1}{2}})(-{\frac {1}{2}})(-{\frac {3}{2}})}{3.2.1}}(4z)^{3}+{\frac {({\frac {1}{2}})(-{\frac {1}{2}})(-{\frac {3}{2}})(-{\frac {5}{2}})}{4.3.2.1}}(4z)^{4}-{\frac {({\frac {1}{2}})(-{\frac {1}{2}})(-{\frac {3}{2}})(-{\frac {5}{2}})(-{\frac {7}{2}})}{5.4.3.2.1}}(4z)^{5}+...} {\displaystyle (1-4x)^{({\frac {1}{2}})}=1-{\frac {({\frac {1}{2}})}{1}}4z+{\frac {({\frac {1}{2}})(-{\frac {1}{2}})}{2.1}}(4z)^{2}-{\frac {({\frac {1}{2}})(-{\frac {1}{2}})(-{\frac {3}{2}})}{3.2.1}}(4z)^{3}+{\frac {({\frac {1}{2}})(-{\frac {1}{2}})(-{\frac {3}{2}})(-{\frac {5}{2}})}{4.3.2.1}}(4z)^{4}-{\frac {({\frac {1}{2}})(-{\frac {1}{2}})(-{\frac {3}{2}})(-{\frac {5}{2}})(-{\frac {7}{2}})}{5.4.3.2.1}}(4z)^{5}+...}

و به دست می آوریم:

( 1 − 4 x ) 1 2 = 1 − 1 1 ! 2 z − 1 2 ! 4 z 2 − 3.1 3 ! 8 z 3 − 5.3.1 4 ! 16 z 4 − 7.5.3.1 5 ! 32 z 5 − . . . ( 9 ) {\displaystyle (1-4x)^{\frac {1}{2}}=1-{\frac {1}{1!}}2z-{\frac {1}{2!}}4z^{2}-{\frac {3.1}{3!}}8z^{3}-{\frac {5.3.1}{4!}}16z^{4}-{\frac {7.5.3.1}{5!}}32z^{5}-...\quad (9)} {\displaystyle (1-4x)^{\frac {1}{2}}=1-{\frac {1}{1!}}2z-{\frac {1}{2!}}4z^{2}-{\frac {3.1}{3!}}8z^{3}-{\frac {5.3.1}{4!}}16z^{4}-{\frac {7.5.3.1}{5!}}32z^{5}-...\quad (9)}

از معادله 8 و 9 داریم:

f ( z ) = 1 + 1 2 ! 2 z + 3.1 3 ! 4 z 2 + 5.3.1 4 ! 8 z 3 + 7.5.3.1 5 ! 16 z 4 + . . . ( 10 ) {\displaystyle f(z)=1+{\frac {1}{2!}}2z+{\frac {3.1}{3!}}4z^{2}+{\frac {5.3.1}{4!}}8z^{3}+{\frac {7.5.3.1}{5!}}16z^{4}+...\quad (10)} {\displaystyle f(z)=1+{\frac {1}{2!}}2z+{\frac {3.1}{3!}}4z^{2}+{\frac {5.3.1}{4!}}8z^{3}+{\frac {7.5.3.1}{5!}}16z^{4}+...\quad (10)}

عباراتی نظیر 7.5.3.1 کمی دردسرسازند. این عبارات شبیه فاکتوریل‌ها هستند؛ اما اعداد زوج را در برندارند. اما توجه کنید که 2 2 .2 ! = 4.2 {\displaystyle 2^{2}.2!=4.2} {\displaystyle 2^{2}.2!=4.2} و 2 3 .3 ! = 6.4.2 {\displaystyle 2^{3}.3!=6.4.2} {\displaystyle 2^{3}.3!=6.4.2} و 2 4 .4 ! = 8.6.4.2 {\displaystyle 2^{4}.4!=8.6.4.2} {\displaystyle 2^{4}.4!=8.6.4.2} و مشابه این. بنابراین ( 7.5.3.1 ) .2 4 4 ! = 8 ! {\displaystyle (7.5.3.1).2^{4}4!=8!} {\displaystyle (7.5.3.1).2^{4}4!=8!} . بنابراین اگر این ایده را برای معادله 10 به کار ببریم به دست می آوریم:

f ( z ) = 1 + 1 2 2 ! 1 ! 1 ! z + 1 3 4 ! 2 ! 2 ! z 2 + 1 4 6 ! 3 ! 3 ! z 3 + 1 5 8 ! 4 ! 4 ! z 4 + . . . = ∑ i = 0 ∞ 1 i + 1 ( 2 i i ) z i {\displaystyle f(z)=1+{\frac {1}{2}}{\frac {2!}{1!1!}}z+{\frac {1}{3}}{\frac {4!}{2!2!}}z^{2}+{\frac {1}{4}}{\frac {6!}{3!3!}}z^{3}+{\frac {1}{5}}{\frac {8!}{4!4!}}z^{4}+...=\sum _{i=0}^{\infty }{\frac {1}{i+1}}{2i \choose i}z^{i}} {\displaystyle f(z)=1+{\frac {1}{2}}{\frac {2!}{1!1!}}z+{\frac {1}{3}}{\frac {4!}{2!2!}}z^{2}+{\frac {1}{4}}{\frac {6!}{3!3!}}z^{3}+{\frac {1}{5}}{\frac {8!}{4!4!}}z^{4}+...=\sum _{i=0}^{\infty }{\frac {1}{i+1}}{2i \choose i}z^{i}}

از این عبارت می‌توانیم نتیجه بگیریم که n امین عدد کاتالان با این فرمول به دست می‌آید:

C i = 1 i + 1 ( 2 i i ) {\displaystyle C_{i}={\frac {1}{i+1}}{2i \choose i}} {\displaystyle C_{i}={\frac {1}{i+1}}{2i \choose i}}

ماتریس n*n هانکل که هر درایه ( i , j ) {\displaystyle (i,j)} {\displaystyle (i,j)} آن عدد کاتالان C i + j − 2 {\displaystyle C_{i+j-2}} {\displaystyle C_{i+j-2}} است بدون توجه به n دترمینانی برابر یک دارد. برای مثال برای n=۴ داریم: Thumb

توجه کنید که درایه‌ها شیفت خورده‌اند و به صورت C i + j − 1 {\displaystyle C_{i+j-1}} {\displaystyle C_{i+j-1}} بازهم بدون توجه به n دترمینان یک است. برای مثال برای n=۴ داریم:

Thumb

دنباله کاتالان نخستین بار در قرن هیجدهم توسط لئونارد اویلر به کار برده شد که به تعداد راه‌های تقسیم کردن یک چندضلعی به مثلث علاقه‌مند بود. شارل کاتالان ارتباط بین پرانتزگذاری عبارات را در طول کشفیاتش در باره معمای برج‌های هانوی کشف کرد. ترفند شمارشی برای کلمات Dyck نیز توسط د.آندره در سال ۱۸۸۷ به دست آمد.

بررسی روش‌های برنامه‌نویسی اعداد کاتالان

    ویکی‌پدیای انگلیسی

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

    Edit in WikipediaRevision historyRead in Wikipedia

    Wikiwand in your browser!

    Seamless Wikipedia browsing. On steroids.

    Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

    Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

    Chrome
    Wikiwand for Chrome
    Edge
    Wikiwand for Edge
    Firefox
    Wikiwand for Firefox

    تعریف

    خواص

    کاربرد در ترکیبیات

    اثبات فرمول

    ماتریس هانکل

    تاریخچه

    پیوندهای مفید

    منابع