非常妙的组合数学题.题干:有一个单调递增的数列,你要从中选两个不重的集合,然后对其进行两种检查:1:如果两个集合元素数量不一样,则元素更多的集合一定更大.2:两个集合元素和不重复.你要先对这些集合进行检查1,而且不必要不进行检查2,求对大小12的数列有多少个集合需要进行检查2.
已知长度为4的数列有25种集合选法,其中只有1个需要进行检查2,长度为7的数列有70个集合需要进行检查2.
首先,检查1的本质是找出所有两个集合大小相同的选法.
对于一个共同的size,考虑什么时候不需要检查2:假设元素为 1212 ,显然集合1小于集合2,不需要检查.相似地, 1122 同理,这是一个走楼梯问题,只能往下或者往右走,同时不能超过对角线,问有多少种情况.这是卡特兰数典题.
所以答案就是