ترکیبیات شمارشی

ترکیبیات شمارشی شاخه‌ای از ترکیبیات است که با شمارش تعداد حالت‌های ایجاد یه قالب سر و کار دارد. به عبارت کامل تر هدف این شاخه پیدا کردن تابعی برای محاسبه تعداد اعضای مجموعهٔ نامتنهی از مجموعه‌های متنهی است. ساده‌ترین نوع این توابع، توابع بسته هستند که به صورت ترکیبی از توابع اولیه (فاکتوریل، توان و …) قابل نمایش هستند.

توابع مولد

از توابع مولد برای توصیف خانواده‌ای از اشیاء ترکیبی استفاده می‌شود. فرض کنید F خانواده‌ای از اشیا و F(x) تابع مولد آن باشد، بنابراین : $F(x)=\sum _{n=0}^{\infty }f_{n}x^{n}$
که $f_{n}$ تعداد اشیاء به اندازه n را نشان می‌دهد.

یونیون‌ها

برای دو خانوادهٔ ترکیبی مانند ${\mathcal {G}}$ و ${\mathcal {F}}$ با توابع مولد (G(x و (F(x، تابع مولد ( ${\mathcal {F}}\cup {\mathcal {G}}$ ) برابر (F(x) + G(x خواهد بود.

جفت‌ها

برای دو خانوادهٔ ترکیبی مانند بالا، تابع مولد خانوادهٔ حاصل از ضرب کارتزین این دو ( ${\mathcal {F}}\times {\mathcal {G}}$ ) برابر (F(x)G(x خواهد بود.

دنباله‌ها

دنباله‌ها حالت کلی تری از جفت‌ها هستند. دنباله‌ها ضرب‌های دلخواه یه خانوادهٔ ترکیبی با خودش است. به شکل رسمی:

{\mbox{Seq}}({\mathcal {F}})=\epsilon \ \cup \ {\mathcal {F}}\ \cup \ {\mathcal {F}}\times {\mathcal {F}}\ \cup \ {\mathcal {F}}\times {\mathcal {F}}\times {\mathcal {F}}\ \cup \cdots

توضیح فرمول: یک دنبالهٔ خالی یا دنبالهٔ یک عنصر یا دنبالهٔ دو عنصر یا …

تابع مولد به شکل زیر خواهد بود:

1+F(x)+[F(x)]^{2}+[F(x)]^{3}+\cdots ={\frac {1}{1-F(x)}}

جستارهای وابسته

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Enumerative combinatorics». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲ جون ۲۰۱۷.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.