USTC课程资源分享在线

Contributors

• 1.在1与1000之间不能被4，5和6整除的数有多少个？
• *2.求1到500中能被3和5整除，但是不能被7整除的数的个数？
• *3. 求1与1000之间既不是平方数又不是立方数的整数的个数。
• *4. 求多重集合 $S=\{\infty \cdot a,3\cdot b,5\cdot c,7\cdot d\}的10组合数$
• *5. 求不定方程$x_1+x_2+x_3=14$的数值不超过8的正整数解的个数。
• *6. 在宴会后，7位男士检查他们的帽子，问有多少种方法，使得
  • (1)没有人接到自己的帽子？
  • (2)至少有一人接到自己的帽子？
  • (3)至少有两人接到自己的帽子？
• *7.求集合$\{1,2,\cdot ,n\}$的排列数，使得在排列中正好有k个整数在它们的自然位置上（所谓自然位置，就是整数i排在第i位上）
• 8. 求多重集合$S=\{3\cdot a,4\cdot b,2\cdot c\}$的全排列数，使得在这些排列中同一个字母的全体不能相邻（例如，不允许 abbbbcaac,但允许baabbacbc）
• 9. $D_n$是偶数当且仅当n是奇数。
• *10.证明 $Q_n=D_n+D_{n-1}$

转载自liuzengh/combinatorial-mathematics

from scipy.special import perm, comb, factorial

1.在1与1000之间不能被4，5和6整除的数有多少个？

令集合$S=1,2,3,\cdots ,1000$, 记集合$A_1,A_2,A_3$分别表示从1到1000中能被4，5和6整除的数。则1与1000之间不能被4，5和6整除的数的个数为: $|S|-(|A_1|+|A_2|+|A_3|)+(|A_1|\cap |A_2|+|A_2|\cap |A_3|+|A_3|\cap |A_1|)-(|A_1|\cap |A_2|\cap |A_3|)=1000-(\lfloor \frac{1000}{4}\rfloor +\lfloor \frac{1000}{5}\rfloor +\lfloor \frac{1000}{6}\rfloor )+(\lfloor \frac{1000}{20}\rfloor +\lfloor \frac{1000}{30}\rfloor +\lfloor \frac{1000}{24}\rfloor )-\lfloor \frac{1000}{120}\rfloor =500$

*2.求1到500中能被3和5整除，但是不能被7整除的数的个数？

能被3和5整除等价于能被15整除，在能被15整除的基础上减去同时能被7整除的书，就等于能被15整除而不能被7整除的数。 能被15整除的数的个数为: $\lfloor \frac{500}{15}\rfloor =33$; 能被105整除的数的个数为: $\lfloor \frac{500}{105}\rfloor =3$;所以求1到500中能被3和5整除，但是不能被7整除的数的个数为: $33-3=30$

*3. 求1与1000之间既不是平方数又不是立方数的整数的个数。

令 $A=\{1,2,3,\cdots ,1000\}$,则记$A_1,A_2$分别为1到1000中的平方数集合和立方数的集合，$A_1\cap A_2$表示1到1000中既是平方数又是立方数的的集合则有: $$|A|=1000$$ $$|A_1|=\lfloor \sqrt[2]{1000}\rfloor =31$$ $$|A_2|=\lfloor \sqrt[3]{1000}\rfloor =10$$ $$A_1\cap A_2=\{1,64,729\}$$ 于是 ${\overline{A}}_1\cap {\overline{A}}_2$ 表示$A$中既不是平方数又不是立方数的整数, 则1与1000之间既不是平方数又不是立方数的整数的个数: $$|{\overline{A}}_1\cap {\overline{A}}_2|=|A|-(|A_1|+|A_2|)+(|A_1\cap A_2|)=1000-(31+10)+3=962$$

*4. 求多重集合 $S=\{\infty \cdot a,3\cdot b,5\cdot c,7\cdot d\}的10组合数$

参考 4.3节例1

令 $S_{\infty }=\{\infty \cdot a,\infty \cdot b,\infty \cdot c,\infty \cdot d\}$, 则$S_{\infty }$的10组合数为:$C_{10+4-1}^{10}=C_{13}^3=286$, 设集合A是$S_{\infty }$的10组合数全体，则$|A|=286$,定义A上的性质集合$P=\{P_1,P_2,P_3\}$,其中:

