P3978 [TJOI2015]概率论

P3978 [TJOI2015]概率论

关于 Catalan 数的常见公式：

$$
H _ n = \frac {\binom {2n} n} {n + 1} \tag 1
$$

$$
H_n = \sum_{i=1}^{n} H_{i-1} H_{n-i} \tag 2
$$

$$
H_n = \frac{H_{n-1} (4n-2)}{n+1} \tag 3
$$

$$
H_n = \binom{2n}{n} - \binom{2n}{n-1} \tag 4
$$

考虑递归计算 $n$ 个点的二叉树的个数，枚举左右节点的个数，可以得到上面 $3$ 式的形式，那么有通项公式 $1$ 式。

考虑 $n$ 个点的二叉树的叶子节点数和。对于 $n$ 个节点 $k$ 的叶子节点的二叉树，任意删除一个叶子节点，可以得到 $n - 1$ 个节点的二叉树。$n -1$ 个节点的二叉树有 $n$ 位置可以接上一个叶子节点，那么被算了 $n$ 次。即 $n$ 个点的二叉树的叶子节点个数和为 $n - 1$ 个节点的二叉树的个数和的 $n$ 倍。

故答案为 $\frac {n\frac {\binom {2n - 2} {n - 1}}{n}}{\frac {\binom {2n} n} {n + 1}} = \frac {(2n - 2)!(n + 1) n!n!}{(n - 1)!(n - 1)!n(2n)!} = \frac {n (n + 1)} {2(2n - 1)}$

查看代码

#include <cstdio>
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        flag |= c == '-';
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...Rest>
void read (Type &x, Rest &...y) { read(x); read(y...); }
template <class Type>
void write (Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
}
int main ()
{
    int n; read(n);
    printf("%.10lf", n * (n + 1.0) / 2 / (2 * n - 1));
    return 0;
}