概述

概率组合题目分类
1、以高中数学为基础的古典概率计算方法。
2、斐波那契数和卡特兰数。
3、以选择题居多。

经典题

• 在6*9的网格中，以左上角为起点，右下角为终点移动，要求移动过程中每一步只可以向下移动一位或向右移动一位，问一共有几种路线
  左上角移动到右下角必然需要移动13步，其中有5步向下，8步向右，所以只需要从13步中随机选择5步作为向下移动即可，一共有种方案
• 七人站队，要求A必须站在B的左边，但不要求相邻，如果要求必须相邻呢？
  1、不要求相邻：7人全排列，共有7！种情况，此时A在B左边的概率为0.5，所以答案为0.5 * 7！
  2、要求必须相邻：此时可以将AB看成一个人，剩下的人全排列即可，答案为(7 - 1)！
• 6个人站队，要求甲和乙、丙不能相邻，一共有几种方案
  1、甲在头排：在甲后面可以有三种情况，其他的四个人全排列即可，所以共有3*(4!)种方案
  2、甲在中间：中间共有4个位置，在每个位置与甲相邻的人可以从除乙丙外的其他三个人中选择即种，其他的3个人全排列即可即3！，所以共有4*6*6中方案
  3、甲在末尾：在甲前面可以有三种情况，其他的四个人全排列即可，所以共有3*(4!)种方案
  4、所以共有3*(4!) + 3*(4!) + 4*6*6 = 288种方案
  5、还有另一种方法为：6! - 4*(5!) + 2*(4!) = 720 - 480 + 48 = 288
• 有10颗相同的糖，分给3个人吃，每人字少要吃一颗，一共有多少种分法
  因为每人至少吃一颗，所以只能在糖之间划分，10颗糖共有9个划分位置，分成3部分需要两个划分点，所以一共有种划分方案
• 有10个不同的球，放到3个不同的桶中，问一共有多少种放法
  每个球都有3种放法，10个球共有3¹⁰种放法
• 有10颗糖，每天至少吃一颗，有多少种不同的吃法
  采用划分的思想，因为每天至少吃一颗，所以需要在糖中间划分，10个糖一共有9个划分位置，可以采用0,1,2,……,9个划分点划分，即将糖划分为1天,2天,3天,……,10天吃，所以共有+++……+种划分方案
  
  公式1为二项式定理的内容
• 有n对左右括号，请返回合法排列的总数
  1、n对左右括号，共有排列总数为
  2、所有排列中，不合法的排列总数为
  若将不合法的排列中的左括号用1表示，右括号用-1表示，找到排列中-1的个数大于1的个数的最短前缀，则该前缀一定不合法，我们将该前缀中的所有的1变成-1，-1变成1，则可以得到一个1的个数为n + 1，-1的个数为n - 1的序列，可以证明，包含n + 1个1、n - 1个-1的序列与所有序列中每个不合法序列一一对应，所以不和法的排列总数为
  3、合法序列的总数如下：
  
  上式右边即为卡特兰数
• n个数出栈的顺序有几种
  出栈之前必须进栈，所以可以把进栈操作当成左括号，出栈操作当成右括号，这样合法的进出栈操作即为n对括号中合法的序列数，即卡特兰数
  
• 2n个人排队买票，n个人手拿5块，n个人手拿10块，当前票价为10块，售票员手中没有零钱，问2n个人怎样排队才能使售票员顺利购票
  拿10块钱的人买票之前必须有人拿5块钱买票，所以可以把拿10块钱的人买票当成左括号，拿5块钱的人买票当成右括号，这样合法的进出栈操作即为n对括号中合法的序列数，即卡特兰数
  
• n个无差别节点构成的不同结构的二叉树为f(n)，问f(n)为多少
  1、由题意可知：n = 0时，f(0) = 1、n = 1时，f(1) = 1、n = 2时，f(2) = 2、n = 3时，f(3) = 5
  2、若，则f(n)为卡特兰数，即：
  
• 12个高矮不同的人排成两排，每排从矮到高排列，且第二排比对应的第一排的人高，问有多少种排列方式
  如果将排在第一排的人标记为0，排在第二排的人标记为1，将所有的人从矮到高排序，则每种排队方式可以表示成由0 1组成的序列，只要在这个序列中任意一个前缀中0的个数大于1的个数即为合法序列，所以此题解仍为卡特兰树问题， 即
  
• 有n个装有信的信封，现在将其倒出后再将信装入和原来不同的信封，问有几种装法
  采用递归的方式解决：