组合数学第一次作业

1

首先每个盒子中放k 个球, 剩余 n - rk 个球

此时转换问题为 n - rk 个球 放入 r 个盒子中的 可重组合

共计 : $C(n-rk + r - 1 , r ) = C(n-(k-1)r - 1 , r )$

2

方法一：补零方法

1. 考虑数字 0 到 99,999 的补零五位数表示：

   总数字数：100,000。每个位（个位、十位、百位、千位、万位）上，每个数字 0-9 出现次数均等，为 100,000 / 10 = 10,000 次。

   因此，所有位上 0 出现的总次数：5 位 × 10,000 = 50,000。

2. 计算所有前导零的总数：

   • 数字 0：5 个前导零。
   • 1 位数字（1-9）：9 个数字 × 每个 4 个前导零 = 36。
   • 2 位数字（10-99）：90 个数字 × 每个 3 个前导零 = 270。
   • 3 位数字（100-999）：900 个数字 × 每个 2 个前导零 = 1,800。
   • 4 位数字（1000-9999）：9,000 个数字 × 每个 1 个前导零 = 9,000。
   • 5 位数字（10000-99999）：90,000 个数字 × 每个 0 个前导零 = 0。

   总前导零数：5 + 36 + 270 + 1,800 + 9,000 = 11,111。

3. 计算 0 到 99,999 的实际数字中 0 的出现次数：实际 0 出现次数 = 总 0 次数 - 前导零总数 = 50,000 - 11,111 = 38,889。数字 0 的贡献为 0，因此 1 到 99,999 的 0 出现次数也为 38,889。
4. 添加 100,000 的 0 出现次数：100,000 的数字为 100000，包含 5 个 0。因此，1 到 100,000 的总 0 出现次数：38,889 + 5 = 38,894。

方法二：逐位计算方法

• 个位（第 0 位）：个位为 0 当数字可被 10 整除。序列 10, 20, …, 100,000，项数：(100,000 - 10)/10 + 1 = 10,000。出现次数：10,000。

• 十位（第 1 位）：

  十位为 0 当 floor(n/10) mod 10 = 0 且 n ≥ 10。

  k = floor(n/10) 从 1 到 10,000，k mod 10 = 0 时（k=10,20,…,10,000），项数：1,000。

  但对应数字数：k=10 到 9,990（步进 10）有 999 个 k，

  每个对应 10 个数字；k=10,000 对应 1 个数字（100,000）。

  总数字数：999 × 10 + 1 = 9,991。出现次数：9,991。

• 百位（第 2 位）：百位为 0 当 floor(n/100) mod 10 = 0 且 n ≥ 100。m = floor(n/100) 从 1 到 1,000，m mod 10 = 0 时（m=10,20,…,1,000），项数：100。但对应数字数：m=10 到 990（步进 10）有 99 个 m，每个对应 100 个数字；m=1,000 对应 1 个数字（100,000）。总数字数：99 × 100 + 1 = 9,901。出现次数：9,901。
• 千位（第 3 位）：千位为 0 当 floor(n/1,000) mod 10 = 0 且 n ≥ 1,000。p = floor(n/1,000) 从 1 到 100，p mod 10 = 0 时（p=10,20,…,100），项数：10。但对应数字数：p=10 到 90（步进 10）有 9 个 p，每个对应 1,000 个数字；p=100 对应 1 个数字（100,000）。总数字数：9 × 1,000 + 1 = 9,001。出现次数：9,001。
• 万位（第 4 位）：万位为 0 当 floor(n/10,000) mod 10 = 0 且 n ≥ 10,000。q = floor(n/10,000) 从 1 到 10，q mod 10 = 0 时只有 q=10（对应 n=100,000）。出现次数：1。
• 十万位（第 5 位）：100,000 的十万位为 1，不为 0，出现次数：0。
• 总出现次数：10,000（个位） + 9,991（十位） + 9,901（百位） + 9,001（千位） + 1（万位） + 0（十万位） = 38,894。

3

( 1 ) 把女生当做隔板, 男生站在女生空隙里, $P(n+1 , m ) * n!$

( 2 ) 女生作为一个整体, 站在男生的空隙里 $(m + 1) m! n!$

