【2】基本计数问题

作者: 备考999天 | 来源:发表于2022-07-07 15:00 被阅读0次

题2.1 从 $1,2,3,4,5,6,7$ 中取 $3$ 个不同的数，有多少种组合？
解可以利用杨辉三角形：
$1\\ 1 \quad1 \\ 1\quad2\quad1\\ 1\quad 3\quad3\quad1\\ 1\quad 4\quad 6 \quad 4 \quad 1\\ 1\quad 5\quad 10 \quad 10 \quad 5 \quad 1\\ 1\quad 6\quad 15 \quad 20 \quad 15 \quad 6 \quad 1\\ 1\quad 7\quad 21 \quad 35 \quad 35 \quad 21 \quad 7 \quad 1$
解得：从不同的7个数中取3个不同的数，总共有35种组合。
$\blacksquare$

题2.2 从 $1,2,3,4,5,6,7$ 中取 $3$ 个不同的数，组成三位整数，共可以组成多少个三位数？
解第一步、计算组合数：从不同数中取3个不同的数，按照题2.1，同有35中组合。
第二步、计算排列数：3个不同的数，共有6总排列，所以本题的答案是 $35\times 6 =210$ 。
答：总共有210个三位数。
$\blacksquare$

题2.3
(1)从1,2,3,4,5,6中，取3个不同的数，组成3位数的偶数，把所有情况都列出来。
(2)从0,1,2,3,4,5中，取3个不同的数，组成3位数的偶数，把所有情况都列出来。
解 (1)设这个偶数为 $\overline{cba}$ ，根据题意分步骤讨论：
第1步： $a$ 是偶数，取2,4,6之一有3种可能。
第2步：确定 $\overline{cb}$ ，这相当于从剩余5个不同的数中取2个作排列，有 $A_{5}^2$ 种组合。
两步计数满足乘法原理，故有 $3\times A_5 ^2=60$ 。以下部分列出满足条件的3位数，其余的只要把以下各数十位、百位互换即可得到：
132 142 152 162 342 352 362 452 462 562
124 134 154 164 234 254 264 354 364 564
126 136 145 156 236 246 256 346 356 456
(2) 分类列举：
第1类，0在个位有：120 130 140 150 210 230 240 250 310 320 340 350 410 420 430 450 510 520 530 540
第2类，2在个位有：102 132 142 152 302 312 342 352 402 412 432 452 502 512 532 542
第2类，4在个位有：104 124 134 154 204 214 234 254 304 314 324 354 504 514 524 534
所以，共有20+16+16=52个满足条件的偶数。
$\blacksquare$
题2.4 篮球队有10个人，分成两个不同的小组训练，有多少种方案？
解答案是组合数 $C_{10}^5$ ，利用组合递推公式：
$C_{10}^5=C_9^5+C_9^4=C_8^5+2C_8^4+C_8^3\\ =6C_7^3+2C_7^2=6C_6^3+6C_6^2+2\times 21\\ =6(C_5^3+C_5^2)+6\times 15 + 42=120+90+42=252$
$\blacksquare$

评注2.5 利用杨辉三角形可以证明组合数的递推公式： $C_n^r=C_{n-1}^{r}+C_{n-1}^{r-1} \space(n,r\in\mathbb N,n>r\ge1)$

题2.6 (1) 如图2.6.1，按箭头方向走，从A地到B地的旅行路径有多少种？

2.6.1

(2) 如图2.6.2，按箭头方向走，从A地到B地的旅行路径有多少种？

图2.6.2

(3)如图2.6.3，旅行家每次走一格，并且只能向右或向上，图中红色路径是一条符合条件的路径。问：从A地到B地的旅行路径有多少种？

图2.6.3
解 (1) 如图2.6.4,给每个点编码：

图2.6.4
易知：旅行家到达某个点的路径计数，是所有可能的上一个站点的路径和，设站点

x

的路径数为

a_x

，则如下成立：

a_A=1,a_1=1

a_2=a_A+a_1=2

a_3=a_2=2,a_4=a_2=2

a_B=a_3+a_4=2+2=4

所以，

A\rightarrow B

的路径数为4。

(2) 如图2.6.5，给所有的点表明编码(A,B,C,...)，按照(1)的方法：

图2.6.5

a_A=1

a_C=1

a_D=a_A+a_C=2

a_F=a_E=a_D=2

a_G=a_D+a_F=2+2=4

a_I=a_F+a_G=2+4=6

a_H=a_D+a_G+a_I=2+4+6=12

a_B=a_H+a_I=6+12=18

可见，

A\rightarrow B

的路径有18条。

(3) 如图2.6.6，每个格点的坐标为有序自然数对，易见 $A=(0,0),B=(7,3)$ ，用 $T(x,y)$ 表示从 $(0,0)$ 到 $(x,y)$ 的路径数，本题求 $T(7,3)$ 。

图2.6.6
注意到以下三点：
a).

x,y

是任意自然数,

T(x,0)=T(0,y)=1

。
b)

x,y

是任意自然数,

T(x,y)=T(y,x)

c). 到达

(x,y)

的前一站为

(X,y)

或

(x,Y)

，其中

