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