# ترکیبیات

تعداد حالات ممکن برای نشستن $n$ بچه روی $n$ صندلی به شرطی که فاصله آنها حداکثر یک صندلی باشد

با ارقام 3,3,3,3,0,0,0,0 چند عدد زوج هشت رقمی می‌توان ساخت؟

دانشجویی هر روز بعد از کلاس درس به یکی از سه نوع بازی کامپیوتری می‌پردازد. به چند طریق می‌تواند هر روز بازی کند به طوری که در طول یک هفته‌ی تحصیلی هر یک از سه نوع بازی را حداقل یک بار انجام دهد؟

فرض کنید $f,g:{\mathrm{\mathbb{Z}}}^{+}\stackrel{}{\to }\mathrm{ℝ}$، $f\left(n\right)=n$ و $g\left(n\right)={\log }_2\left(n\right)$ برای $n\in {\mathrm{\mathbb{Z}}}^{+}$. نشان دهید که $g\in O\left(f\right)$ ولی $f\notin O\left(g\right)$.

اگر $g:{\mathrm{\mathbb{Z}}}^{+}\stackrel{}{\to }\mathrm{ℝ}$ و $c\in \mathrm{ℝ}$، تابع $cg:{\mathrm{\mathbb{Z}}}^{+}\stackrel{}{\to }\mathrm{ℝ}$ را بوسیله‌ی $\left(cg\right)\left(n\right)=c\left(g\left(n\right)\right)$، برای هر $n\in {\mathrm{\mathbb{Z}}}^{+}$ تعریف می‌کنیم. ثابت کنید که اگر $f,g:{\mathrm{\mathbb{Z}}}^{+}\stackrel{}{\to }\mathrm{ℝ}$ با $f\in O\left(g\right)$، آنگاه $f\in O\left(cg\right)$ به ازای $c\in {\mathrm{ℝ}}^{+}$، $c\ne 0$.

برای هر $n\in \mathrm{\mathbb{Z}}$، $n\ge 0$ ثابت کنید $2^{2n+1}+1$ بر $3$ و $n^3+{\left(n+1\right)}^3+{\left(n+2\right)}^3$ بر $9$ بخش‌پذیر هستند و $\frac{n^7}{7}+\frac{n^3}{3}+\frac{11n}{21}$ عددی صحیح است.

یک ردیف از $n$ صندلی داریم به طوری که روی هر کدام یک بچه نشسته است. هر بچه می‌تواند تا حداکثر یک صندلی تغییر مکان بدهد. تعداد آرایش‌های ممکن را بیابید.

 $n$ نفر در یک اتاق حضور دارند. ثابت کنید که در بین آنها حتما دو نفر پیدا می‌شوند که تعداد دوستانشان در این اتاق با هم برابر باشد.