计算卡特兰分布配对中边界切割键的平均数量

首先得指出你之前思路里的核心问题：你把所有可能的跨边界元素对都算进了统计，但卡特兰配对的无交叉约束会排除很多这类配对，而且剩下的合法跨配对在所有卡特兰排列里的出现概率也不是均匀的，这就是你结果高估的原因。

举个简单的例子：n=2，L=1时，你认为有3种跨边界配对（1-2、1-3、1-4），但实际上1-3这个配对是非法的——如果1和3配对，剩下的2和4配对会形成交叉，不符合卡特兰无交叉的要求。合法的跨配对只有1-2和1-4，各在一种卡特兰排列里出现，所以总切割数是1+1=2，平均是1，而不是你算的3/2。

正确的解题思路：线性期望+卡特兰配对递归性质 #

我们可以用线性期望来简化问题：平均切割数等于每个可能的合法跨边界配对在卡特兰排列中出现的概率之和（因为期望是线性的，不管事件是否独立）。不过更直观的是用递归方式推导，结合卡特兰配对的结构：

递归公式定义

设Q(n,L)为n对元素、边界在第L个元素右侧时的平均切割数，卡特兰数$C_n=\frac{(2n)!}{n!(n+1)!}$。递归公式如下：

Q(n,L) = [sum_{k=1到floor(L/2)} (C_{k-1}*C_{n-k}/C_n) * Q(n-k, L-2k)] 
        + [sum_{k=ceil((L+1)/2)到n} (C_{k-1}*C_{n-k}/C_n) * (1 + Q(k-1, L-1))]

• 第一部分：第一个元素和左侧第2k个元素配对（完全在边界左侧），不产生切割，递归计算剩余元素的平均切割数。
• 第二部分：第一个元素和右侧第2k个元素配对（跨边界），产生1个切割，递归计算中间元素的平均切割数。

初始条件

• $Q(0, 0) = 0$（没有元素时切割数为0）
• $Q(n, 0) = Q(n, 2n) = 0$（边界在最左或最右时无切割）
• $Q(1, 1) = 1$（1对元素，边界在中间时必然切割）

验证例子

比如n=2，L=2：

• 卡特兰数$C_2=2$，两种排列：
  1. (1-2),(3-4)：切割数0
  2. (1-4),(2-3)：切割数2（两个配对都跨边界）
• 平均切割数=(0+2)/2=1，用递归公式计算结果一致。

再比如n=3，L=2：

• 递归计算得$Q(3,2)=\frac{6}{5}=1.2$，而你之前算的$\frac{8}{5}=1.6$明显高估，因为你把非法的跨配对也算进去了。

更高效的计算方式 #

如果需要计算较大的n和L，可以用动态规划预存卡特兰数和Q(n,L)的值，避免重复递归计算。

另外，我们也可以用指示变量简化推导：
设K为边界左侧内部配对的对数，那么跨边界的配对数=$L-2K$（左侧L个元素中，2K个用于内部配对，剩下L-2K个必须和右侧元素配对）。因此：

Q(n,L) = L - 2*E[K]

其中$E[K]$是左侧内部配对对数的期望，可通过计算每个左侧元素和内部元素配对的概率之和再除以2得到（每个配对被计算两次）。

备注：内容来源于stack exchange，提问作者J.Agusti