اتحاد پاسکال

در ریاضیات، اتحاد پاسکال یک همانی ترکیبیاتی در مورد ضریب دوجمله‌ای است. بنابر اتحاد پاسکال، به‌ازای هر عدد طبیعی n

${n-1 \choose k}+{n-1 \choose k-1}={n \choose k}\quad$

به‌ازای $1\leq k\leq n$

که در آن ${n \choose k}$ یک ضریب دوجمله‌ای است. نوشتن این اتحاد به صورت زیر هم رایج است:

${n \choose k}+{n \choose k-1}={n+1 \choose k}\quad$

به‌ازای $1\leq k\leq n+1$

اثبات ترکیبیاتی

اثباتی شهودی برای این اتحاد وجود دارد. یادآوری می‌شود که ${n \choose k}$ تعداد حالت‌هایی است که می‌توان از مجموعه‌ای n تایی، k چیز برداشت. یک عضو دلبخواهی از مجموعه به عنوان X جدا می‌شود. حال هر بار که زیرمجموعه‌ای k تایی از مجموعه برداشته شود، X یا عضو این زیر مجموعه است یا عضو این زیرمجموعه نیست. اگر X عضو زیر مجموعه باشد، با کنار گذاشتن آن تعداد حالت‌ها برابر ${n-1 \choose k-1}$ می‌شود. اگر X عضو زیرمجموعه نباشد با کنار گذاشتن آن تعداد حالت‌ها برابر ${n-1 \choose k}$ است. از آنجا که حالت دیگری ممکن نیست (X یا در زیرمجموعهٔ kتایی هست یا در آن نیست) پس

${n-1 \choose k-1}+{n-1 \choose k}={n \choose k}$

اثبات جبری

قصد بر این است که ثابت شود:

${n \choose k}+{n \choose k-1}={n+1 \choose k}.$

${\begin{aligned}{n \choose k}+{n \choose k-1}&={\frac {n!}{k!(n-k)!}}+{\frac {n!}{(k-1)!(n-k+1)!}}\\&=n!\left[{\frac {n-k+1}{k!(n-k+1)!}}+{\frac {k}{k!(n-k+1)!}}\right]\\&={\frac {n!(n+1)}{k!(n-k+1)!}}={\binom {n+1}{k}}\end{aligned}}$

تعمیم

اگر $n,k_{1},k_{2},k_{3},\dots ,k_{p},p\in \mathbb {N} ^{*}$ و $n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}$ . آنگاه:

${\begin{aligned}&{}\quad {n-1 \choose k_{1}-1,k_{2},k_{3},\dots ,k_{p}}+{n-1 \choose k_{1},k_{2}-1,k_{3},\dots ,k_{p}}+\cdots +{n-1 \choose k_{1},k_{2},k_{3},\dots ,k_{p}-1}\\&={\frac {(n-1)!}{(k_{1}-1)!k_{2}!k_{3}!\cdots k_{p}!}}+{\frac {(n-1)!}{k_{1}!(k_{2}-1)!k_{3}!\cdots k_{p}!}}+\cdots +{\frac {(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots (k_{p}-1)!}}\\&={\frac {k_{1}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}+{\frac {k_{2}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}+\cdots +{\frac {k_{p}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={\frac {(k_{1}+k_{2}+\cdots +k_{p})(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}\\&={\frac {n(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={\frac {n!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}.\end{aligned}}$

جستارهای وابسته

مثلث خیام

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Pascal's rule». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۷ دسامبر ۲۰۱۸.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.