第二次作业

1.

Tips

$n$ 个完全一样的球放到 $r$ 个有标志的盒 $(n⩾r)$ 中, 无一空盒, 试问有多少种方案?

将球排成一行, 形成 $n-1$ 个间隙. 从 $n-1$ 个间隙中选择 $r-1$ 个位置插入隔板, 将球划分为 $r$ 组 (每组对应一个盒子). 方案数为 $C(n-1,r-1)$.

2.

Tips

试证一整数是另一整数的平方的必要条件是该整数有奇数个因子.

对于任意正整数 $n$, 若 $n$ 为平方数 (即 $n=m^2$), 考虑其所有正因子. 对于每个因子 $d⩽m$, 存在对应的因子 $\frac{n}{d}⩾m$. 当 $d<m$ 时, $d$ 与 $\frac{n}{d}$ 为不同因子; 当 $d=m$ 时, $\frac{n}{d}=m$, 此时因子 $m$ 单独出现. 因此, 除 $m$ 外, 其余因子成对存在, 总因子数为偶数对数目加 1, 必为奇数. 由此可知, 平方数必有奇数个因子, 此为必要条件.

3.

Tips

在由 $n$ 个 0 及 $n$ 个 1 构成的字符串中, 在任意前 $k$ 个字符 中, 0 的个数不少于 1 的个数的字符串有多少?

显然含 $n$ 个 1, $n$ 个 0 的 $2n$ 位二进制数共有 $C(2n,n)$ 个, 下面考虑不满足要求的数目.

考虑一个含 $n$ 个 1, $n$ 个 0 的 $2n$ 位二进制数, 扫描到第 $2m+1$ 位上时有 $m+1$ 个 0 和 $m$ 个 1 (容易证明一定存在这样的情况), 则后面的 0-1 排列中必有 $n-m$ 个 1 和 $n-m-1$ 个 0. 将 $2m+2$ 及其以后的部分 0 变成 1, 1 变成 0, 则对应一个 $n+1$ 个 0 和 $n-1$ 个 1 的二进制数. 反之亦然 (相似的思路证明两者一一对应).

从而 $C_n=C(2n,n)-C(2n,n+1)$.

4.

Tips

(1) 在由 5 个 0, 4 个 1 组成的字符串中, 出现 01 或 10 的总次数为 4 的字符串, 有多少个?
(2) 在由 $m$ 个 0, $n$ 个 1 组成的字符串中, 出现 01 或 10 的总次数为 $k$ 的字符串, 有多少个?

(1)

分析
相邻位不同的次数 (即转换次数) 为 4, 意味着字符串被分为 5 个连续的相同字符块 (块数=转换次数 +1) . 块结构有两种可能:

• 起始为 0: 块结构为 0、1、0、1、0 (3 个 0 块和 2 个 1 块) .
• 起始为 1: 块结构为 1、0、1、0、1 (3 个 1 块和 2 个 0 块) .

计算

• 起始为 0:
  • 将 5 个 0 分为 3 个块 (每块 $⩾1$): 方法数为 $C(5-1,3-1)=C(4,2)=6$.
  • 将 4 个 1 分为 2 个块 (每块 $⩾1$): 方法数为 $C(4-1,2-1)=C(3,1)=3$.
  • 总情况数: $6\times 3=18$.
• 起始为 1:
  • 将 4 个 1 分为 3 个块 (每块 $⩾1$): 方法数为 $C(4-1,3-1)=C(3,2)=3$.
  • 将 5 个 0 分为 2 个块 (每块 $⩾1$): 方法数为 $C(5-1,2-1)=C(4,1)=4$.
  • 总情况数: $3\times 4=12$.

最终答案:
总情况数为 $18+12=\boxed{{\displaystyle 30}}$.

---

(2)

分析
设转换次数为 k, 则字符串被分为 $k+1$ 个连续块. 块结构有两种可能:

1. 起始为 0: 0 块数为 $t=\lceil \frac{k+1}{2}\rceil$, 1 块数为 $s=\lfloor \frac{k+1}{2}\rfloor$.
2. 起始为 1: 1 块数为 $t=\lceil \frac{k+1}{2}\rceil$, 0 块数为 $s=\lfloor \frac{k+1}{2}\rfloor$.

计算

• 起始为 0 的条件:
  • $m⩾t$ 且 $n⩾s$, 方法数为 $C(m-1,t-1)C(n-1,s-1)$.
• 起始为 1 的条件:
  • $n⩾t$ 且 $m⩾s$, 方法数为 $C(n-1,t-1)C(m-1,s-1)$.

最终答案:
总情况数为两种起始情况之和:

$$\boxed{{\displaystyle C(m-1,\lceil \frac{k+1}{2}\rceil -1)C(n-1,\lfloor \frac{k+1}{2}\rfloor -1)+C(n-1,\lceil \frac{k+1}{2}\rceil -1)C(m-1,\lfloor \frac{k+1}{2}\rfloor -1)}}$$