Question

排列组合问题 附上讲解

能做几道就几道 谢谢！
NOIP2002TG-C-1
在书架上放有编号为1 ，2 ，．．．，n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：n = 3时：
原来位置为：1 2 3
放回去时只能为：3 1 2 或 2 3 1 这两种
问题：求当n = 5时满足以上条件的放法共有多少种？（不用列出每种放法）

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

NOIP2006TG-C-2
将边长为 n 的正三角形每边 n 等分，过每个分点分别做另外两边的平行线，得到若干个正三角形， 我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是 n=5 时一条通路的例 子）。设 n=10，则该正三角形的不同的通路的总数为_ __。

NOIP2007TG-C-1
给定n个有标号的球，标号依次为1，2，…，n。将这n个球放入r个相同的盒子里，不允许有空盒，其不同放置方法的总数记为S(n,r)。例如，S(4,2)=7，这7种不同的放置方法依次为{(1) , (234)} , {(2) , (134)} , {(3) , (124)} , {(4) , (123)} , {(12) , (34)} , {(13) , (24)} , {(14) , (23)}。当n=7，r=4时，S(7,4)= 。

NOIP2007TG-C-2
N个人在操场里围成一圈，将这N个人按顺时针方向从1到N编号，然后从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为J(N)，例如，J(5)=3，J(10)=5，等等。
则J(400)= 。
（提示：对N=2m+r进行分析，其中0≤r<2m）。

Answer 1

1. 采取组合中的爬楼梯法来解决。设方法数为Sn
当n=2时，S2=1.
当n=3时，S3=3！-3*S2-1=2
当n=4时，S4=4!-4*S3-6*S2-1=9 (4=4个中取一个，6=4个中取2个)
当n=5时，S5=5！-5*S4-10*S3-10*S2-1=44 (10=5个中取2个，10=5个中去3个)

2. 为每本书标上编号，记为1，2，3，……，21.题目变为取4个数1<=x1<x2<x3<x4<=21,使得其两两不相邻。
令y1=x1,
y2=x2-x1-1,
y3=x3-x2-1,
y4=x4-x3-1,
y5=21-x4,
则y1+y2+y3+y4+y5=18
所以结果为18C4=3060 （因为实际上y5是不取的）