$P_1$:A中的元素b的的个数大于等于4；

$P_2$:A中的元素c的的个数大于等于6；

$P_3$:A中的元素d的的个数大于等于8；

将满足性质 $P_i$的10组合数全体记为$A_i(1\le i\le 3)$, 那么依次有: $A_1=C_{10-4+4-1}^{10-4}=84$, $A_2=C_{10-6+4-1}^{10-6}=35$, $A_2=C_{10-8+4-1}^{10-8}=10$。

$A_1\cap A_2=1$, $A_2\cap A_3=0$, $A_3\cap A_1=0$

$A_1\cap A_2\cap A_3=0$.

所以A中的元素b的的个数小于等于3， 元素c的的个数小于等于5，元素d的的个数小于等于7的10组合数个数为: ${\overline{A}}_1\cap {\overline{A}}_2\cap {\overline{A}}_3=|A|-(A_1+A_2+A_3)+(A_1\cap A_2+A_2\cap A_3+A_3\cap A_1)-(A_1\cap A_2\cap A_3)=286-(84+35+10)+1-0=158$

*5. 求不定方程$x_1+x_2+x_3=14$的数值不超过8的正整数解的个数。

$C_{14-1}^2-3C_{14-8-1}^2=48$

*6. 在宴会后，7位男士检查他们的帽子，问有多少种方法，使得

(1)没有人接到自己的帽子？

$D_7=7!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}-\frac{1}{7!})=1854$

(2)至少有一人接到自己的帽子？

$7!-D_7=5040-1854=3186$

(3)至少有两人接到自己的帽子？

总数 - 没有人接到自己的帽子的方法数 -恰好只有一个人接到自己的帽子的方法数： $7!-D_7-7\ast D_6=5050-1854-7\times 256=1331$

*7.求集合$\{1,2,\cdot ,n\}$的排列数，使得在排列中正好有k个整数在它们的自然位置上（所谓自然位置，就是整数i排在第i位上）

$N(k)={\sum }_{r=0}^{n-k}(-1{)}^r{C}_{k+r}^{k}w(k+r)={\sum }_{r=0}^{n-k}(-1{)}^r{C}_{k+r}^k(n-k-r)!$

8. 求多重集合$S=\{3\cdot a,4\cdot b,2\cdot c\}$的全排列数，使得在这些排列中同一个字母的全体不能相邻（例如，不允许 abbbbcaac,但允许baabbacbc）

$\frac{(3+4+2)!}{3!4!2!}-(\frac{(1+4+2)!}{4!2!}+\frac{(3+1+2)!}{3!2!}+\frac{(3+4+1)!}{3!4!})+(\frac{(1+1+2)!}{2!}+\frac{(3+1+1)!}{3!}+\frac{(1+4+1)!}{4!})-(1+1+1)!=1260-(105+60+280)+(12+20+30)-6=871$

9. $D_n$是偶数当且仅当n是奇数。

根据递推公式： $D_n=(n-1)(D_{n-1}+D_{n-2});D_1=0,D_2=1$

$D_n=n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots +(-1{)}^n\frac{1}{n!})$

*10.证明 $Q_n=D_n+D_{n-1}$

$D_n=n!-C_n^1(n-1)!+C_n^2(n-2)!+\cdots (-1{)}^n{C}_n^n$ $D_{n-1}=(n-1)!-C_{n-1}^1(n-2)!+C_{n-1}^2(n-3)!+\cdots (-1{)}^{n-1}{C}_{n-1}^{n-1}$ $D_n+D_{n-1}=n!-(C_n^1-C_{n-1}^0)(n-1)!+(C_n^2-C_{n-1}^1)(n-2)!+\cdots +(C_n^k-C_{n-1}^{k-1})(n-k)!+\cdots +(C_n^n-C_{n-1}^{n-1})0!=n!-C_{n-1}^1(n-1)!+C_{n-1}^2(n-2)!+\cdots +(-1{)}^k{C}_{n-1}^k(n-k)!+\cdots (-1{)}^{n-1}{C}_{n-1}^{n-1}1!=Q_n$