( 3 ) 男生 A 和 女生 B 相邻时 : 把 AB当做一个整体, 整体有 AB 和 BA 两种排列.

共计 $(m+n - 1) ! * 2 $

总排列数为 $(m+n)!$

所以共计 $(m+n)! - 2 (m+n-1)!$

4

( 1 ) 由于四边与坐标轴平行，每个长方形由其左下角点(x,y)和右上角点(u,v)唯一确定，

其中x < u 且 y < v。x和u的取值范围是0到9，y和v的取值范围是0到7。

• 对于每个左下角点(x,y)，右上角点(u,v)必须满足x < u ≤ 9 且 y < v ≤ 7。因此，u有(9 - x)种选择（从x+1到9），v有(7 - y)种选择（从y+1到7）。
• 因此，对于固定(x,y)，长方形的数量为(9 - x) × (7 - y)。
• 需要求和所有可能的x和y：x从0到9，y从0到7。总数为：

$$\sum_{x=0}^9\sum_{y=0}^7(9-x)\times(7-y)=1260$$

( 2 ) 对于正方形，同样由左下角点(x,y)和右上角点(u,v)确定，但需满足边长相等，即u - x = v - y。设边长s = u - x = v - y，s ≥ 1。

• 由于u = x + s ≤ 9，v = y + s ≤ 7，所以s ≤ 9 - x 且 s ≤ 7 - y。因此s的最大值为min(9 - x, 7 - y)。
• 对于每个(x,y)，s可以从1取到min(9 - x, 7 - y)，所以正方形的数量为min(9 - x, 7 - y)。
• 需要求和所有可能的x和y：x从0到9，y从0到7。总数为：

$$\sum_{x=0}^9\sum_{y=0}^7min(9-x,7-y)=196$$

5

关键转换：将问题转化为网格路径问题：

• 从点(0,0)出发，0代表向右移动（横坐标加1），1代表向上移动（纵坐标加1）。
• 目标是从(0,0)走到(n,n)，且路径始终不越过直线y = x（即任意时刻向右移动的次数不少于向上移动的次数）。这等价于避免路径触及y = x + 1，从而确保0的数目始终不少于1的数目。

总路径数：从(0,0)到(n,n)的无限制路径数为组合数C(2n, n)，因为需要在2n步中选择n步向右（或向上）。

非法路径数：那些违反条件的路径会接触或越过直线y = x + 1。使用反射原理，从(0,0)到(n,n)的非法路径与从(-1,1)到(n,n)的路径一一对应，其数为C(2n, n-1)。

有效路径数：总路径数减去非法路径数，即C(2n, n) - C(2n, n-1)。

6

首先分解 $a_{60} = 20^{20} = (2^2 5)^ {20} = 2^{40} 5^{20}$

由于数列条件 $a_i 是 a_{i+1} 的约数$

定义新数列$b_i = a_{i+1} / a_{i }$ 其中 i 从 1 到 59 , 每个$b_i$ 是正整数

$$b_1* b_2* b_3* ........*b_{59} = a_{60}$$

转换问题为分解 $b_i = 2^{x_i} * 5 ^{y_i}$ 即可

( 1 ) 在这种情况下, $b_i$可以等于 1

$x_1 + x_2 +…+ x_{59} = 40, 根据隔板法, 得到 C(40 + 59 - 1, 40) = C(98,40)$

$y_1 + y_2 + …+y_{59} = 20,根据隔板法, 得到 C(20 + 59 - 1 ,20) =C(78,20)$

最终结果为 $ C(98,40) * C(78,20)$

( 2 ) 若进一步要求 $a_i$ 严格递增，求满足条件的序列数目

严格递增要求 $a_i < a_{i+1}$，即 $d_i = a_{i+1}/a_i > 1$，所以每个 $d_i \geq 2$。

这意味着每个 $d_i$ 不能为 1，即对于每个 $i$，$x_i$ 和 $y_i$ 不能同时为零。

使用包含排斥原理计算。设 $N = 59$。

总分配数（无严格递增要求）为：

$$T = \binom{98}{40} \cdot \binom{78}{20}.$$

对于 $j = 0, 1, \ldots, 59$，设 $F(j)$ 为强制 $j$ 个特定 $d_i$ 为 1（即 $x_i = 0$ 且 $y_i = 0$）时，分配指数到剩余 $59 - j$ 个 $d_i$ 的方式数：