X=\max(x-1,0),Y=\max(y-1,0)

，所以：

T(x,y)=T(X,y)+T(x,Y)

于是，可以利用a)c)得，

T(x,1)=x+1,T(1,y)=y+1

再利用a),b),c)递归求解：

T(7,3)=T(6,3)+T(7,2)=\\ =T(6,2)+T(5,3)+T(6,2)+T(7,1)\\ =T(5,2)+T(6,1)+T(4,3)+T(5,2)+T(5,2)+T(6,1)+8\\ =3T(5,2)+T(4,3)+22\\ =3T(4,2)+3T(5,1)+T(3,3)+T(4,2)+22\\ =3T(3,2)+3T(4,1)+18+T(2,3)+T(3,2)+T(3,2)+T(4,1)+22\\ =6T(3,2)+60=6T(2,2)+6T(3,1)+60=12T(2,1)+84\\ =36+84=120

可见，总共有120条路径。

\blacksquare

评注2.7 试想如下场景，给定两个符号 $\rightarrow,\uparrow$ ，符号串 $a_1,a_2,a_3,...,a_{10}$ 含有7个右箭头，3个上箭头。这个符号串是旅行家行走方格的"说明书"，当 $a_k="\rightarrow"$ 时，第 $k$ 步向右；当 $a_k="\uparrow"$ 时，第 $k$ 步向上。如下说明书：
$\rightarrow \rightarrow \uparrow\rightarrow \rightarrow \rightarrow \rightarrow \uparrow\uparrow\rightarrow$
其路径为图2.7.1：

图2.7.1
每本这样的说明书与路径方案双射，易验证，说明书的串

\{a_n\}

的可能组合总数为

C_{10}^3

，根据杨辉三角形容易计算

C_{10}^3=120

。

题2.8 按 $x$ 次数的递增展开多项式：
例子： $(1+2x)(1+x) = 1\times 1+1\times x+2x\times 1+2x\times x\\ =1+x+2x+2x^2\\=1+3x+2x^2$
(1) $(1+x)^2$
(2) $(1+x)^3$
(3) $(x+3)(x^2+2x+2)$

解 (1) 如图2.8.1，乘法分配律表示如下：

图2.8.1
所以，

(1+x)^2=1\times1+1\times x+x\times1+x\times x=1+2x+x^2

(2) $(1+x)^3=(1+x)(1+x)^2=(1+x)(1+2x+x^2)$
如图2.8.2使用表格计算：

图2.8.1
所以，

(1+x)^3=1+x+2x+2x^2+x^2+x^3=1+3x+3x^2+x^3

(3)如图2.8.2使用表格计算：

图2.8.3
所以

(x+3)(x^2+2x+2)=6+6x+2x+2x^2+3x^2+x^3\\ =6+8x+5x^2+x^3

\blacksquare

题2.9 从 $1,2,3,...,7$ 这7个数字中组成的所有整数比 $1271$ 小的数有多少个？

解分类计数：
(a) 1位数的有7个；
(b) 2位数的有 $7\times 7=49$ 个；
(c) 3位数的有 $7\times 7 \times 7=343$ 个；
(c) 4位数再分类：
$\overline{127x}$ 型：0个；
$\overline{12yx},y<7$ 型： $6\times 7=42$ 个；
$\overline{11yx}$ 型： $7\times7=49$ 个。
总共有： $7+49+343+0+42+49=490个$ 。
$\blacksquare$

题2.10 $0,1,10,11,100,101,110,...,10010$ ，请问 $10010$ 的位置是多少？
解 $0,1,10,11,100,101,110,...,10010$ 是自然数列的二进制表示，所以： $10010=2+2^4=18$ ，所以10010在第19位。
$\blacksquare$
题2.11 306班有10名男生，8名女生，从男生中选3名，女生中选4名，参加辩论赛，有多少种方案。
解 $C_{10}^3\times C_8^4=8400$

题2.12 A,B,C,D,E,F六个人组成一个乐队，1个架子鼓、2个吉他手、3个歌手，共有多少种方案。
解 $C_6 ^1\times C_5 ^2 \times C_3^3=120$

题2.13 把15个篮球运动员分成人数相同的三组进行循环赛，有多少种分法。
解 $\frac{C_{15}^5C_{10}^5}{3!}=126126$

题2.14
(1) 1~10000这些整数中，出现数字2的次数是多少？
(2) 1~2022这些整数中，出现数字"24"的次数是多少？
解 (1) 因为10000没有2，所以这与 $“0000”-“9999”$ 中找“2”是等价的。把小于10000的自然数都补充称4位数，高位不足补零，则 $\{“0000”-“9999”\}$ 的字典序与{0，1,2,...,9999}这两个集合一一对应。“0000”-“9999”中每个数字出现的机会均等，10个不同的数字总共出现40000次，所以2出现的次数为 $4000$ 。
(2)分类如下：
(a) "24"位于个十位：形如“x24”的数有10个，形如"1x24"的数有10个数；
(b) "24"位于十百位：形如"24x"的数有10个，形如"124x"的数有10个数；
综上，1~2022这些整数中，出现数字"24"的次数是40。

【2】基本计数问题

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读