اتحادهای ترکیبیاتی، تساویها و فرمولهای مهم و پرکاربرد ترکیبیاتی هستند که تسلط به آنها لازمهی حل بسیاری از مسائل شمارشی-ترکیبیاتی است.
این اتحاد از مهمترین و پرکاربردترین اتحادهای ترکیبیاتی است. صورت اتحاد پاسکال: \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}