递归枚举半键上的碳所连的三个烷基。

• 三个有标号烷基碳原子数不同，$F_1 = \displaystyle\sum_{0\le i,j,i+j \le n-1} f(i)f(j)f(n-1-i-j)$
• 三个有标号烷基有两个碳原子数相同，$F_2 = \displaystyle\sum_{0\le i\le (n-1)/2} \binom{f(i)+1}{2} f(n-1-2i)$
• 三个有标号烷基的碳原子数都相同，$F_3 = \displaystyle\binom{f((x-1)/3)+2}{3}$

从 $n$ 个元素中选 $m$ 个可以重复的元素，共有 $\binom{n+m-1}{m}$ 种选法。

期望每种方案计算 $6$ 次，但是实际上有两个碳原子数相同的只计算了 $3$ 次，三个碳原子数相同的只计算了 $1$ 次。

$$\begin{aligned} 6f(n) &= F_1 + 3(F_2-F_3) + 5F_3 \\ &= \left( \sum_{0\le i,j,i+j \le n-1} f(i)f(j)f(n-1-i-j) \right) + 3 \left( \sum_{0\le i\le (n-1)/2} \frac{f(i)(f(i)+1)}{2} f(n-1-2i) \right) + 2\left( \frac{X(X+1)(X+2)}{6} \right), X=[3 \mid n-1]f\left(\frac{n-1}{3}\right) \end{aligned} $$

设 $t(n) = \displaystyle\sum_{0\le i\le n} f(i)f(n-i)$

则

$$\begin{aligned} 6f(n) &= \left( \sum_{0\le i\le n-1} f(i)t(n-1-i) \right) + 3 \left( \sum_{0\le i\le (n-1)/2} \frac{f(i)(f(i)+1)}{2} f(n-1-2i) \right) + 2\left( \frac{X(X+1)(X+2)}{6} \right) \\ &= \left( \sum_{0\le i\le n-1} f(i)t(n-1-i) \right) + 3 \left( \sum_{0\le i\le n-1} \frac{Y(n-1-i)(Y(n-1-i)+1)}{2} f(i) \right) + 2\left( \frac{X(X+1)(X+2)}{6} \right), &Y(n)=[2\mid n]f(n/2) \\ &= \left( \sum_{0\le i\le n-1} f(i) \left(t(n-1-i) + \frac{3}{2} Y(n-1-i)(Y(n-1-i)+1)\right) \right) + 2\left( \frac{X(X+1)(X+2)}{6} \right) \end{aligned} $$

令 $g(n) = t(n) + \dfrac{3}{2} Y(n)(Y(n)+1)$，

于是有转移方程

$$\begin{aligned} f(n) &= \frac{1}{6}\left[\left( \sum_{0\le i\le n-1} f(i)g(n-1-i) \right) + 2\left( \frac{X(X+1)(X+2)}{6} \right)\right] \\ g(n) &= \frac{3}{2} Y(n)(Y(n)+1) + \sum_{0\le i\le n} f(i)f(n-i) \end{aligned} $$

或者更简洁地，

$$\begin{aligned} f(n) &= \frac{1}{6}\left[ (f*g)(n-1) + 2\left( \frac{X(X+1)(X+2)}{6}\right)\right] \\ g(n) &= \frac{3}{2} Y(n)(Y(n)+1) + (f*f)(n) \end{aligned} $$

根据 $f(1)=1$ 以及 -H 的事实（特别地，我们将氢自由基看作零烷基，可以得出边界条件

$$f(0) = 1, g(0) = 4$$

f = [0]*2000

f[0] = f[1] = 1

for n in range(3, 10):
    for i in range(n):
        for j in range(n-i):
            f[n] += f[i]*f[j]*f[n-1-i-j]
            #print(f'add {f[i]*f[j]*f[n-1-i-j]}')
    for i in range((n-1)//2+1):
        f[n] += 1.5 * f[i]*(f[i]+1)*f[n-1-2*i]
        #print(f'add 3 * {0.5 * f[i]*(f[i]+1)*f[n-1-2*i]}')
    X = 0 if ((n-1) % 3) else f[(n-1)//3]
    f[n] += 2*(X*(X-1)*(X-2)/6 + X*X)
    #print(f'X={X}, add {2*(X*(X-1)*(X-2)/6 + X*X)}')
    f[n] /= 6
    print(f'C{n}H{2*n+1}Cl 共有 {f[n]} 种同分异构体')

f = [0]*2000
g = [0]*2000

f[0] = 1
g[0] = 4

def convat(a1, a2, ln):
    return sum(a1[i]*a2[ln-i] for i in range(ln+1))

for i in range(1, 10):
    x = 0 if ((i-1) % 3) else f[(i-1)//3]
    y = 0 if (i % 2) else f[i//2]
    f[i] = (convat(f, g, i-1) + 2*(x*(x-1)*(x-2)/6 + x*x))/6
    g[i] = convat(f, f, i) + 1.5 * y*(y+1)
    print(f'C{i}H{2*i+1}Cl 共有 {f[i]} 种同分异构体')