$$F(j) = \binom{98 - j}{40} \cdot \binom{78 - j}{20}.$$

其中当 $98 - j < 40$ 或 $78 - j < 20$ 时，二项式系数为 0。
由包含排斥原理，严格递增序列数目为：

$$\sum_{j=0}^{59} (-1)^j \binom{59}{j} \binom{98 - j}{40} \binom{78 - j}{20}.$$

7

简单回路相当于一笔画问题，等价于每个点都走一次即可。

相当于从 $(1, n)$ 和 $(n + 1, 2n)$ 这两个集合在总的遍历序列里面交替出现。

对于完全二分图 $K_{n,n}$，点集 $V=\{1,2,\ldots,2n\}$，边集 $E=\{(i,n+j)\mid 1\leq i,j\leq n\}$，要求计算长度为 $2k$ 的简单回路的数目，其中 $k$ 是满足 $1\leq k\leq n$ 的正整数。
分析

• 简单回路要求不含重复顶点或重复边，且长度至少为 3。在完全二分图中，任何回路长度必须为偶数，且最小回路长度为 4（因为长度 2 的回路不存在）。
• 当 $k=1$ 时，长度为 2 的回路不存在，故数目为 0。
• 当 $k\geq 2$ 时，长度为 $2k$ 的简单回路必须使用 $k$ 个左部顶点（来自 $\{1,2,\ldots,n\}$）和 $k$ 个右部顶点（来自 $\{n+1,n+2,\ldots,2n\}$），且回路在诱导子图 $K_{k,k}$ 上形成哈密顿回路。
  计算步骤

1. 选择顶点：从 $n$ 个左部顶点中选择 $k$ 个，有 $\binom{n}{k}$ 种方式；从 $n$ 个右部顶点中选择 $k$ 个，有 $\binom{n}{k}$ 种方式。故选择顶点的总方式数为 $\binom{n}{k}^2$。

2. 形成回路：在选定的 $2k$ 个顶点形成的完全二分图 $K_{k,k}$ 中，无向哈密顿回路的数目为 $\frac{(k!)^2}{2}$。这是因为：

   • 有向哈密顿回路的数目为 $k!\times k!=(k!)^2$（从左部顶点开始，选择序列）。
   • 每个无向回路对应两个有向回路（方向相反），故无向回路数为 $\frac{(k!)^2}{2}$。

总数目：因此，对于 $k\geq 2$，长度为 $2k$ 的简单回路数目为：$\binom{n}{k}^2\cdot\frac{(k!)^2}{2}$

8

( 1 ) 一个圆和n条直线最多将圆分成的部分数

当添加第k条直线时，它最多与之前的k-1条直线相交，从而被分成k段，每段会将圆的一个区域分成两部分。因此，部分数的递推关系为：$f(n)=f(n-1)+n$,其中$f(0)=1$ (只有圆本

身)。求解得：

$$f(n)=1+\sum_{k=1}^nk=1+\frac{n(n+1)}2$$

所以，最多部分数为：

$$\boxed{1+\frac{n(n+1)}2}$$

设 $f(n)$为n 条直线最多能把圆分成多少部分。

$当$n$=0时$, f( 0 ) = 1 。当 n $ = 1 时 $,f( 1 )=2。

当n = 2时，第 2 条直线为了产生最多的新区域，必须与第 1 条直线在圆内相交。这条新线本身被第 1 条线分成2段，每一段都将一个已有区域一分为二，所以新增了2个区域。则f(2)=f(1)+2=4

….

当我们画第 n 条直线时，为了使其增加的区域最多，它必须与前面已有的 n-1 条直线都在圆内相交。这n-1 个交点会将第 n 条直线 (在圆内的部分，即一条弦) 分割成 n 个线段。每一个线段都会把它所在的区域一分为二，从而增加一个新的区域。因此，第 n 条直线最多能增加 n 个新区域。
则$f(n)=f(n-1)+n=f(0)+1+2+3+\ldots\ldots+n=1+\frac{n(n+1)}2$

(2)圆周上n个点两两连线，线段在圆内的交点数目

