NOIP初赛一些题目

从 1 到 2018 这 2018 个数中，共有__________个包含数字 8 的数。

这道题目应该使用组合计数的知识去做，首先考虑补集就是 1 到 2018 中不包含数字 8 的数的个数。

1 位数，一共有 8 个。

2 位数，因为每一位不能有 8 且第一位不能是 0 ，所以有 (8*9=72) 个，

3 位数同理，(8*9*9=648) 个。

4 位数分为 1000 到 1999 和 2000 到 2018 两个部分考虑，1000 到 1999 中有 (1*9*9*9=729) 个，2000 到 2018 中有 (2018-2000+1-2=17) 个。

所以共有(2018-1+1-8-72-648-729-17=544)个包含数字 8 的数

有数字1,1,2,4,8,8所组成的不同的四位数的个数是_____.

这道题我们还是要用组合计数知识去解决。

首先，我们先枚举在选择的 (4) 个数有多少个数相同。
所以我们算了一下，全都不相同的时候答案就是 (4! = 12) 。

只有一对相同，一共有 (2*3 = 6) 种选法，对于每一种选法，我们可以看做固定两个相同的数的位置，剩余的任意选，所以就是 (C_4^2*2!*6 = 72) 种情况。

有两对相同，一共有 (1) 种选法，思考方式和上面一样，所以有 (C_4^2*1! = 6) 种情况。

所以最终答案就是 (4+6+72 = 102) 。

由四个不同的点构成的简单无向连通图的个数是（）。

A. 32
B. 35
C. 38
D. 41

因为有 (4) 个点，所以最多有 (n*(n-1)/2) 条边，其实只要边的数目大于 (3) ，这张图肯定联通，边数小于 (3) ，这张图肯定不能联通。

所以我们只需要考虑等于 (3) 的情况，当边数等于 (3) 的时候只有围成一个三角形和单独的一个点的时候不能联通，所以我们之间用 (C_4^3 = 4) 来计算出来不能联通的方案数。

所以答案就是 (C_6^3-C_4^3+C_6^4+C_6^5+C_6^6 = 38) 。

因为边有区别，且和选出来的顺序无关，所以可以用组合数来算。

现有一只青蛙，初始时在 n 号荷叶上。当它某一时刻在 k 号荷叶上时，下一时刻将等概率地随机跳到 1, 2, …, k 号荷叶之一上，直至跳到 1 号荷叶为止。当 n = 2 时，平均一共跳 2 次；当 n = 3 时，平均一共跳 2.5 次。则当 n = 5 时，平均一共跳_________次。

设 (f(i)) 为期望要跳 (i) 次到达 (1) 号点。

显然 (f(1)=0) ，因为我们不需要跳直接就在 (1) 号点。

有 (frac{1}{5}) 的概率跳到 (1) ，花费 (1+f(1)) 。

有 (frac{1}{5}) 的概率跳到 (2) ，花费 (1+f(2)) 。

……

有 (frac{1}{5}) 的概率跳到 (5) ，答案为 (1+f(5)) 。

加一是因为又多跳了一步。

然后推广到一般情况

[f(k)=sum_{i=1}^kfrac{1}{k}(f(i)+1) ]

[f(k)=frac{1}{k}sum_{i=1}^kf(i)+1 ]

[f(k)=frac{1}{k}sum_{i=1}^{k-1}+frac{1}{k}f(k)+1 ]

移项，合并同类项，将系数除到另一边，得到

[f(k)=frac{1}{k-1}sum_{i=1}^{k-1}+frac{k}{k-1} ]

然后我们就可以愉快地代数求值了，答案就是 (frac{35}{12}) 。

还有就是初赛的那本书对这道题的分析第二个式子是错误的。

书架上有21本书，编号从1到21，从其中选4本，其中每两本的编号都不相邻的选法一共有______种。

这道题目可以转化为在 (17) 个黑色的盒子中插入 (4) 个红色盒子要求红色的盒子不相邻，其实选书去拿只是一个逆向的过程，所以答案其实是一样的，答案就是 (C_{18}^4 = 3060) 。