如何使用3个有效值计算NxM网格的不同组合

Question

我有3个有效值：a、b、c 我可以将它们插入Nx3网格，这样就不会有行或列包含相同值的单元格。如何计算可以使用N行创建的有效模式数

例如，如果N=4，则有效模式的总数为296490。

这是我的尝试：

def countPatterns(n):

    dp1, dp2 = 6,6
    mod = 10 ** 9 + 7
    
    for i in range(2, n+1):
        dp1, dp2 = (dp1 * 3 + dp2 * 2) % mod, (dp1 * 2 + dp2 * 2) % mod
    return (dp1 + dp2) % mod

当N=4时，输出应该是174，但我得到54

Answer 1

简短回答

这也可以通过数学方法解决，因此公式为：

24ⁿ-（9*8ⁿ-9*2ⁿ-18*3ⁿ+24）

def countPatterns(n):
    result = 24**n - (9 * 8**n - 9*2**n - 18*3**n + 24)
    mod = 10 ** 9 + 7
    return result % mod

print (countPatterns(4)) 

296490

长话短说

一,。条件：没有行包含相同的值

对于给定的行，有3 种方法可以在每个单元格中设置颜色。因此，有3个3个=27个可能的组合。然而，在这些27组合中，3是GGG、BBB和RRR。因此，必须排除它们，并且一行中的有效组合数为27 - 3 = 24

因此，具有n行的表的组合总数为24ⁿ

二,。条件：没有列包含相同的值

为了解决这种情况，我们可以计算所有“无效组合”，然后从总数中减去它们的数目（如前一节所述，总数为24ⁿ）

2.1无效组合

1. 只有第一列具有相同的值
2. 只有第二列具有相同的值
3. 只有第三列具有相同的值
4. 只有前两列具有相同的值（第一列的值不一定等于另一列）
5. 只有最后两列具有相同的值
6. 只有第一列和最后一列具有相同的值
7. 每列中的值相等

显然，1的组合数等于2和3。关于4、5和6也可以注意到这一点

如果我们把从1到7的组合求和，那么我们将得到总数

但是，很难单独计算（1）-（7），但更容易计算组合的数量，以便至少k列具有相同的值。一旦找到这些，我们将应用inclusion-exclusion principle来查找问题中提出的组合数

2.1.1第一列具有相同的值

对于每一行，都有8组合，使得该行以R开头：

RRG
RRB
RGR
RGG
RGB
RBR
RBG
RBB

这意味着对于具有n的表，有8个组合，其中第一列由8组成。其中，存在3×8ⁿ组合，使得第一列从R、G或B开始

现在，重要的是要认识到，这个数字表示4无效案例1、4、6和7（所有包含第一列的列集）

2.1.2第二列具有相同的值

基本上，我们可以使用与上面相同的逻辑来实现它也是3*8ⁿ

这表示2、4、5和7

2.1.3第三列具有相同的值

与之前相同-3*8ⁿ

这包括{}、{}、{}和{}

如果我们将这些3步骤的组合相加，我们将得到9*8ⁿ。然而，正如在这些步骤中所指出的，我们将对4、5和6进行两次计数7将被计数三次

2.1.4 2列具有相同的值

让我们为2第一列计算它，因为每对列的数量仍然相同

如果一行以2相同颜色开头，则每种颜色都有2组合。如果不是，则每对都有3个组合（有6个可能的对）。因此，组合的总数是3*2ⁿ+6*3ⁿ

因此4和7的组合数是3*2ⁿ+6*3ⁿ

{}和{}的组合数为3*2ⁿ+6*3ⁿ

6和7的组合数为3*2ⁿ+6*3ⁿ

2.1.5每列中的值等于

这意味着所有行必须相等。因为只有24在构造行的方法中，有24种方法可以使列中的所有值相等。所以，它是24

无效个案总数

如前所述，如果我们将2.1.1、2.1.2和2.1.3相加，那么我们将计算4、5和6两次，7-3次（从2.1）。由于每对列的组合数相同，我们只需减去3*2ⁿ+6*2ⁿ3次（从2.1.4开始），然后将三列的组合数相加一次（因为减法后不会出现）

9*8ⁿ-3*（3*2ⁿ+6*3ⁿ）+24=9*8ⁿ-9*2ⁿ-18*3ⁿ+24

三,。最终答案

现在，只需从24例中减去无效病例数：

24ⁿ-（9*8ⁿ-9*2ⁿ-18*3ⁿ+24）

不要忘记在最后应用10⁹+7的模运算

Answer 2

这可以用组合学的标准技术来解决

import math


# Counts the number of grids where the first i rows and first j columns are
# monochrome. All of the monochrome rows and columns must have the same color if
# and only if both i and j are nonzero. Otherwise, the color choices are
# independent.
def count_monochrome(n, i, m, j):
    return 3 ** (1 if i and j else i + j) * 3 ** ((n - i) * (m - j))


# Uses inclusion-exclusion to count the number of grids with no monochrome row
# or column.
def count(n, m=3):
    # There are math.comb(n, i) * math.comb(m, j) intersections with i
    # monochrome rows and j monochrome columns.
    return sum(
        math.comb(n, i)
        * math.comb(m, j)
        * (-1) ** (i + j)
        * count_monochrome(n, i, m, j)
        for i in range(n + 1)
        for j in range(m + 1)
    ) % (10 ** 9 + 7)


print(count(4))