USTC课程资源分享在线

Contributors

• 1. 计算50！的尾部有多少个零？
• *2.比5400大的四位整数中，数字2，7不出现，且各位数字不同的整数由多少个?
• *3.12个人围坐在圆桌旁，其中一个拒绝与另一个相邻，问有多少种安排方法？
• 4. 有颜色不同的四盏灯。
  • (1) 把它们按不同的次序全部挂在灯杆上表示信号，共有多少种不同的信号？
  • (2) 每次使用一盏、二盏、三盏或四盏灯按一定的次序挂在灯杆上表示信号，共有多少种不同的信号？
  • (3) 在(2)中，如果信号与灯的次序无关，共有多少种不同的信号？
• 5. 现在有100件产品，从中任意抽取3件。
  • (1)共有多少种抽法？
  • (2) 如果100件产品中有2件次品，那么抽出的产品中至少有一件是次品的概率是多少？
  • (3) 如果100件产品中有2件次品，那么抽出的产品中恰好有一件是次品的概率是多少？
• 6. 把$q$个负号和$p$个正号排在一条直线上，使得没有两个负号相邻，证明不同的排法有$C_{p+1}^q$种。
• 7. 8个棋子大小相同，其中5个红的，3个蓝的，把它们放在$8\times 8$的棋盘上，每行每列只能放一个，问有多少种放法？若放在$12\times 12$的棋盘上，结果如何？
• 8. 有纪念章4枚、纪念册6本，赠送给10位同学，每人得一件，共有多少种不同的送法?
• *9.
  • (1)从整数1，2，…,100中选出两个数，使得它们的差正好是7，有多少种不同的选法?
  • (2)如果要求两数之差小于等于7，又有多少种不同的选法？（注意：应该是两数之差的绝对值小于等于7更加准确地反映出题意）
• *10.试求不定方程$x_1+x_2+\cdot +x_8=40$满足 $x_i\ge i(i=1,2,\cdot ,8)$的整数解个数？
• 11. 在一次选举中，甲、乙分别得到a张和b张票(a>b)，将全部a+b张选票按某种顺序排列，依次计票时甲所得的票数总是比乙多.问这种排列方法有多少种？
• 12. n个不同的字符顺序进栈恰一次，问有多少种不同的出栈方式？
• *13. 计数(0, 0)点到(n, n)点的不穿过直线y=x的非降落路径数.
• 14. 有n个不同的整数，从中取出两组来，要求第一组的最小数大于第二组里的最大数，问有多少种方案？
• 15. 试求n个完全一样的骰子能掷出多少种不同的点数？
• 16.凸10边形的任意3条对角线不共点，试求该凸10边形的对角线交于多少个点？又把所有的对角线分割成多少段?
• 17. 设 $n=p_1^{\alpha 1}{p}_2^{\alpha 2}\cdot p_l^{\alpha l}$,其中$p_1,p_2,\dots p_l$是l个不同素数，试求能整除n的正整数数目。
• 18. 将52张牌平均分给4个人，问每个人有一个5张牌的同花顺的概率是多少？
• 19.取定空间中的25个点，其中任意4点均不共面，问它们能决定多少个三角形？又能决定多少个四面体？
• 20. 考虑集合$1,2,\cdots ,n+1$的非空子集.
  • (1)证明最大元素恰好是j的子集数为$2^{j-1}$.
  • (2)利用(1)的结论证明 $1+2+2^2+\cdots +2^n=2^{n+1}-1$
• 21. 从整数1,2,…1000中选取3个数，使得它们的和正好被4整除，问有多少种选法？
• 22.
  • (1)在由5个0和4个1组成的字符串中，出现01或10的总的次数为4的字符串有多少个？
  • (2)在由m个0和n个1组成的字符串中，出现01或10的总的次数为k的字符串有多少个?
