象棋材料组合个数的一种简便计算方法

Question

在国际象棋中，一个棋手可以有不同的材料组合，例如：

“1个王后、2个公鸡、2个骑士、2个主教、8个爪牙+国王”是一个组合

如果玩家失去一个主教：

“1个王后2个公鸡2个骑士1个主教8个爪牙+国王”是另一种组合

..之后，如果一个棋子被提升为骑士，那么：

“5个王后，5个公鸡，5个骑士，5个主教，2个爪牙+国王”

因为你没有可以提升的棋子。（5个皇后=需要4个棋子）（5个公鸡=需要3个棋子）等等，所以4+3+3+3=13个棋子需要。既然棋盘上有2个典当，那么最多也就能提升6个典当。无效。

有多少个有效的材料组合？我使用下面的C代码计算了8694个组合。问题是：

你找到更简单/有效的算法来计算它吗？（更少的循环，更少的计算，更清晰的代码，等等）...甚至是一个数学公式？？

total = 0;
for (queens=0;queens<=9;queens++)
for (rooks=0;rooks<=10;rooks++)
for (bishops=0;bishops<=10;bishops++)
for (knights=0;knights<=10;knights++)
for (pawns=0;pawns<=8;pawns++)
{
    pawnsRequested = 0;
    if (queens>1) pawnsRequested += queens - 1;
    if (rooks>2) pawnsRequested += rooks - 2;
    if (bishops>2) pawnsRequested += bishops - 2;
    if (knights>2) pawnsRequested += knights - 2;
    if (8-pawns < pawnsRequested) continue;
    total++;
}
printf("%i\n",total); 

Answer 1

如果棋子的类型是独立的，那么我们可以乘以：10种可能的皇后乘以11种可能的雄鸡乘以等，我们需要跟踪典当的使用，然而。有一种叫做生成函数的数学技巧，我们可以把它的可能性编码为

3 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8,

其中x的幂次表示使用的棋子数，系数表示可能性数。这里有三种可能不需要提升的典当(0，1，2)，一种可能需要一个提升的典当(3)，一种可能需要两个提升的典当（4）等等，现在我们可以将其中的每一个因素乘在一起（分别是，女王、雄鸡、主教、骑士、典当）。

  (2 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)
* (3 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)
* (3 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)
* (3 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)
* (1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)

这是Wolfram Alpha写的。

1到x^8的系数，即0到8所需典当的可能性数，为54、135、261、443、693、1024、1450、1986、2648，相加为8694。