一个有些挑战性的组合题zzz

Osiris · 发表于 2005-7-2 11:16

整数 |p| ≤ n , 要求从这 2n+1 个数中取k个总和为q的数, 请问总共有多少中取法？

：）看似不难, 但其实有些难度, 而且结果可能有多种形式.....

Osiris · 发表于 2005-7-3 19:23

可能上面说的有点抽象, 看起来不是很明白,举个例子
譬如n=2, 则满足|p| ≤ n 的 p可以取
-2,-1,0,1,2
共5个数.
如果想从这5个数中取3个数(即当k=3时),并使这两个数的和为3(即当q=3时),
这时的取法有:
0,1,2
总共1种;
再如当n=3时,则满足|p| ≤ n 的 p可以取
-3,-2,-1,0,1,2,3
共7个数.
如果想从这7个数中取3个数(即当k=3时),并使这两个数的和为3(即当q=3时),
这时的取法有:
0,1,2/-1,1,3/-2,2,3/
总共3种;

现在问题是对于一般的整数n,p,q, 总共会有多少中取法呢？(即求其通式)

Osiris · 发表于 2005-7-8 14:05

：）是不是觉得难度很大？

Osiris · 发表于 2005-7-11 00:41

有两位朋友提出了如下的想法, 大家可以考虑下:
第1种. 按照要求，如果这k个数看作是有序的，第j个数记为xj，其中1≤j≤k，-n≤xj≤n，则x1+x2+…+xk=q。再令xj=yj-n，则0≤yj≤2n，y1+y2+…+yk=q-kn，这个不定方程满足0≤yj≤2n的整数解的组数是多项式(1+a+a2+…+a2n)k展开式中的aq-kn项的系数，记为t，即有t种取法。如果这些数看作无顺序的，则有t/k!种取法。
第2种. ∏ (1+yx^i)展开式中(y^k)(x^q)项的系数,连乘积对i=-n,...,-1,0.1,...,n进行.
当然其实这两种想法比较相似了, 各位也可以考虑下有没别的思路.....

Osiris · 发表于 2005-7-14 13:17

不过上面也只是提出了一种问题转化的思路,并没得到最终结果的表达式,..
谁来挑战一下.....

Osiris · 发表于 2005-8-31 15:15

-_- this is a real challenge, right?

wangyangke · 发表于 2010-1-23 17:02

[灌水] [灌水]jzkyllcjl 老先生风光风光

白新岭 · 发表于 2010-1-23 17:23

因为楼主要的无序不重复的组数，所以问题很复杂，在加上限定了取值范围，这就更难了，这与一个数的拆分有关系，如果不限定范围，一个数的和的组数，就是一个拆分数目，的确与x+2y+3z+...+mu=P的定义域的解组数相同。

		自动登录	找回密码
密码			注册