• *23. 5 封不同的信用通信通道传送，在两封信之间至少要放3个空格，一共要加入15个空格，问有多少种方法？
• 24. 将a,b.c,d,e,f,g,h排成一行，要求a在b的左侧，b在c的左侧，问有多少种排法?
• 25.从1至100的整数中不重复的选取两个数组成有序对(x, y)，使得x与y的乘积xy不能被3整除，
• 26. 在$m\times n$的棋盘中选取两个相邻的方格（即有一条公共边的方格）有多少种不同的选取方法？
• 27. 某电影院票房前有2n个人排队，每人欲购买一张5元的电影票.在这些人中，有n个人，每人有一张5元钞票，其余每人有一张10元钞票，而票房在卖票前无任何钞票，问使得每个人都能顺利地买到电影票的排队方式有多少种？
• 28.证明下列组合恒等式：
  • （1） ${\sum }_{k=0}^n(-1{)}^k\cdot k^2\cdot C_n^k=0$
  • （2）${\sum }_{k=0}^n=\frac{1}{(k+1)(k+2}{C}_n^k=\frac{2^{n+2}-n-3}{(n+1)(n+2)}$
  • （3）${\sum }_{k=0}^n\frac{k+2}{k+1}{C}_n^k=\frac{(n+3)\cdot 2^n-1}{n+1}$
  • （4）${\sum }_{k=0}^n(k+1{)}^2{C}_n^k=2^{n-2}\cdot (n^2+5n+4)$
  • （5） ${\sum }_{k=0}^n\frac{1}{k+2}\cdot C_n^k=\frac{n\cdot 2^{n+1}+1}{(n+1)(n+2)}$
  • （6）${\sum }_{k=0}^n{C}_{2n}^k=2^{2n-1}+\frac{1}{2}{C}_{2n}^n$
• 29. 以 $h_m(n)$表示用m种颜色去涂$2\times n$棋盘，使得相邻格子异色的涂色数，证明$h_m(n)=(m^2-3m+3{)}^{n-1}\cdot m\cdot (m-1)$
• 30. 上题中，若以 $h_m^{\prime }(n)$表示m种颜色去涂 $2\times n$ 棋盘，使得相邻格子异色且每种颜色至少使用一次的涂色方案，求 $h_m^{\prime }(n)$ 的计数公式.
• 31. 有20根完全相同的木棍从左到右竖立成一行，占据20个位置。要从中选出6根。
  • (1) 有多少种选择?
  • (2) 如果选出的木棍中没有两根是相邻的，又有多少种选择？
  • (3) 如果在所选出的每一对木棍之间必须至少有两根棍，有多少中选择？

转载自liuzengh/combinatorial-mathematics

1. 计算50！的尾部有多少个零？

编程题 Leetcode 172 Factorial Trailing Zeroes

def fun(n):
    if n<5:
        return 0
    return n//5 + fun(n//5)
fun(50)

一种有12个零。 注意到只能由$2\times 5$产生0(而如果一个数本身含有0， 一定是能被2和5整除的。)

{2，5}，{12,15}，{32,35}, {42,45}, {4,25}, 10, {20,50} 30, 40

*2.比5400大的四位整数中，数字2，7不出现，且各位数字不同的整数由多少个?

加法原则，如果首位大于5则，可以为6，8， 9, 于是有 $3\times 7\times 6\times 5$。如果首位为5，则次高位可以为4，6， 8， 9,于是有$1\times 4\times 6\times 5$，所以总的个数为: $3\times 7\times 6\times 5+1\times 4\times 6\times 5=750$

*3.12个人围坐在圆桌旁，其中一个拒绝与另一个相邻，问有多少种安排方法？

减法原则。$\frac{12!}{12}-2\frac{11!}{11}=9\times 10!$

4. 有颜色不同的四盏灯。

(1) 把它们按不同的次序全部挂在灯杆上表示信号，共有多少种不同的信号？

$A_4^4=24$

(2) 每次使用一盏、二盏、三盏或四盏灯按一定的次序挂在灯杆上表示信号，共有多少种不同的信号？

$A_4^1+A_4^2+A_4^3+A_4^4=64$

(3) 在(2)中，如果信号与灯的次序无关，共有多少种不同的信号？

$C_4^1+C_4^2+C_4^3+C_4^4=2^4-1=15$

5. 现在有100件产品，从中任意抽取3件。

(1)共有多少种抽法？

$C_{100}^3=161700$

(2) 如果100件产品中有2件次品，那么抽出的产品中至少有一件是次品的概率是多少？

$1-\frac{C_{97}^3}{C_{100}^3}$

(3) 如果100件产品中有2件次品，那么抽出的产品中恰好有一件是次品的概率是多少？

$\frac{C_3^1{C}_{97}^2}{C_{100}^3}$

6. 把$q$个负号和$p$个正号排在一条直线上，使得没有两个负号相邻，证明不同的排法有$C_{p+1}^q$种。

证明:先把$p$个正号排在一条直线上，那么包括两头在内，留出了$p+1$个空位置。由于负号不能相邻，所以原问题等价于从这$p+1$个空位置中选择$q$个位置把负号放入其中，则总的个数为：$C_{p+1}^q$

7. 8个棋子大小相同，其中5个红的，3个蓝的，把它们放在$8\times 8$的棋盘上，每行每列只能放一个，问有多少种放法？若放在$12\times 12$的棋盘上，结果如何？

参考2.4节例6

编程题Leetcode 51.N-Queens, 52.N-Queens II, 36-Valid Sudoku, 37.SudoKu Solver 暴力枚举；回溯法

先选位置再选颜色。

对于$8\times 8$的棋盘，每行都必须要放置一个棋子，可以先固定行，然后第1个棋子有8种列坐标可选，第2个棋子有7种列坐标可选，依次下去，总的选法数为8！，然后从8个棋子种选择5个着色为红色（这一步也可以看成计算多重集合$M=\{5\cdot R,3\cdot B\}$上的全排列个数）。$8!C_8^5=\frac{(8!{)}^2}{5!3!}$

如果是$12\times 12$的棋盘则先从12行中选择8行（无序），在从12列中排列8列(有序)，然后选择5个棋子着为红色即可 $C_{12}^8{A}_{12}^8{C}_8^5=\frac{(12!{)}^2}{3!(4!{)}^{2}5!}$

8. 有纪念章4枚、纪念册6本，赠送给10位同学，每人得一件，共有多少种不同的送法?

解法一：从10位同学中选择4位送纪念章，那么后剩余6位一定是送纪念册咯。$C_{10}^4$

解放二：匹配问题，可以看成给10个人打上送纪念章或纪念册的标签，那么就是多重集合$M=\{4\cdot 0,6\cdot 1\}$的全排列。（0，1分别对应纪念章和纪念册）

*9.

(1)从整数1，2，…,100中选出两个数，使得它们的差正好是7，有多少种不同的选法?

可以取两个数$x,y$，为不失一般性不妨取 $x<y$，则有$y=x+7$，由于$1\le x\le 100,1\le y\le 100$,则可以取$(1,8),(2,9),\dots ,(93,100)$.则一种有93种取法

(2)如果要求两数之差小于等于7，又有多少种不同的选法？（注意：应该是两数之差的绝对值小于等于7更加准确地反映出题意）

可以取两个数$x,y$，为不失一般性不妨取 $x<y$，则有$y=x+7$，由于$1\le x\le 100,1\le y\le 100$， 当x取1时，y可以取{2，3，4，5，6，7，8}，可以类推到x取到93的情况，当x取{94，95，… ,99, 100},y只需要取比x大的数即可。总的选法为：$93\times 7+{\sum }_{i=94}^{100}(100-i)=672$

*10.试求不定方程$x_1+x_2+\cdot +x_8=40$满足 $x_i\ge i(i=1,2,\cdot ,8)$的整数解个数？

令 $y_i=x_i-i$,则${\sum }_{i=1}^8{y}_i={\sum }_{i=1}^8{x}_i-{\sum }_{i=1}^8={\sum }_{i=1}^8{x}_i-36=40-36=4$

$C_{8+4-1}^{8-1}=C_{11}^4=330$

11. 在一次选举中，甲、乙分别得到a张和b张票(a>b)，将全部a+b张选票按某种顺序排列，依次计票时甲所得的票数总是比乙多.问这种排列方法有多少种？

该问题与第12题是等价的。相当于共有a个元素进栈，那么需要出栈b个元素一共有多少种不同的可能。 把1当成进栈，0当成出栈，那么共有（a+b）个移动次序，并满足任意时刻，进栈数大于出栈数（a>b）。

该问题与13题是等价的。相当于于计数(0, 0)点到(a, b)点的不穿过直线y=x的非降落路径数。（只考虑直线y=x下三角的情况）设往右走对应于甲的票，往上走对应于乙的票，那么不穿过直线y=x就保证了依次计票时甲所得得票数总是比乙多。

方法一：可以转换成13题的几何形式

方法二：写成递归函数，Catalan数

$C_{a+b-2}^{a-1}-C_{a+b-2}^a$

12. n个不同的字符顺序进栈恰一次，问有多少种不同的出栈方式？

参考7.2节Catalan数

编程题 Leetcode 946.Validate Stack Sequences 模拟

设f(n)为n个不同字符对应的计数。$f(n)=\frac{1}{n}{C}_{2n-2}^{n-1}$ $$f(n)=\sum _{i=0}^{n-1}f(i)f(n-i+1),f(0)=1,f(1)=1$$

*13. 计数(0, 0)点到(n, n)点的不穿过直线y=x的非降落路径数.

参考2.4节例3，7.2节例3

编程题 Leetcode 62.Unique Paths, 63 Unique Paths II 写成递推方程，用递归或者动态方程计算；用组合数表达出总的次数，转而编程计算组合数

从可以先从(0,0)到达(0, 1)或者(1, 0)，这两个点到(n,n)而不穿过$y=x$的非降落路径数是相等的。于是可以考虑从(1,0)到(n，n)不穿过直线$y=x$的非降落路径数，由于不穿过$y=x$，那么必定是要经过点(n, n-1)。

从(1,0)到(n,n-1)的非降落路径数为：$C_{2n-2}^{n-1}$。

从(1, 0)到(n, n-1)穿过直线$y=x$的非降落路径和从(0, 1)到(n, n-1)的非降落路径是对称的等于：$C_{2n-2}^n$

于是从点(0, 0)点到(n, n)点的不穿过直线y=x的非降落路径数为： $$2(C_{2n-2}^{n-1}-C_{2n-2}^n)=2(\frac{(2n-2)!}{n!(n-1)!}-\frac{(2n-2)!}{n!(n-2)!})=2\frac{(2n-2)!}{n!(n-1)!}=\frac{2}{n}{C}_{2n-2}^{n-1}$$

14. 有n个不同的整数，从中取出两组来，要求第一组的最小数大于第二组里的最大数，问有多少种方案？

可以把这n个数一一映射到集合{1, 2, …, n}上。依次取确定第二组里最大的数为n，n-1，…, 1;相应的第二组可以从剩余的n-1, n-2, …. 0个数中任意取整数构成一个组。则有: $$f(n)=\sum _{i=1}^n{2}^{i-1}\ast (2^{n-i}-1)=n{2}^{n-1}-2^n+1$$

15. 试求n个完全一样的骰子能掷出多少种不同的点数？

一个骰子有6个面，点数依次为1,2,3,4, 5, 6。则$f(n)={\sum }_i^n{x}_i,0\le x_i\le 6$, 计算函数f(n)值域的大小，为 $6^n$。

16.凸10边形的任意3条对角线不共点，试求该凸10边形的对角线交于多少个点？又把所有的对角线分割成多少段?

相交的点数：$C_n^4$

每条对角线分割成的段数：$\frac{n(1+{\sum }_{i=3}^{n-1}(i-2)(n-i))}{2}$

17. 设 $n=p_1^{\alpha 1}{p}_2^{\alpha 2}\cdot p_l^{\alpha l}$,其中$p_1,p_2,\dots p_l$是l个不同素数，试求能整除n的正整数数目。

素数分解定理，确保了任意整数能够被分解为多个素数的乘积形式。使用乘法法则，总的数目为： $$\prod _{i=1}^l(1+{\alpha }_i)$$

18. 将52张牌平均分给4个人，问每个人有一个5张牌的同花顺的概率是多少？

2： {3， 4， 5， 6， 7}, {4， 5， 6， 7， 8}， {5， 6， 7， 8， 9}

1： {6， 7， 8， 9， 10}， {7， 8， 9， 10 ，J}

19.取定空间中的25个点，其中任意4点均不共面，问它们能决定多少个三角形？又能决定多少个四面体？

三角形个数$C_{25}^3$, 四面体个数$C_{25}^4$。

20. 考虑集合$1,2,\cdots ,n+1$的非空子集.

(1)证明最大元素恰好是j的子集数为$2^{j-1}$.

如果集合A中的最大元素为j,那么A还可能包含$j-1,j-2,\cdots ,1$的数。利用乘法法则，个数为$2^{j-1}$

(2)利用(1)的结论证明 $1+2+2^2+\cdots +2^n=2^{n+1}-1$

根据最大元素的不同可以把集合$1,2,\cdots ,n+1$划分为n+1个不互斥的子集,但是不包含空集。从而有: $$\sum _{j=1}^{n+1}{2}^{j-1}=2^{n+1}-1$$

21. 从整数1,2,…1000中选取3个数，使得它们的和正好被4整除，问有多少种选法？

按对4取模的结果{0, 1, 2, 3}把这1000个数划分为4个等价类，代表元分别为0，1，2，3,每个类的元素个数相等。则有{013, 112, 220, 332, 000}，总的选法为: $250^3+250C_{250}^2\times 3+C_{250}^3$

22.

(1)在由5个0和4个1组成的字符串中，出现01或10的总的次数为4的字符串有多少个？

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

*23. 5 封不同的信用通信通道传送，在两封信之间至少要放3个空格，一共要加入15个空格，问有多少种方法？

如果第1封信之前和第5封信之后允许放置空格，则$x_1+x_2+x_3+x_4+x_5+x_6=15$, 其中$0\le x_1,3\le x_2,3\le x_3,3\le x_4,3\le x_5,0\le x_6$。等价于 ${\sum }_{i=1}^6{y}_i=3$, 其中$y_1=x_1,y_6=x_6,y_i=x_i-3(2\le i\le 5),0\le y_i$。则总的次数为：$A_5^5{C}_8^3=6720$

24. 将a,b.c,d,e,f,g,h排成一行，要求a在b的左侧，b在c的左侧，问有多少种排法?

设n为字母的个数，根据b所在的位置可以为$2，3，\cdots ,n-1$ $$\sum _{i=1}^{n-1}{A}_i^i{A}_{n-i-1}^{n-i-1}$$

25.从1至100的整数中不重复的选取两个数组成有序对(x, y)，使得x与y的乘积xy不能被3整除，

按对3取模的结果{0, 1, 2}把这100个数划分为3个等价类代表元分别为0，1，2，三个类的元素个数分别为：33， 34， 33。不能被3整除的取法为11， 12，22。总的个数为: $2\times (C_{34}^2+C_{34}^1{C}_{33}^1+C_{33}^2)$

26. 在$m\times n$的棋盘中选取两个相邻的方格（即有一条公共边的方格）有多少种不同的选取方法？

从$(i,j)$可以到$(i+1,j),(i,j+1)$， 总的选取方法为：$m\times (n-1)+n\times (m-1)$

27. 某电影院票房前有2n个人排队，每人欲购买一张5元的电影票.在这些人中，有n个人，每人有一张5元钞票，其余每人有一张10元钞票，而票房在卖票前无任何钞票，问使得每个人都能顺利地买到电影票的排队方式有多少种？

思路和题11，12，13类似。从前往后计数，拥有5元钞票的人的个数必须大于等于10人钞票的人数；同时要考虑到每个人是不同的物体。

$$n!n!\frac{1}{n}{C}_{2n-2}^{n-1}$$

28.证明下列组合恒等式：

（1） ${\sum }_{k=0}^n(-1{)}^k\cdot k^2\cdot C_n^k=0$

怎么看着像卷积公式

（2）${\sum }_{k=0}^n=\frac{1}{(k+1)(k+2}{C}_n^k=\frac{2^{n+2}-n-3}{(n+1)(n+2)}$

（3）${\sum }_{k=0}^n\frac{k+2}{k+1}{C}_n^k=\frac{(n+3)\cdot 2^n-1}{n+1}$

（4）${\sum }_{k=0}^n(k+1{)}^2{C}_n^k=2^{n-2}\cdot (n^2+5n+4)$

（5） ${\sum }_{k=0}^n\frac{1}{k+2}\cdot C_n^k=\frac{n\cdot 2^{n+1}+1}{(n+1)(n+2)}$

（6）${\sum }_{k=0}^n{C}_{2n}^k=2^{2n-1}+\frac{1}{2}{C}_{2n}^n$

29. 以 $h_m(n)$表示用m种颜色去涂$2\times n$棋盘，使得相邻格子异色的涂色数，证明$h_m(n)=(m^2-3m+3{)}^{n-1}\cdot m\cdot (m-1)$

用坐标(x, y)来表示格子的位置 第一次涂(1,1)，有m种选择，第二次涂(2, 1)有m-1种选择。现在涂(1, 2)和(2,2)，有两种情况。如果(1,2)和（2，1）的颜色相同，则(2,2)有m-1种选择；如果(1,2)和(2,1)颜色不同则有(m-2)种选择，（2，2）也有m-2种选择；可以看出$2\times (n-2)$和$2\times (n-1)$的情况类似，依次归纳下去n-1次则有

$h_m(n)=m\cdot (m-1)((m-1)+(m-2)\cdot (m-2){)}^{n-1}=(m^2-3m+3{)}^{n-1}\cdot m\cdot (m-1)$

30. 上题中，若以 $h_m^{\prime }(n)$表示m种颜色去涂 $2\times n$ 棋盘，使得相邻格子异色且每种颜色至少使用一次的涂色方案，求 $h_m^{\prime }(n)$ 的计数公式.

二项式反演公式:设$\{a_n{\}}_{n\ge 0}$和$\{b_n{\}}_{n\ge 0}$是两个数列，s是非负整数，如果对任意的不小于s的整数n，都有$a_n={\sum }_{k=s}^n{C}_n^k{b}_k$,则对于如果对任意的不小于s的整数n，都有 $b_n={\sum }_{k=s}^n(-1{)}^{n-k}{C}_n^k{a}_k$

$h_m^{\prime }(n)={\sum }_{k=2}^m(-1{)}^{m-k}{C}_m^k(k^2-3k+3{)}^{n-1}k(k-1)$

31. 有20根完全相同的木棍从左到右竖立成一行，占据20个位置。要从中选出6根。

(1) 有多少种选择?

考虑位置不同 $C_{20}^6=38760$

(2) 如果选出的木棍中没有两根是相邻的，又有多少种选择？

${\sum }_{i=0}^7{x}_i=20-6=14,0\le x_1,x_7;1\le x_2,x_3,x_4,x_5,x_6$， ${\sum }_{i=0}^7{y}_i=9,y_i\ge 0$, 总的个数为$C_{7+9-1}^9=5005$

def f(n, m):
    if m == 0:
        return 1
    if n < (2*m - 1):
        return 0
    elif n ==  2*m-1:
        return 1
    else:
        tmp = 0
        for i in range(1, n+1):
            tmp += f(n-i-1, m-1)
        return tmp
f(20, 6)

(3) 如果在所选出的每一对木棍之间必须至少有两根棍，有多少中选择？

${\sum }_{i=0}^7{x}_i=20-6=14,0\le x_1,x_7;2\le x_2,x_3,x_4,x_5,x_6$， ${\sum }_{i=0}^7{y}_i=4,y_i\ge 0$, 总的个数为$C_{7+4-1}^4=210$

def g(n, m):
    if m == 0:
        return 1
    if n < (3*m - 2):
        return 0
    elif n ==  3*m-2:
        return 1
    else:
        tmp = 0
        for i in range(1, n+1):
            tmp += g(n-i-2, m-1)
        return tmp
        
g(20, 6)