卡特兰数

努力学习JAVA中…水一篇面试小科普.

题目描述

面试很常见的一个买票找零问题: 票价5元钱,售票员手中没有钱,n个人拿着5块钱,和m个人拿着10块钱依次买票,问售票员可以找开零钱的情况一共有多少种.

这个题目还有很多变种,比如:

  • n个左括号和n个右括号组成长度2n的字符串,其中多少种括号合法匹配的情况,即任何前缀子串中,左括号的个数都大于等于右括号的个数.
  • 一个栈,n个push,和m个pop,问多少种合法的操作序列.

题解

对于刚好是n个push和n个pop的情况,答案就是卡特兰数.

如果是n个push和m个pop, 且n > m. 我们依然可以参照卡特兰数的思路来求解, 思路是求出有多少种非法情况.

设有n个push和m个pop, 其中n > m, d = n - m.

对于任意一种非法的序列S,他一定在某个位置第一次出现了pop比push多一个情况,假设这个位置是k.我们可知:

  • S[0:k]中, pop比push多一个,
  • S[k:n+m]中, push比pop多d+1个.

我们翻转S[k:n+m]中的pop和push操作,得到新的操作序列S’:

  • S’[0:k]中, pop比push多一个,
  • S’[k:n+m]中, pop比push多d+1个,
  • 那么S’中,pop比push多d+2个.

任意一个非法序列S,可以通过上述翻转操作转化成一个pop比push多d+2个的新序列S’.

很容易证明以下两点:

  • 任意两个不同的S,转换后S’也不同.
  • 任意pop比push多d+2个的序列S’, 都对应着一个非法序列.

换句话说,所有的非法序列和所有的pop比push多d+2个的序列是一一对应的关系,而新序列的个数很容易求出.

pop比push多d+2个的序列中pop有n+1个,push有m-1个.这种序列一共有C(n+m, n+1)种,可知

  • 非法序列个数为C(n+m, n+1)个,
  • 合法序列个数为 C(n+m, n) - C(n+m, n+1).

如果有30个人拿5块钱来买票,10个人拿10块钱来买票,售票员出问题的概率是 (40 choose 31) / (40 choose 30) = 10/31.