12 / 2 页下一页

查看: 7141|回复: 11

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

[复制链接]

字体大小: 正常放大

Osiris

2 主题	2 听众	29 积分

升级 25.26%

该用户从未签到

电梯直达

1^#

发表于 2005-7-2 12:14 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

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

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

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

Osiris

2 主题	2 听众	29 积分

升级 25.26%

该用户从未签到

2^#

发表于 2005-7-3 19:07 |只看该作者 |招呼Ta 关注Ta

可能上面说的有点抽象, 看起来不是很明白,举个例子
譬如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

2 主题	2 听众	29 积分

升级 25.26%

该用户从未签到

3^#

发表于 2005-7-8 13:45 |只看该作者 |招呼Ta 关注Ta

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

我也说一句

发表

使用道具举报

Osiris

2 主题	2 听众	29 积分

升级 25.26%

该用户从未签到

4^#

发表于 2005-7-11 00:22 |只看该作者 |招呼Ta 关注Ta

有两位朋友提出了如下的想法, 大家可以考虑下:
第1种. 按照要求，如果这k个数看作是有序的，第j个数记为x_j，其中1≤j≤k，-n≤x_j≤n，则x₁+x₂+…+x_k=q。再令x_j=y_j-n，则0≤y_j≤2n，y₁+y₂+…+y_k=q-kn，这个不定方程满足0≤y_j≤2n的整数解的组数是多项式(1+a+a²+…+a²ⁿ)^k展开式中的a^q-kn项的系数，记为t，即有t种取法。如果这些数看作无顺序的，则有t/k!种取法。

第2种. ∏ (1+yx^i)展开式中(y^k)(x^q)项的系数,连乘积对i=-n,...,-1,0.1,...,n进行.