嘿，我来帮你梳理下这里的问题所在！

首先你的直觉公式 P(n+1,r) = (n+1)*P(n,r) 确实不对，就像你举的例子：P(4,2)=12，但4*P(3,2)=4*6=24，差了整整一倍，问题出在重复计数上。

咱们来拆解你的“证明”逻辑：你把集合S（n+1个元素）的r排列，拆成了“去掉每个s_i后S-{s_i}的r排列”，然后乘以(n+1)。但这里的问题是，那些不包含多个s_i的r排列会被多次统计！

比如拿P(4,2)举例，假设S={a,b,c,d}，排列c,d既属于S-{a}的r排列，也属于S-{b}的r排列，所以在你的计算里它被算了2次，但实际上它只是S的一个r排列，只该被算1次。所有不包含k个元素的r排列，都会被你重复统计k次，这就导致你的结果比实际大很多。

那正确的递归思路应该怎么想呢？我们可以把P(n+1,r)分成两种互斥的情况：

• 情况1：这个r排列不包含新增的那个元素（也就是n+1集合里多出来的那个元素），那其实就是从原来的n个元素里选r个排列，数量是P(n,r)。
• 情况2：这个r排列包含新增的元素，那我们可以先给这个新元素找位置（有r个位置可选），然后剩下的r-1个位置从原来的n个元素里选r-1个排列，数量是r*P(n,r-1)。

把两种情况加起来，就得到正确的递归公式：
P(n+1,r) = P(n,r) + r*P(n,r-1)

咱们用你的例子验证一下：P(4,2)=P(3,2)+2*P(3,1)=6+2*3=12，完全符合实际结果！

再回到你的推导，核心错误就是没考虑到不同S-{s_i}的r排列集合之间有重叠，直接相乘会把重叠部分多次计数，自然就错啦。

备注：内容来源于stack exchange，提问作者Mani