Question

一道Pascal的公式推导过程，急求高赏

给两个数：S和N

求由1~N*S组成的N位组合个数
要求：这些组合中的每一种的N*S个数，至少有一个≤S，至少有一个≤2*S，至少有一个≤3*S……至少有一个≤N*S
求总组合数的公式（重点是组合，不是排列）
可以是数字公式，也可以是程序段
要过程，急求，谢谢各位大神！！！
例子：S=2 N=3
排列：1 2 3 1 2 4 1 2 5 1 2 6
1 3 4 1 3 5 1 3 6
1 4 5 1 4 6
2 3 4 2 3 5 2 3 6
2 4 5 2 4 6
答案就是14
比如1 5 6和3 4 5就不行
1 5 6中没有≤2*S=2*2=4的
3 4 5中没有≤S=2的

Answer 1

你的意思：要求：这些组合中的每一种的N*S个数，至少有一个≤S，至少有一个≤2*S，至少有一个≤3*S……至少有一个≤N*S，

1 5 6中没有≤2*S=2*2=4的，1不是≤2*S=2*2=4的吗？
你的意思是至少有一个≤S，至少有一个S<X1≤2*S，至少有一个2S<X2≤3*S……至少有一个
(N-1)S<XN≤N*S，是这样吗？

如是这样的话，最前S个数中必须要选一个；第2组S个数中必须要选一个；…………最后S个数中必须要选一个，共有N组。
根据乘法原理，共有S^N种。
所给例子即为2^3=8种。

追问

不是啊，只要求有一个≤2*S
比如说上面一个例子中1 2 3就可以
符合：1≤S=2 2≤2*S=4 3≤3*S=6
但是不符合：1≤S S<2≤2S 2S<3≤3S
还是谢谢你的及时解答，希望你能继续为我解答

追答

1 5 6中没有≤2*S=2*2=4的，1不是≤2*S=2*2=4的吗？这个怎么说？已经用过的就不算吗？靠题目文字好象不能理解？

追问

这么说吧，每种排列都由小到大，比如只能1 2 3，而不能1 3 2
在有小到大的排列下
组合中的第i个数字≤i*S
1 2 3中
1≤1*S=2
2≤2*S=4
3≤3*S=6

追答

要求：这些组合中的每一种的N*S个数，第一个≤S，第个≤2*S，第三个≤3*S……

最后一个≤N*S,且数字不能重复。

求总组合数的公式（重点是组合，不是排列）

是这样理解吧？

给一个PASCAL程序吧：

var s,n,x:longint;

function pp(k,k1:longint):longint; //选第k..n个数的种数，可从k1+1以上选

var i,x:longint;

begin

  if k=n then begin pp:=s*n-k1; exit end;  //最后一个数可选范围为k1+1..s*n

  x:=0;

  for i:=k1+1 to k*s do x:=x+pp(k+1,i); //选下一个数

  pp:=x;

end;

begin

  readln(s,n); // 每组s个，共n组

  writeln(pp(1,0));

end.

追问

太谢谢了，我已经追加到最高了，希望以后我又不会的题你还能为我解答
（我是做noip的）

Answer 2

数字是不是能否重复使用？好像没有1 1 1
为什么没有5 4 2的排列
你的意思不大怎么看懂，是不是指：
左边的第一个要<=S，第2个要<=2*s……第n个<=n*s，而且数不能重复使用

还有如果n=2 s=10
10 20
是不是其中的一种

追问

是14种
说了是组合不是排列，为了方便由小到大打，1 2 3和1 3 2和3 2 1和3 1 2和2 1 3和2 3 1算一种
另外不能重复，没有111