مسائل ترکیبیاتی زیادی را تاکنون مطالعه کردهاید. اگر باز هم دوست دارید این مسائل را حل کنید حتماً بخش‌های ذيل از سایت رشد را بخوانید:
http://olympiad.roshd.ir/computer/content/pdf/0017.pdf
تمام ماتریس‌های .gif)
را که ورودی‌های آن 1 یا 1- است درنظر بگیرید.
میخواهیم محاسبه کنیم در چند حالت از این ماتریسها حاصل‌ضرب عناصر در هر سطر و هر ستون برابر 1 است.
یک نکتهای كه در این مورد هست اين است که تعداد کل ماتریسها با این شرایط برابر تعداد کل ماتریس‌های .gif)
است كه ورودیهایشان فقط 1 و 1- است.
ماتریس‌های .gif)
را که ورودی‌های آن فقط 1 یا 1- است درنظر میگیریم.
سپس به ماتریس‌های .gif)
می‌رسیم که حاصل ضرب درایه‌های آن 1 است.
با اضافه کردن یک سطر و ستون، آیا تعداد این ماتریسها با هم برابر خواهد بود؟ (شكل 1)
|
شكل 1. |
با کمی دقت در ماتریس‌های فوق خواهید دید تعداد کل ماتریس‌های برابر تعداد ماتریس‌های است به‌طوري که حاصل‌ضرب درایه‌های آن در هر سطر و ستون آن برابر 1 باشد.
برای هر ماتریس که درایه‌های آن فقط 1و 1- است تنها یک ماتريس وجود دارد که علاوه بر اینکه درایه‌های آن فقط 1 و 1- است در هر سطر یا ستون حاصل‌ضرب درایه‌ها 1 خواهد بود.
برای اینکار باید یک سطر یا ستون به ماتریس اضافه شود؛ به این صورت که:
| - درایه‌های سطر آخر را که میخواهیم اضافه کنیم برابر حاصل‌ضرب سایر درایه‌ها در همان ستون
- و ستون آخر هم برابر حاصل‌ضرب درایه‌ها در همان سطر |
خواهد بود.بنابراین تعداد ماتریس‌های که درایه‌های آن فقط 1 و 1- است و در هر سطر یا ستون حاصل‌ضرب درایه‌ها 1 است با تعداد کل ماتریس‌های که درایه‌های آن فقط 1 و 1- است برابر بوده و از رابطه‌ي ذيل محاسبه خواهد شد: