در شکل روبهرو٬ ۵ عدد میخ مشاهده میکنید که با تعدادی کش به هم متصل شدهاند. به چند طریق میتوان ۵ تا از کشها را انتخاب کرد٬ به طوری که هر میخ٬ دقیقا به دو کش انتخاب شده وصل باشد؟
پاسخ
ابتدا کش $a$ که رسم نشدهاست را اضافه میکنیم و در نهایت تعداد حالتهایی که شامل کش $a$ هستند را از جواب کم میکنیم (متمم گیری). هر میخ باید به ۲ کش متصل باشد. برای انتخاب یکی از کشهای میخ ۱، ۴ حالت داریم. فرض کنیم سر دیگر کش، میخ $i$ باشد. از بین کشهایی که به $i$ وصلاند یکی انتخاب شده پس ۳ انتخاب وجود دارد و برای میخهای دیگر به همین ترتیب ۲ و ۱ انتخاب داریم. ترتیب انتخاب کشها اهمیتی ندارد پس کل حالتها را تقسیم بر ۲ میکنیم. بنابراین $\frac{4×3×2×1}{2}=12$ حالت برای انتخاب کشها وجود دارد.
کش $a$ در $۳×۲=۶$ تا از حالتها انتخاب شدهاست. (۳ انتخاب برای کش متصل به میخ ۳ و ۲ انتخاب برای کش متصل به ۴)
بنابراین به $۱۲-۶=۶$ راه میتوان کش انتخاب کرد.