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

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

توابع ترکیبی بر اساس توابع شمارشی.به این نوع توابع ها توابع نموداری نیز می گویند.

توابع مولد

از توابع مولد برای توصیف خانواده‌ای از اشیاء ترکیبی استفاده می‌شود. فرض کنید 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». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲ جون ۲۰۱۷.