【排队买票】 （C语言代码）利用 卡特兰数

解题思路:

N+K 个人排队买票，N个持有1元，M个人持有2元，那么每一个持有2元的人必有一个持有1元的人与之配对。

那这个问题就是个配对问题，配对问题正好用卡特兰数。

参考：

https://zh.wikipedia.org/wiki/卡塔兰数

http://www.cnblogs.com/wuyuegb2312/p/3016878.html#suggestion

https://blog.csdn.net/doc_sgl/article/details/8880468

注意事项:

卡特兰数本身是组合计数，本题有个特殊要求是要排序，因此乘以 N 与 K 的全排列数，即阶乘的个数。



参考代码:

#include <stdio.h>

#define N 10

long fIter(int n)

{

    long result = 1;

    while(n > 1)

    {

        result *= n;

        n--;

    }

    return result;

}

long catalan(int n, int m)

{

    long count;

    long mid;

    mid = fIter(n+m);

    count = (mid/(fIter(n)*fIter(m)) - mid/(fIter(n+1)*fIter(m-1)))*(fIter(n)*(fIter(m)));

    return count;

}

int main()

{

    int n,m,k;

    long count;

    while((scanf("%d%d%d",&m,&n,&k))==3)

    {

        count = catalan(n,k);

        printf("%d\n",count);

    }

    return 0;

}