Number of Ways to Rearrange Sticks With K Sticks Visible

我们用 f(i, j) 表示长度为 1,2,⋯,i 的木棍且可以可以看到其中的 jj 根木棍的方案数。

在进行状态转移的时候，我们可以考虑最后一根木棍是否可以被看到：

如果可以被看到，那么最后一根木棍的长度一定为 i，因此前 i−1 根木棍的长度恰好为 1,2,⋯i−1 的一个排列，并且可以看到其中的 j−1 根木棍。这样就有状态转移方程：

f(i, j) = f(i – 1, j – 1)

如果不可以被看到，那么最后一根木棍的长度为 [1, i-1] 中的某个值。假设这个值为 x，那么前 i-1 根木棍的长度为 1,⋯,x−1,x+1,⋯,i 的一个排列，并且可以看到其中的 j 根木棍。

由于一根木棍能否被看到只与它和它左侧木棍的「相对高度关系」有关，而与「绝对高度关系」无关。因此如果我们将长度：
1,⋯,x−1,x+1,⋯,i

按照顺序重新分配为：
1,2,⋯,i−1

那么任意两根木棍的「相对高度关系」都保持不变，即我们仍然可以看到 jj 根木棍，满足要求的排列数为 f(i−1,j)，与 x 的取值无关。这样就有状态转移方程：
f(i,j)=(i−1)⋅f(i−1,j)

将上面的两种情况求和，即可得到最终的状态转移方程：
f(i,j)=f(i−1,j−1)+(i−1)⋅f(i−1,j)

最终的答案即为 f(n,k)。