作业帮12、13届noip中的题目……急求解【要过程】1．给定n 个有标号的球,标号依次为1,2,…,n.将这n 个球放入r 个相同的盒子里,不允许有空盒,其不同放置方法的总数记为S(n,r).例如,S(4,2)=7,这7 种不同
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/10 23:37:07
12、13届noip中的题目……急求解【要过程】1．给定n 个有标号的球,标号依次为1,2,…,n.将这n 个球放入r 个相同的盒子里,不允许有空盒,其不同放置方法的总数记为S(n,r).例如,S(4,2)=7,这7 种不同
12、13届noip中的题目……急求解【要过程】
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)= _____________.
2．N 个人在操场里围成一圈,将这N 个人按顺时针方向从1 到N 编号,然后,从第一个人起,每
隔一个人让下一个人离开操场,显然,第一轮过后,具有偶数编号的人都离开了操场.依次做下去,直
到操场只剩下一个人,记这个人的编号为J(N) ,例如,J(5)=3 ,J(10)=5 ,等等.则
J(400)=______________.
（提示：对 N=2m+r 进行分析,其中 0≤r
12、13届noip中的题目……急求解【要过程】1．给定n 个有标号的球,标号依次为1,2,…,n.将这n 个球放入r 个相同的盒子里,不允许有空盒,其不同放置方法的总数记为S(n,r).例如,S(4,2)=7,这7 种不同
1.解法一：递推公式S(x,y)=S(x-1,y)*y+S(x-1,y-1).因为把X个球放入Y个箱子,相当于先把X-1个球放好再放最后一个.最后一个有两种放法：放入前面已经有球的箱子或者独占一个箱子.前者对应S(x-1,y)*y (放入每一个不同的箱子都是一种不同的放法,因为箱子内原来的球不同),后者对应S(x-1,y-1).
解法二：将这n 个球放入r 个相同的盒子里,不允许有空盒,因为是"相同的盒子",所以是一个组合问题.既将n个球分成r份.这样当n=7,r=4时,将7个球分成4份,有三种分法:(1)分为4,1,1,1(2)分为3,2,1,1(3)分为2,2,2,1
第一种分法有C(7,4)=35种
第二种分法有C(7*3)*C(4,2)=210种
第三种分法有C(7,2)*C(5,2)*C(3,2)/A（3,3）=105种
S（7,4）= C(7,4)+C(7,3)*C(4,2)+C(7,2)*C(5,2)*C(3,2)/A（3,3）=350
C(n,m)表示从n个不同元素中取出m个元素的组合数
A(n,m)表示从n个不同元素中取出m个元素的排列数
2.若N是满足2^m