解决模式无效（需要删除）的组合问题

Question

问题在N天，一个学生可以缺席也可以缺席，但是不允许连续缺席3天以上。因此，组合总数为 - 2^N，其中每天只有 2 个选项，A - 缺席或 P - 存在

让我们取 N as 7，这意味着总组合是 - 2^7 = 128

现在无效的模式是 AAA, AAAA, AAAAA, AAAAAA, AAAAAAA，因此需要从总值中删除它们，以下是我的理解：

1. 3 Absent together:

    AAAP--- - 2^3 = 8
    ---PAAA - 2^3 = 8
    PAAAP-- - 2^2 = 4 * 3C1 (as there are such combinations) = 12
    Total - 28

2. 4 Absent together:
   AAAAP-- - 2^2 = 4
   --PAAAA - 2^2 = 4
   PAAAAP- - 2 *2 = 4
   Total - 12

3. 5 Absent together:
   AAAAAAP- - 2
   -PAAAAAA - 2
   PAAAAAP - 1
   Total - 5

4. 6 Absent together:
   AAAAAAP
   PAAAAAA
   Total - 2

5. 7 Absent together:
   AAAAAAA
   Total - 1

总无效 - 28 + 12 + 5 + 2 + 1 = 48

有效组合总数 - 128 - 48 = 80

请告诉我我推导的是否正确，或者我的理解有误

Answer 1

让我们制作循环方程。长度的有效组合 k 可能以 0、1 或 2 个“A”结尾 - 表示此类变体的数量 v0, v1 and v2。

如果我们将“P”添加到长度 k

的任何有效组合中，我们就可以得到长度 k+1 与零结尾“A”的有效组合

v0(k+1) = v0(k) + v1(k) + v2(k)

如果我们将“A”添加到长度 k

的任何零结尾组合中，我们就可以得到长度 k+1 与一个结尾“A”的有效组合

v1(k+1) = v0(k)

如果我们将“A”添加到长度 k

的任何单结尾组合中，我们就可以得到长度 k+1 和两个结尾“A”的有效组合

v2(k+1) = v1(k)

现在看Python代码(Ideone example)

v0 = 1
v1 = 0
v2 = 0
for i in range(10):
    v0, v1, v2 = v0 + v1 + v2, v0, v1
    print(i, v0)

结果是

注意你有错误v(7) = 81，不是80

这是 tribonacci sequence 更简单的递归表达式：

 a(n) = a(n-1) + a(n-2) + a(n-3)

解决模式无效（需要删除）的组合问题

Solving the combination problem where a pattern is invalid (needs to be removed)

math

combinations

permutation