组合数学选择题

梦里梦外; 2022-05-18 08:27 295阅读 0赞

1.【题目】美团有个传统，就是公司各部门每月都要组织员工进行一次团建互动(team building，简称TB)，每个员工都可以带家属参加。活动内容出了吃喝玩之外，还要做一些互动的游戏，需要从员工中随机选出几名组成一队来完成游戏。一次TB活动，一共有20个人(含员工和家属)参加。已知如果随机选取3位员工以及该3位员工的家属，一共有220组合。问如果每次随机选取4个员工及该4位员工的家属，会有多少组合?  
A.405 B.455 C.495 D.505

【答案】C  
【解析】C(x,3)=220  
x=12  
C(12,4)=495

2.【题目】农场主和老婆每隔一年半就生一个孩子，他们一共生了15个孩子。最大的孩子的年龄是最小的孩子年龄的8倍。试求最大的孩子的年龄？  
A. 16                   B.20               C.24               D.32  
【答案】C  
【解析】最大孩子与最小孩子相差(15-1)\*1.5=21; 设最小年龄为x,则(x+21)/x=8，故x=3,则最大为24

3.【题目】抽屉里有100个红球、100个蓝球、100个黄球、100个橙球，现在每个人过来随机抽一个球，最多*\_\_*个人抽完之后，能保证一定集齐20个相同颜色的球。  
A.37          B.45         C.77      D.50        E.48         F.21  
【答案】C  
【解析】最多情况是，临界值（在抽一次就能满足条件：集齐20个相同颜色的球）为，每种颜色的球都抽了19个，最后抽一次，抽那个都一定完成任务，则总此次数：19\*4+1 = 77。

4.【题目】10个相同的糖果，分给三个人，每个人至少要得一个。有()种不同分法  
A.33            B.34           C.35             D.36  
【答案】D  
【解析】10个糖果依次排开，中间有9个空挡 ，依次编号为空挡1-9，从这9个空挡中任意取出2 个作为分割点 ，正好能把糖果分为3份，并且保证每一份中至少有一个糖果。因为分割点并没有顺序，所以可以使用组合公式C(9,2)计算。

5.【题目】一个合法的表达式由()包围，()可以嵌套和连接，如(())()也是合法 表达式；现在有 6 对()，它们可以组成的合法表达式的个数为*\_\_*  
A.15      B.30       C.64       D.132           E.256       F.360  
【答案】D  
【解析】C(12,6)-C(12,5)=132  
解释：  
卡特兰数列  
我们可以把左括号看做1，右括号看做0，这些括号的组合就是01的排列  
这里需要满足从第一个数开始的任意连续子序列中，0的个数不多于1的个数，也就是右括号的个数不多于左括号的个数。  
假设我们不考虑这个限制条件，那么全部的01排列共有C（2n,n）种，也就是一半0一半1的情况  
现在我们想办法把其中不符合要求的数量去掉  
在任何不符合条件的序列中，找出使得0的个数超过1的个数的第一个0的位置，然后在导致并包括这个0的部分序列中，以1代替所有的0并以0代表所有的1。结果总的序列变成一个有(n+1)个1和(n-1)个0的序列。而且这个过程是可逆的，也就是说任何一个有(n+1)个1和(n-1)个0构成的序列都能反推出一个不符合条件的序列，所以不符合条件的序列个数为C（2n,n-1）  
所以合法的排列数有C（2n,n）-C（2n,n-1）= C(12,6)-C(12,5)=13

6.【题目】从1,2,3,4…8,9里任意选择一部分数(至少1个),能得到多少种不同的乘积  
A.144         B.148    C.152       D.156    E.160     F.164  
【答案】C  
【解析】分解因子: 1\*2\*…*9=2^7*  3^4 \* 5 \* 7  
总=8\*5\*2\*2=160  
但 2^7 \* 3^0 和 2^0 \* 3^4 这两种情况不存在，5和7的组合是4种  
所以答案=160- 2\*4 = 152