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

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

یونیون‌ها

برای دو خانوادهٔ ترکیبی مانند ${\displaystyle \mathcal{G}}$

جفت‌ها

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

دنباله‌ها

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

${\displaystyle \text{Seq}(\mathcal{F})=ϵ\cup \mathcal{F}\cup \mathcal{F}\times \mathcal{F}\cup \mathcal{F}\times \mathcal{F}\times \mathcal{F}\cup \cdots }$

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

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

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

• لم برنساید
• نظریه بازی‌های ترکیبیاتی