پرش به محتوا

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

از ویکی‌پدیا، دانشنامهٔ آزاد
توابع ترکیبی بر اساس توابع شمارشی.به این نوع توابع ها توابع نموداری نیز می گویند.

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

توابع مولد

[ویرایش]

از توابع مولد برای توصیف خانواده‌ای از اشیاء ترکیبی استفاده می‌شود. فرض کنید F خانواده‌ای از اشیا و F(x) تابع مولد آن باشد، بنابراین :
که تعداد اشیاء به اندازه n را نشان می‌دهد.

یونیون‌ها

[ویرایش]

برای دو خانوادهٔ ترکیبی مانند و با توابع مولد (G(x و (F(x، تابع مولد () برابر (F(x) + G(x خواهد بود.

جفت‌ها

[ویرایش]

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

دنباله‌ها

[ویرایش]

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

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

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

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

[ویرایش]

منابع

[ویرایش]