عنوان پایان‌نامه
بررسی برخی خانواده های کاتالان درختها و الگوریتم ها یمرتبط
- رشته تحصیلی
- علوم کامپیوتر
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 4447;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 48058
- تاریخ دفاع
- ۲۸ شهریور ۱۳۸۹
- دانشجو
- عاطفه عبداله زاده زارع
- استاد راهنما
- مرتضی محمدنوری
- چکیده
- اعداد کاتالان دنباله شناخته¬شده¬ای در ریاضیات بوده و بصورت C_n=1/(n+1) (2n¦n) تعریف می¬شوند. بسیاری از مسائل شمارشی در خانواده کاتالان قرار گرفته و اثبات می¬شود پاسخ کلیه این مسائل متناظر با¬ اعدادکاتالان است. در این پایان¬نامه خانواده¬های کاتالان مورد بررسی قرار می¬گیرند. این مسائل دارای تعمیمات متعددی بوده و ارتباط این مسائل با اعداد k-کاتالان نیز اثبات شده است. تعریف اعداد k-کاتالان بصورت C_n^k=1/(kn+1) ((kn+1)¦n) است. علاوه بر این مسائل جدیدی نیز مطرح شده که در خانواده کاتالان قرار گرفته و پاسخ آن¬ها متناظر با اعداد k-کاتالان است. یکی از مسائل جدیدی که در این حوزه معرفی شده، تبیین ارتباط شی ترکیبیاتی کاشی¬کاری پلکانی با اعداد k-کاتالان است. ارتباط این شی با اعداد k-کاتالان از طریق تناظر با درختان k-تایی صورت می¬گیرد. در این پایان¬نامه روشی جهت کدگذاری شی ترکیبیاتی کاشی¬کاری پلکانی بیان شده و علاوه بر آن الگوریتم¬های جدیدی برای تولید، رتبه¬گذاری و رتبه¬گشایی این شی ارائه گردیده¬است. تبیین ارتباط اعداد کاتالان با چندجمله¬ای¬های هوک واثبات این¬که این چندجمله¬ای¬ها برای درختان m-تایی و جنگل¬های مسطح بصورت عبارت ساده¬ای بر حسب ضرایب دو جمله¬ای قابل ارائه هستند، مطالب دیگری از این پایان¬نامه را تشکیل می¬دهند. واژه¬های کلیدی: خانواده کاتالان، کاشی¬کاری پلکانی، چندجمله¬ای¬های با طول هوک
- Abstract
- In the thesis, the family of the Catalan numbers is examined. The Catalan numbers is the famous sequence in the mathematics world and many of the counting problems are related to it. In the first chapter, the basic concepts and definitions used in other chapters are proposed. In chapter 2, the problems related to Catalan numbers are introduced and proved that the answer of all these problems, are the Catalan numbers. Investigating the extension of these problems and also describing the new problems are followed in this chapter; Expressing relation of those problems with k-Catalan is the another part in this chapter. In the third chapter, the combinatorial object of Staircase Tiling is described in details and proved its bijection with k-ary trees and Catalan numbers. In the forth chapter, a method for coding this object with new algorithms for generation, ranking and unranking this object is proposed. Describing relation of Catalan number with hook polynomial is followed in this chapter. And also hook polynomial for k-ary forests and plane tree is expressed. KeyWords: Family catalan, Staircase tiling Object, Hook length polynomials
