组合数学习题解答(7)

当n是偶数时，最后一次会出现F0=0项

当n是奇数时，最后一次会出现F1=1项

4）证明 用2）的结论

下面证明是最大公约数

设F(n,m)不是最大公约数， FN是,

则 m|N, n|N 则 N=<(n,m)与 N>(n,m)矛盾 是最大公约数

29. 从1到n的自然数中选取k个不同且不相邻的数，设此选取的方案为f(n,k)。

（a）求f(n,k)的递推关系。 （b）用归纳法求f(n,k)。

（c）若设1与n算是相邻的数，并设在此假定下从1到n的自然数中选取k个不同且不相邻的k个数的方案数为g(n,k)，利用f(n,k)求g(n,k)。 解：...

（a）

（b）

（c）

30. 设S2(n,k)是第二类Stirling数。 证明

证明：...

设与第n+1号球同盒的球有n-k个，这样，其他k个球就放入另外m-1个盒子， k=m-1,m,…,n。 即从n个不同的球中取k个放入m-1个相同的盒子的方案有

31. 求下图中从A点出发到n点的路径数。

解：...

把上方的点序列设为an

把下方的点序列设为bn 可得第推关系

特征方程为 解得

代入初值可解

32. n位0,1符号串，求从左向右只在最后两位才出现0，0的符号串的数目。 解：...

设所求的串的个数为an，相邻不同为0的串的个数为bn

特征方程为 解得

代入初值可解

33. 试证

证明：...

用数学归纳法

I n=2时

成立

II 设n=k时成立即

当n=k+1时

由I、II知题设成立

1.某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议

解: 设Ai为甲与第i个朋友相遇的会议 集，i＝1，?，6．则

故甲参加的会议数为:28+5=33.

2.求从1到500的整数中被3和5整除但不被7整除的数的个数. 解: 设A3：被3整除的数的集合 A5：被5整除的数的集合 A7：被7整除的数的集合

所以

3. n个代表参加会议，试证其中至少有2人各自的朋友数相等。

解:每个人的朋友数只能取0，1，?，n－1．但若有人的朋友数为0，即此人和其 他人都不认识，则其他人的最大取数不超过n－2．故这n个人的朋友数的实际取数只 有n－1种可

能．，所以至少有２人的朋友数相等．

4. 试给出下列等式的组合意义.

解:

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库组合数学习题解答(7)在线全文阅读。