اتحاد وندرموند

قضیه ۳ اتحاد وندموند فرض کنید r , n ,m اعداد صحیح نامنفی بوده و r کوچکتر مساوی از n , m است. آنگاه:

شکل شماره ۱

تذکر: این اتحاد توسط ریاضی‌دان الکساندر-توفیل وندرموند در قرن هجدهم کشف شد.

اثبات: فرض کنید m عنصر در یک مجموعه و n عنصر در مجموعه دوم وجود داشته باشد. آنگاه تعداد روش‌هایی که می‌توان r عنصر را از اجتماع این مجموعه‌ها انتخاب کرد، برابر است با (شکل ۲)

روش دیگر برای انتخاب r عنصر از اجتماع این مجموعه‌ها این است که k عنصر از مجموعه اول و r-k عنصر از مجموعه دوم برداشته شود که k یک عدد صحیح ۰≤k≤r است.

با استفاده از اصل ضرب، این کار را می‌توان به (شکل ۳)  روش انجام داد.

بنابراین این تعداد روش‌های انتخاب r عنصر از اجتماع، همچنین برابر است با:

(شکل ۴)

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

نتیجه ۴ از اتحاد وندرموند نتیجه می‌شود.

نتیجه ۴ اگر n یک عدد صحیح نامنفی باشد، آنگاه:

(شکل ۵)

اثبات: از اتحاد وندرموند با m=r=n استفاده کرده و بدست می‌آوریم:

(شکل ۶)

تساوی آخر با استفاده از رابطه (شکل ۷) به دست آمده‌است.

همان‌طور که اثبات قضیه ۴ نشان خواهد داد، اتحادهای ترکیبیاتی را می‌توان با شمارش رشته‌های بیتی با خصوصیات مختلف نیز بدست آورد.

قضیه ۴ فرض کنید r , n اعداد صحیح نامنفی با r≤n هستند. آنگاه:

(شکل ۸)

اثبات: از اثبات ترکیبیاتی استفاده می‌کنیم. طبق مثال ۱۴ از بخش ۵–۳، سمت چپ رابطه، (شکل ۹) ، تعداد رشته‌های بیتی با طول n + 1 که شامل r + 1 بیت یک هستند را می‌شمارد.

با در نظر گرفتن مکان‌های ممکن آخرین بیت ۱ در رشته‌ای با r+1 بیت یک، نشان می‌دهیم که طرف راست نیز همان اشیاء را می‌شمارد.

آخرین بیت یک باید در مکان‌های r+1 , r+2 , … یا n+1 ظاهر شود. به علاوه اگر آخرین بیت یک، k امین بیت باشد، باید r بیت یک، در بین اولین k-1 مکان قرار گیرند.

در نتیجه طبق مثال ۱۴ از بخش ۵–۳، تعداد چنین رشته‌هایی برابر (شکل ۱۰)  است.

با محاسبه مجموع برای kهای r+1≤k≤n+1، به دست می‌آوریم که

(شکل ۱۱)

رشته بیتی با طول n شامل دقیقاً r+1 بیت یک وجود دارد. (توجه کنید که آخرین جمله اثبات، با تغییر مغیر j=k-1 نتیجه می‌شود. (

چون سمت چپ و راست هر دو اشیاء یکسانی را می‌شمارند، با هم برابرند. این اثبات را تماس می‌کند.

منابع 

ریاضیات گسسته / تألیف کنت. اچ. روزن

اتحادهای ریاضی
مقاله‌های ایجاد شده توسط ایجادگر
موضوعات فاکتوریل و دوجمله‌ای
ویکی‌سازی رباتیک