====== اتحادهای ترکیبیاتی ======
اتحادهای ترکیبیاتی، تساوی‌ها و فرمول‌های مهم و پرکاربرد ترکیبیاتی هستند که تسلط به آن‌ها لازمه‌ی حل بسیاری از مسائل شمارشی-ترکیبیاتی‌ است.

===== اتحاد پاسکال =====
این اتحاد از مهم‌ترین و پرکاربردترین اتحادهای ترکیبیاتی است. صورت اتحاد پاسکال:
$$\binom{n-1}{r-1} + \binom{n-1}{r} = \binom{n}{r}$$
تمرین. اتحاد پاسکال را ثابت کنید.
<پاسخ>

$$\binom{n-1}{r-1} + \binom{n-1}{r} = \frac{(n-1)!}{(r-1)! (n-r)!} + \frac{(n-1)!}{r! (n-r-1)!} =
\\
\frac{r (n-1)!}{r! (n-r)!} + \frac{(n-r) (n-1)!}{r! (n-r)!} = \frac{(n-r+r) (n-1)!}{r! (n-r)!} = 
\\
\frac{n!}{r! (n-r)!} = \binom{n}{r}
$$
</پاسخ>

تمرین ۲. این اتحاد را با استفاده از روش دوگانه‌شماری اثبات کنید.

===== اتحاد چوشی - چی =====
$$\binom{k}{k} + \binom{k+1}{k} + ... + \binom{n}{k} = \sum \limits_{r=k}^{n} \binom{r}{k} = \binom{n+1}{k+1}$$

تمرین. این اتحاد را اثبات کنید.

<پاسخ>
از اتحاد پاسکال داریم:
$$\binom{n-1}{r-1} + \binom{n-1}{r} = \binom{n}{r}$$

بنابراین:
$$\binom{n-1}{r-1} = \binom{n}{r} - \binom{n-1}{r} \Longrightarrow  \binom{r}{k} = \binom{r+1}{k+1} - \binom{r}{k+1} \Longrightarrow
\\
\sum \limits_{r=k}^{n} \binom{r}{k} = \sum \limits_{r=k}^{n} \binom{r+1}{k+1} - \binom{r}{k+1} = 
\\
-\binom{k}{k+1} + \binom{k+1}{k+1} - \binom{k+1}{k+1} + \binom{k+2}{k+1} - \binom{k+2}{k+1} + \binom{k+3}{k+1} - \ ... 
\\
- \binom{n}{k+1} + \binom{n+1}{k+1} = \binom{n+1}{k+1} - \binom{k}{k+1} = \binom{n+1}{k+1} - 0 = \binom{n+1}{k+1}$$

</پاسخ>



===== صورت دوم اتحاد چوشی - چی =====
$$\binom{k}{0} + \binom{k+1}{1} + ... + \binom{k+n}{k} = \sum \limits_{r=0}^{n} \binom{k+r}{k} = \binom{n+k+1}{n}$$

تمرین. فرمول بالا را اثبات کنید.

<پاسخ>
طبق اتحاد چوشی - چی:
$$\sum \limits_{r=0}^{n} \binom{k+r}{k} = \sum \limits_{r=0}^{n} \binom{k+r}{r} = \sum \limits_{r=k}^{n+k} \binom{r}{k} = \binom{n+k+1}{k+1} = \binom{n+k+1}{n}$$
</پاسخ>


===== اتحاد واندرموند =====
برای اعداد طبیعی $n, m, k$: 
$$\sum \limits_{i=0}^{k} \binom{m}{i} \binom{n}{k-i} = \binom{n+m}{k}$$

تمرین. اتحاد بالا را اثبات کنید.

<پاسخ>
اثبات با دوگانه شماری:

مساله: مدرسه‌ای دو کلاس دارد. کلاس اول $m$ و کلاس دوم $n$ دانش‌آموز دارد. به چند طریق می‌توانیم از بین دانش‌آموزان این دو کلاس $k$ نفر را برای گروه سرود انتخاب کنیم؟

راه حل اول: اگر $i$ نفر از کلاس اول انتخاب شوند: به $\binom{m}{i}$ طریق این $i$ دانش‌آموز و به $\binom{n}{k-i}$ طریق $k-i$ نفر دیگر را از کلاس دوم انتخاب می‌کنیم. پس طبق اصل جمع،‌ جواب مساله برابراست با:
$$\sum \limits_{i=0}^{k} \binom{m}{i} \binom{n}{k-i}$$

راه حل دوم: می‌خواهیم $k$ نفر از بین $n+m$ نفر انتخاب کنیم. تعداد راه‌های انجام این کار برابراست با:‌ $\binom{n+m}{k}$

پس:
$$\sum \limits_{i=0}^{k} \binom{m}{i} \binom{n}{k-i} = \binom{n+m}{k}$$

</پاسخ>

===== نتیجه‌ی اتحاد واندرموند =====

$$\sum \limits_{i=0}^{n} {\binom{n}{i}}^2 = \binom{2n}{n}$$

تمرین. فرمول بالا را اثبات کنید.

<پاسخ>
در اتحاد واندرموند اگر قرار دهیم $n = m = k$:
$$\sum \limits_{i=0}^{k} \binom{m}{i} \binom{n}{k-i} = \binom{n+m}{k} \Longrightarrow \sum \limits_{i=0}^{k} \binom{n}{i} \binom{n}{i} = \binom{2n}{n}$$

</پاسخ>