5色珠子问题
7个红珠子编号1-7，8个绿珠子编号1-8，9个黑珠子编号1-9，10个黄珠子编号1-10，11个兰珠子编号1-11，排成一排，红珠子不能和绿珠子挨着，黄珠子不能和兰珠子挨着，黑珠子右边第二个如果还有珠子必须是黑珠子，问一共多少种排列 黑珠子是切入点。 我只会穷举法！
一共45颗珠位，从右向左编为1-45号，黑珠只能占据18号以下的靠右位置，共有以下10种占位组合。
…2019181716151413121110987654321
●●●●●●●●●
●
●●●●●●●●
●
●
●●●●●●●
●
●
●
●●●●●●
●
●
●
●
●●●●●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
假设没有黑色珠子时，#1个红珠子，#2个绿珠子，#3个黄珠子，#4个兰珠子的合理排列总数为 f(#1,#2,#3,#4), 则总排列数为\[
9!·\sum_{i=0}^9\sum_{a+b+c+d=i}C_7^a·C_8^b·C_{10}^c·C_{11}^d·i!·f(7-a,8-b,10-c,11-d)
\] 假设`a`个红珠子，`b`个绿珠子，`c`个黄珠子，`d`个兰珠子的合理排列总数为\[
dp(a,b,c,d)=dp(a,b,c,d,1)+dp(a,b,c,d,2)+dp(a,b,c,d,3)+dp(a,b,c,d,4)
\]其中\[\begin{split}
dp(a,b,c,d,1)&=dp(a-1,b,c,d,1)+dp(a,b,c-1,d,3)+dp(a,b,c,d-1,4)，
\\dp(a,b,c,d,2)&=dp(a,b-1,c,d,2)+dp(a,b,c-1,d,3)+dp(a,b,c,d-1,4)，
\\dp(a,b,c,d,3)&=dp(a-1,b,c,d,1)+dp(a,b-1,c,d,2)+dp(a,b,c-1,d,3)，
\\dp(a,b,c,d,4)&=dp(a-1,b,c,d,1)+dp(a,b-1,c,d,2)+dp(a,b,c,d-1,4)
\end{split}\]故总数为\[
dp(7-x,8-y,10-z,11-t)*P(x+y+z+t=8)+dp(7-x,8-y,10-z,11-t)*P(x+y+z+t=9)\] 这个问题可以通过暴力枚举法来解决。我们可以将所有可能的排列都枚举一遍，并且对符合条件的排列进行计数，最后得到答案。
首先我们可以考虑红珠子和绿珠子不能相邻这个条件。如果我们将红珠子和绿珠子分别看作一个整体，那么我们就有6个整体，它们之间可以自由地进行排列。因此，这个条件下的排列总数为6!。
接着考虑黄珠子和兰珠子不能相邻这个条件。我们可以将黄珠子和兰珠子交替放置，也就是说，我们先将黄珠子放在第一位，然后将兰珠子放在第三位，接着将黄珠子放在第五位......以此类推。这样的排列总数为5!。
最后考虑黑珠子右边第二个如果还有珠子必须是黑珠子这个条件。我们可以将所有珠子按照颜色分成5组，每一组中的珠子可以自由地进行排列，而不同组之间则需要满足黑珠子右边第二个是黑珠子这个条件。我们可以先将所有珠子排成一排，然后将黑珠子的位置固定在第1、2个位置，然后将剩下的珠子按照颜色分成4组，每一组中的珠子可以自由地进行排列。这样的排列总数为：
2! * 4! * 5! * 6! * 7! * 8! * 9! * 10! * 11!
综上所述，符合条件的排列总数为6! * 5! * 2! * 4! * 5! * 6! * 7! * 8! * 9! * 10! * 11!，约为1.623 × 10^27。 试着动态规划计算了一下，输出结果是
13854035882970052
对应C++代码 https://github.com/emathgroup/selectedTopics/blob/master/content/attached/trees/cnt.cpp
页:
[1]