در سوال قبل، اگر به جای رنگ هر نهنگ، نام او (هم نام قاتل و هم نام مقتول) در لیست نوشته شود، چند لیست سیاه متفاوت میتواند وجود داشته باشد؟
پاسخ
گزینهی (۵) درست است.
فرض کنید $f(i,j)$ برابر با تعداد راههای نوشتن این دنباله از لحظهای که دقیقآ $i$ نهنگ سفید و $j$ نهنگ سیاه باقی مانده باشد است. داریم: $f(i,j)=f(j,i)$، $f(1,i)=2\times i!$ و با حالتبندی روی رنگ اولین مقتول، برای هر $2\le i,j$ داریم: $f(i,j)=(f(i,j-1)+f(i-1,j))\times i \times j$ بدین ترتیب $f(2,2)=32$، $f(2,3)=264$، $f(2,4)=2496$، $f(3,3)=4752$، $f(3,4)=86976$ خواهد بود و نهایتا جواب ما یعنی $f(4,4)$ برابر با ۲۷۸۳۲۳۲ می شود.