计算重复和限制的排列

Question

我想计算具有重复且只有 3 个不同符号 0,1,2 的排列，并且没有 0 直接跟在 1 之后的限制。

示例：

有效：01202212

无效：10...

我虽然计算了这些排列子集是 (3^count(0))*(2^count(1))*(3^count(2)) 但这是错误的。如果不是，我如何计算 exakt 计数？

Answer 1

很明显：
- 长度为 K 以 1 结尾的有效序列可以组成
向任何长度为 K-1

的有效序列加 1

-长度为K的以2结尾的有效序列可能组成
将 2 加到任何长度为 K-1

的有效序列

-长度为K的以0结尾的有效序列可能组成
将 0 添加到长度为 K-1 且以 0 或 2

结尾的有效序列

如此简单Python程序

def valid123(n):
    a = [[0]*3 for _ in range(n)]
    a[0][0] = 1
    a[0][1] = 1
    a[0][2] = 1
    summ = 3
    for i in range(1, n):
        a[i][0] = summ - a[i-1][1]
        a[i][1] = summ
        a[i][2] = summ
        summ = sum(a[i])
    return summ

for i in range(1,10):
    print(i, valid123(i))

给予

相应的 OEIS sequence 具有简单的循环表示 a(n) = 3*a(n-1) - a(n-2) - 斐波那契的子集，并且确实存在一些封闭公式：

a(n) = (ap^n - am^n)/(ap-am), with ap := (3+sqrt(5))/2, am := (3-sqrt(5))/2

计算重复和限制的排列

Count permutation with duplicates and restriction

arrays

math

permutation

combinatorics