这些交点由两条弦相交形成，每条弦由圆周上两个点决定。一个交点对应于四个点(因为两条弦的
四个端点确定一个交点)。因此，交点数目为从n个点中选取4个点的组合数：

$$C(n , 4 )$$

( 3 ) 这个有好几种情况

• 三个顶点都在圆周上，则为 $C_{n}^{3}$
• 两个顶点在圆周上，一个顶点在圆周内。在第二问的基础上，可以知道我们任意选择四个点，会一一对应一个交点。因此可以得到方案数为 $4*C_{n}^{4}$
• 一个顶点在圆周上，两个顶点在圆周内。这种情况下，两个在圆周内的顶点都是内部交点，且要在同一条弦上。构造这种三角形需要选择 5 个点。

每选择 5 个点，指定其中 1 个点为顶点（如P1），另外 4 个点（P2,P3,P4,P5）的两条对角线（P2P4, P3P5）会与 P1 发出的弦相交，形成满足条件的三角形。每组 5 个点，可以形成 5 个这样的三角形。

可以得到方案数为 $5*C_{n}^{5}$

• 三个顶点都在圆周内。这种三角形的三个顶点都是内部交点，它的三条边分别属于三条不同的弦。这三条弦必须两两相交。需要选择 6 个点。例如 P1, P2, P3, P4, P5, P6。连接对角点形成三条弦（P1P4, P2P5, P3P6），它们在内部构成的交点正好形成一个三角形。则可以得到为 $C_{n}^{6}$

总的方案数为 $C_{n}^{3}+4C_{n}^{4}+5C_{n}^{5}+C_{n}^{6}$

( 4 ) 这些线段将圆分成的部分数（利用欧拉公式）
利用欧拉公式对于平面图，顶点数 V、边数 E和面数 F满足 V－E＋F＝2。这里：

• 顶点数 V＝n＋(n/4)（n个圆上点和 (n/4)个交点）。
• 边数 E＝(n/2)＋2(n/4)（弦的数目为 (n/2)，每个交点增加2条边）。
  代入欧拉公式并考虑外部区域，得到面数：

$$F=1+E-V=1+\left[\left(\frac{n}{2}\right)+2\left(\frac{n}{4}\right)\right]-\left[n+\left(\frac{n}{4}\right)\right]=1+\left(\frac{n}{2}\right)+\left(\frac{n}{4}\right)-n$$

但需要注意的是，这个面数包括圆外部区域，因此圆内部分数为 F－1。最终圆内部分数为：

$$1+\left(\frac{n}{2}\right)+\left(\frac{n}{4}\right)$$

（这里直接给出了圆内部分数的标准公式，其中已调整了外部区域。）

9

1. 选择一个顶点，从其出发的$n-3$条对角线中选出两条，因此共$C(n-3,2)$种情况
   由于共$n$个点，因此总情况数为$n*C(n-3,2).$
2. 对于任意凸$n$边形，总对角线的个数为$\frac{n(n-3)}2$条，任意选两条不同的对角线就共有
   $C(\frac{n(n-3)}2,2)$种情况，而有公共点的对数包括共享顶点的情况数$nC(n-3,2)$,
   $\bar{\text{以及相交于内部的情况数}C}(n,4)$
   因此无公共点的方案数为$C(\frac{n(n-3)}2,2)-nC(n-3,2)-C(n,4)$

10

首先所有长度为n的字符串，一共有$3^n$个

分两种情况

情况一：x,y,z都是奇数 设这种方案数为A

情况二：x,y,z有一个是奇数，另外两个是偶数,设这种方案数为B

则$A+3B=3^n$

然后我们考虑单个字符的奇偶性，设$O_k$为长度为k的x为奇数次的方案数,$E_k$为偶数的对应情况。

长度为 k 的奇数 x 字符串，可以由以下两种方式得到

1. 一个长度为 k-1 的奇数 x 字符串，在末尾添上 y 或 z(共 $2×O_{k-1}$ 种)
2. 一个长度为 k-1 的偶数 x 字符串，在末尾添上 x(共 $E_{k-1}$ 种)

所以$O_k=2×O_{k-1}+E_{k-1}$ 这是一个等比数列，解得$O_n=(3^n-1)/2$

则$A+B=(3^n-1)/2$

解得$A=(3^n-3)/4$