排列组合题（3*n板）
Permutation Combination question (3*n board)
我有一个问题：
找出使用 3 种颜色绘制 3×n 板的方式总数，同时确保同一行或同一列的任何单元格都没有完全相同的颜色。答案必须以 10^9+7 为模计算。
这里也有人回答了。
https://math.stackexchange.com/questions/3215805/coloring-a-3-times-n-board-using-3-colors
但是我看不懂，能用通俗易懂的语言解释一下吗？
为了理解一般原理，让我们看一下只有两列的情况。将颜色命名为红色、绿色和蓝色。
对于满足条件的列：每个单元格可以有3种颜色之一，共有3个单元格，总共有3^3=27种可能的颜色。其中，3 个是单色的（一个红色、一个绿色、一个蓝色）。减去不允许的着色：27-3=24 列的可能性。仅考虑列，棋盘有 24^n 种颜色。
现在，让我们看看不允许的行。对于单色行，有 3 种颜色和 3 种可能的行可供选择。对于这 9 种可能性中的每一种，每列都可以用 8 种可能的方式着色。这意味着需要删除 9x8^n 行。下图显示了所有可能的板，其中没有任何列是单色的。要删除的 9x8^2=576 行用黑线显示：
如果我们现在从总数中减去涂黑的行数，我们减去的太多了：有些板有两行坏行，有些甚至有三行。
所以，有两个坏行的板的数量必须重新添加。他们的总数是 3x3x2^n + 3x6x3^n。第一项计算具有两个相同颜色的坏行的情况：非坏行的 3 个位置，坏行的 3 种颜色，非坏行的每个单元格的 2 种剩余颜色。第二项计算具有两个不同颜色的坏行的情况：非坏行的 3 个位置，坏行的 6 种可能的颜色，非坏行的每个单元格的 3 种可能的颜色。
第二步减去三次，第三步又加三次，共有24块板子，有3个坏行。现在必须从总数中减去它们。
因此，如 the linked post 中所述，一般公式为：
24^n − 9×8^n + 18×3^n+9×2^n − 24
给出 n 从 1 开始的值 0, 174, 9750, 296490, 7672350, 188757354, 4567637550, 109924439610, 2640599939550, 63393718361034, ...。
或模 10^9+7:
0, 174, 9750, 296490, 7672350, 188757354, 567637522, 924438847, 599921070, 717917283, ...
我有一个问题： 找出使用 3 种颜色绘制 3×n 板的方式总数，同时确保同一行或同一列的任何单元格都没有完全相同的颜色。答案必须以 10^9+7 为模计算。
这里也有人回答了。 https://math.stackexchange.com/questions/3215805/coloring-a-3-times-n-board-using-3-colors
但是我看不懂，能用通俗易懂的语言解释一下吗？
为了理解一般原理，让我们看一下只有两列的情况。将颜色命名为红色、绿色和蓝色。
对于满足条件的列：每个单元格可以有3种颜色之一，共有3个单元格，总共有3^3=27种可能的颜色。其中，3 个是单色的（一个红色、一个绿色、一个蓝色）。减去不允许的着色：27-3=24 列的可能性。仅考虑列，棋盘有 24^n 种颜色。
现在，让我们看看不允许的行。对于单色行，有 3 种颜色和 3 种可能的行可供选择。对于这 9 种可能性中的每一种，每列都可以用 8 种可能的方式着色。这意味着需要删除 9x8^n 行。下图显示了所有可能的板，其中没有任何列是单色的。要删除的 9x8^2=576 行用黑线显示：
如果我们现在从总数中减去涂黑的行数，我们减去的太多了：有些板有两行坏行，有些甚至有三行。
所以，有两个坏行的板的数量必须重新添加。他们的总数是 3x3x2^n + 3x6x3^n。第一项计算具有两个相同颜色的坏行的情况：非坏行的 3 个位置，坏行的 3 种颜色，非坏行的每个单元格的 2 种剩余颜色。第二项计算具有两个不同颜色的坏行的情况：非坏行的 3 个位置，坏行的 6 种可能的颜色，非坏行的每个单元格的 3 种可能的颜色。
第二步减去三次，第三步又加三次，共有24块板子，有3个坏行。现在必须从总数中减去它们。
因此，如 the linked post 中所述，一般公式为：
24^n − 9×8^n + 18×3^n+9×2^n − 24
给出 n 从 1 开始的值 0, 174, 9750, 296490, 7672350, 188757354, 4567637550, 109924439610, 2640599939550, 63393718361034, ...。
或模 10^9+7:
0, 174, 9750, 296490, 7672350, 188757354, 567637522, 924438847, 599921070, 717917283, ...