به چند طریق می توان در خانه های یک جدول $۳ \times ۵ $ ستاره گذاشت طوری که در هر خانه حداکثر یک ستاره قرار بگیرد و در هر سطر و ستون ۱ یا ۲ ستاره قرار بگیرد؟
(راهنمایی: ابتدا سعی کنید حداقل و حداکثر تعداد ستاره هایی که می توانیم بگذاریم را بیابید. )
پاسخ
گزینهی «۱» درست است.
با توجه به راهنمایی سوال میفهمیم که برای اینکه در هر ستونی حداقل یک ستاره باشد باید حداقل 5 ستاره داشته باشیم از طرفی برای اینکه همه سطرها دو ستاره داشته باشند باید 6 ستاره داشته باشیم پس یا 5 ستاره داریم یا 6 ستاره. پس این دو حالت را جدا میکنیم و با اصل جمع تعداد کل حالت هارا بهدست می آوریم.
تعداد حالتها با 5 ستاره: ابتدا سطری را که قرار است در آن یک ستاره باشد را انتخاب میکنیم، سپس در آن یک ستاره میگذاریم و سپس در اولین سطر باقیمانده دو ستاره قرار میدهیم طوری که این دو ستاره با ستارهی قبل هم ستون نشوند و در نهایت در تنها سطر باقیمانده نیز به طور یکتا باید دو ستاره را قرار دهیم. پس میشود:
$\binom{3}{1}\times5\times\binom{4}{2}\times\binom{2}{2}$
حال برای 6 ستاره هم باید یکی از ستونها دو ستارهای شوند، پس ابتدا آن ستون را انتخاب میکنیم و در آن دو ستاره قرار میدهیم. سپس در سطری که ستارهای ندارد دو ستاره قرار میدهیم و در در دو سطر باقیمانده هم در هر سطر یک ستاره دیگر قرار میدهیم. پس میشود:
$\binom{5}{1}\times\binom{3}{2}\times\binom{4}{2}\times\binom{2}{1}\times\binom{1}{1}$
پس در کل 270 حالت میشود.