英文积累:
clockwise(顺时针)
anticlockwise (逆时针)
This is a small but ancient game. You are supposed to write down the numbers 1, 2, 3,..., 2n - 1, 2n consecutively(连续地)in clockwise order on the ground to form a circle, and then, to draw some straight line segments(直线段) to connect them into number pairs. Every number must be connected to exactly one another.(然后用直线段连接一对数字,每个数字都必须连接到另外一个数字上)
And, no two segments are allowed to intersect.(没有两个线段是相交的)
It's still a simple game, isn't it? But after you've written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right?
这道题的大体意思是:2n个人围成一圈,两两互相连接,且连接的线不能交叉,问有多少种方式。
注意是线段不能相交,所以每个点只能出去一条线段。
假设2n个数的相连的方式有An种,注意,任意相连数中间隔的个数一定也是偶数,否则,一定有一个数要穿过这条线,假设左边有2k个数,则左边有Ak种相连方式,右边An-k-1种,这种情况下相连的方式有Ak*An-1-k种,k可以从0到n-1.
这道题就是著名的卡特兰数,(Catalan数),对这道题还有兴趣的,可以从网上百度搜卡特兰数。