برخی از ساختارهای اعداد کاتالان~ \lr{I}I

نوع مقاله : مقاله پژوهشی

نویسندگان

1 گروه کامپیوتر، مجتمع آموزش عالی تربت‌جام ، تربت‌جام، ایران

2 گروه ریاضی و کامپیوتر، دانشکده ریاضی، دانشگاه فردوسی، مشهد، ایران

چکیده

یکی از مهم‌ترین دلایل شهرت اعداد کاتالان، ظاهر شدن آن‌ها در بسیاری از مسائل شمارشی می‌باشد. با مطالعه منابعی که از اعداد کاتالان وجود دارد، مانند کتاب‌‌ها و صفحه ویکی‌پدیا، متوجه می‌شویم در ترکیبیات؛ دنباله این اعداد در بسیاری از مسائل شمارشی مانند مثلث‌بندی کردن یک چند ضلعی، پرانتزگذاری بین‌ $n$ متغییر، شمارش قله‌ها، مسیرهای مشبکه، دنباله‌های پرهیز و درخت‌های دودویی، به‌صورت بازگشتی ظاهر می‌گردد. این اعداد برای نخستین بار توسط ریاضیدان بلغاری اُوجِن چارلز کاتالان کشف شد و بعدها به این نام مشهور گردید. البته، تاریخ ریاضیات نشان می‌دهد که این اعداد خیلی قبل‌تر از کاتالان مورد بررسی قرار گرفته‌اند. این اعداد به شکل‌ها و صورت‌های متفاوتی ظاهر می‌گردند، اما کاربرد زیاد این اعداد در شاخه‌های مختلف ریاضی باعث شده حتی تصور اینکه اعداد کاتالان روزگاری ناشناخته و تعریف نشده بوده است، سخت باشد. در این مقاله، ابتدا ضریب دوجمله‌ای مرکزی را معرفی می‌کنیم و سپس به مطالعه بعضی از ساختار‌های مشهور اعداد کاتالان مانند مسیرهای دیک، درخت‌های دودویی، جایگشت‌ها و افراز‌ها، می‌پردازیم. ما همچنین بعضی از ساختار‌های جبری و دیگر اعداد کاتالان را نیز بررسی می‌کنیم.

کلیدواژه‌ها

موضوعات


[1] C. A. Athanasiadis, On noncrossing and nonnesting partitions for classical reflection groups, Electron. J. Combin., 5 (1998) 16 pp.
[2] A. Fink and B. Iriarte Giraldo, Bijections between noncrossing and nonnesting partitions for classical reflection groups, Port. Math., 67 no. 3 (2010) 369–401.
[3] D. A. Gewurz and F. Merola, Some factorisations counted by Catalan numbers, European J. Combin., 27 no. 6 (2006) 990–994.
[4] A. Granville and O. Ramaré, Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients, Mathematika, 43 no. 1 (1996) 73–107.
[5] D. M. Jackson, Counting cycles in permutations by group characters, with an application to a topological problem, Trans. Amer. Math. Soc., 299 no. 2 (1987) 785–801.
[6] D. E. Knuth, The art of computer programming, 1, Fasc. 1. MMIX, a RISC computer for the new millennium, Addison-Wesley, Upper Saddle River, NJ, 2005.
[7] C. Krattenthaler and Daniel Yaqubi, Some determinants of path generating functions, II, Adv. in Appl. Math., 101 (2018) 232–265.
[8] P. A. MacMahon, Combinatory analysis, I & II., American Mathematical Soc., 2001.
[9] T. Mansour, Counting peaks at height k in a Dyck path, J. Integer Seq., 5 no. 1 (2002) 9 pp.
[10] T. Mansour, Restricted 132-alternating permutations and Chebyshev polynomials, Ann. Comb., 7 (2003) 201–227.
[11] M. Bóna, Combinatorics of Permutations, With a foreword by Richard Stanley, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2004.
[12] R. An and J. Hou, Characterizations of Jordan †-skew multiplicative maps on operator algebras of indefinite inner product spaces, Chinese Ann. Math. Ser. B, 26 no. 4 (2005) 569–582.
[13] R. C. Mullin and R. G. Stanton, A map-theoretic approach to Davenport-Schinzel sequences, Pacific J. Math., 40 (1972) 167–172.
[14] P. Peart and W.-J. Woan, Dyck paths with no peaks at height k, J. Integer Seq., 4 no. 1 (2001) 6 pp.
[15] A. Sarőzy, On divisors of binomial coefficients, I, J. Number Theory, 20 no. 1 (1985) 70–80.
[16] R. P. Stanley, Enumerative combinatorics, 2, second edition, Cambridge University Press, Cambridge, 2011.
[17] R. P. Stanley, Catalan addendum to Enumerative Combinatorics, Available online at https://math.mit.edu/~rstan/ec/catadd.pdf, 2, 2011.
[18] R. P. Stanley, Parking functions and non-crossing partitions, Electron. J. Combin., 4 (1997) 14 pp.
[19] N. J. A. Sloane, The On-Line Encyclopaedia of Integer Sequences, oeis.org (2018).
[20] م. میرزاوزیری، شمردنی‌ها را بشمارید، انتشارات سخن‌گستر، 1386.