مبانی ترکیبیات. هفتهٔ اول. توابع با مقادیر صحیح – شمارش

توابع سقف و کف (قسمت اول)

توابع سقف و کف (قسمت دوم)

تابع ایورسون

شمارش (قسمت اول)

شمارش (قسمت دوم)

تمرین‌های هفتهٔ اول

۱. اگر $m$ عددی صحیح باشد، عبارت زیر را ثابت کنید و برای تعریف سقف، فرم مشابه را بدست آورده و ثابت کنید.
$$\begin{aligned}&\Big\lfloor\frac{m}{2}\Big\rfloor=\frac{m}{2}-\frac{1}{4}+\frac{(-1)^m}{4}\\[7pt]&\Big\lceil\frac{m}{2}\Big\rceil=?\end{aligned}$$

۲. اگر $x\geq0$ عددی حقیقی باشد، موارد زیر را ثابت کنید.
$$\begin{aligned}&\Big\lfloor\sqrt{\lfloor x\rfloor}\Big\rfloor=\Big\lfloor\sqrt{x}\Big\rfloor\\[7pt]&\Big\lceil\sqrt{\lceil x\rceil}\Big\rceil=\Big\lceil\sqrt{x}\Big\rceil\end{aligned}$$

۳. تعداد $m$زیرمجموعه‌های $[n]$ را که شامل هیچ دو عدد متوالی نیستند، محاسبه کنید.

۴. تعداد رشته‌های بیتی را به طول $8$ که شامل سه صفر متوالی و چهار یک متوالی هستند، به‌دست آورید.

۵. چند تابع از مجموعهٔ $\{1,2,3,\dots,n\}$ به مجموعهٔ‌ $\{0,1\}$ وجود دارد که در آن $n$ یک عدد صحیح مثبت است…
الف) که یک به یک باشند؟
ب) که صفر، هم به یک و هم به $n$ نسبت داده شود؟
ج) که به طور دقیق، $1$ به یکی از اعداد صحیح کمتر از $n$ نسبت داده شود؟