组合数学 -卡特兰数 - 满足条件的01序列

组合数学 -卡特兰数 - 满足条件的01序列

1、卡特兰数

$卡特兰数:$卡特兰数: $f(n)=C_{2n}^n-C_{2n}^{n-1}=\frac{C_{2n}^n}{n+1}$f(n)=C2nn​−C2nn−1​=n+1C2nn​​

2、满足条件的01序列

给定n个0和n个1，它们将按照某种顺序排成长度为2n的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少个。

输出的答案对10⁹+7取模。

输出格式
共一行，包含整数n。

输出格式
共一行，包含一个整数，表示答案。

数据范围
1≤n≤10⁵

输入样例：
3
输出样例：
5

---

分析：

样例：
$n=3时，我们将整个01序列中1的个数视作为y轴纵坐标的值，0的个数视作x轴横坐标的值。$n=3时，我们将整个01序列中1的个数视作为y轴纵坐标的值，0的个数视作x轴横坐标的值。

$这样，每一种01序列的排列都对应一条从(0,0)到(3,3)的路径。$这样，每一种01序列的排列都对应一条从(0,0)到(3,3)的路径。

$现要求每一个前缀的0的个数要大于等于1的个数，即对于路径上的每个位置(x_i,y_i)需满足x_i>=y_i。$现要求每一个前缀的0的个数要大于等于1的个数，即对于路径上的每个位置(xi​,yi​)需满足xi​>=yi​。

$对应到坐标轴上，就是路径上的每个位置需保证在橙色直线上或者以下。$对应到坐标轴上，就是路径上的每个位置需保证在橙色直线上或者以下。

$可见，从(0,0)到(3,3)，需要沿x轴正方向走3步，沿y轴正方向走3步，路径总方案数为C_6^3，即6步当中有3步沿x轴。$可见，从(0,0)到(3,3)，需要沿x轴正方向走3步，沿y轴正方向走3步，路径总方案数为C63​，即6步当中有3步沿x轴。

$当然还要除去不合法的一部分路径，作红色直线。$当然还要除去不合法的一部分路径，作红色直线。

$所有经过红色直线上的点再到(3,3)的路径都是不合法的。如上图中的绿色路径。$所有经过红色直线上的点再到(3,3)的路径都是不合法的。如上图中的绿色路径。

$每一条不合法路径都唯一对应于一条终点关于红线与(3,3)对称的路径，即上图蓝色路径，终点为(2,4)。$每一条不合法路径都唯一对应于一条终点关于红线与(3,3)对称的路径，即上图蓝色路径，终点为(2,4)。

$于是不合法路径的总数量即从(0,0)到(2,4)的路径数量，为C_6^2。$于是不合法路径的总数量即从(0,0)到(2,4)的路径数量，为C62​。

$总的合法路径数量为C_{6}^3-C_{6}^{2}。$总的合法路径数量为C63​−C62​。

$故一般地，有总合法路径数量为C_{2n}^n-C_{2n}^{n-1}=\frac{C_{2n}^n}{n+1}。$故一般地，有总合法路径数量为C2nn​−C2nn−1​=n+1C2nn​​。

具体落实：

$只求一个组合数，可以直接根据定义计算：$只求一个组合数，可以直接根据定义计算：

$C_{a}^b=\frac{a!}{(a-b)!·b!}=\frac{a(a-1)(a-2)...(a-b+1)}{b!}$Cab​=(a−b)!⋅b!a!​=b!a(a−1)(a−2)...(a−b+1)​

$本题求 公式：$本题求公式：

$\frac{C_{2n}^n}{n+1}=\frac{1}{n+1}·\frac{2n!}{(2n-n)!·n!}=\frac{1}{n+1}·\frac{2n(2n-1)(2n-2)...(n+1)}{n!}$n+1C2nn​​=n+11​⋅(2n−n)!⋅n!2n!​=n+11​⋅n!2n(2n−1)(2n−2)...(n+1)​

$模数10^9+7是质数，费马小定理+快速幂求逆元取模即可。$模数109+7是质数，费马小定理+快速幂求逆元取模即可。

代码：

#include<iostream>

#define ll long long

using namespace std;

const int mod = 1e9+7;

int n;

ll quick_pow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int main()
{
    cin>>n;
    
    ll ans=1;
    int a=2*n,b=n;
    for(int i=a;i>a-b;i--) ans=ans*i%mod;
    for(int i=1;i<=b;i++) ans=ans*quick_pow(i,mod-2)%mod;
    ans=ans*quick_pow(n+1,mod-2)%mod;
    
    cout<<ans<<endl;
    
    return 0;
}