[趣题分享] 为什么下列连乘积皆为整数？

elimqiu · 发表于 2013-11-28 08:27

设整数 n ≥ m ≥ 1, a = (n -i +1) / i， i = 1,2, ..., m
试证(或否证）以下命题：
a[1], a[1]× a[2], a[1]×a[2]×a[3], ....., a[1]×a[2]× ·····×a[m] 皆为整数

drc2000 · 发表于 2013-11-28 09:18

ysr · 发表于 2013-11-28 09:27

绝妙证明！

ataorj · 发表于 2013-11-28 09:31

列出各项式子则一目了然:
(n)/1
(n-1)/2
(n-2)/3
...
(n-m+1)/m
=========
分母:1_m共m项
分子

(n-m)+1)_((n-m)+m)共m项.[各分子大分母n-m]
而连续m个自然数中,必同时存在:1的倍数,2的倍数,3的倍数,...,m的倍数.
并且(n-m)越大则分子包含的质因子数量越多[你另外一个主题,我谈过这个],
即分子积是分母积的倍数

ataorj · 发表于 2013-11-28 10:10

2楼视角值得借鉴,但是推论是错误的.
你的分子错了,简单查找了下公式,可能不是简单的排列组合问题.

Ysu2008 · 发表于 2013-11-28 11:08

[这个贴子最后由Ysu2008在 2013/11/28 11:09am 第 1 次编辑]

是组合数，2楼是对的。

ataorj · 发表于 2013-11-28 12:27

他的分子错了,请你给出组合的正确公式来吧.

ataorj · 发表于 2013-11-28 12:33

不知道你有图片,原来纠正过了.谢谢!

elimqiu · 发表于 2013-11-28 15:41

[这个贴子最后由elimqiu在 2013/11/28 05:59pm 第 1 次编辑]

谢谢 drc2000, Ysu2008 , ataorj
a[1]×a[2]× ·····×a[k] = C(n,k),  k = 1, 2, ...., m
所以虽然 a 未必是整数，这些乘积却都是组合数。
知道这点其实是非常有用的。看以下代码 (python)：
def comb(n,m):
   if m > n or m < 0:
       return 0
   result = 1
   k = m + 1
   if 2*m > n:
       k = n -m +1
   for i in range(1,k):
       result = result * (n-i+1) / i
   return result
这段代码定义了一个函数 comb(n,m), 就是计算组合数 C(n,m)
大意是说,
n 个不同元素取大于 n 个不同元素成组的取法数以及取负数个元成组的取法皆为 0；
如果 2m > n, 算 C(n,m)  不如算 C(n, n -m);
C(n,0) = C(n,n) = 1;
剩下的情况得当真算，算法就是
C(n,m) = a[1]×a[2]× ·····×a[m]
python 这种语言有个特点，二整数a, b 的python商还是整数:  [a/b],  例如 3/2 得 1， 24/3 得 8， 10/3 得 3.
要得到准确的商，得说 3/2.0 （得 1.5）， 10.0/3 （得 3.33333...x) 等等。
由我们的论证知道，以上算法不会因为python语言的特点而出错。
当然，组合数的算法有很多，例如可以递归等等，但是在种种方案中，上述算法应该是最节省 CPU 和储存的，也是在最大限度上避免“大数中间结果”的。

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

[趣题分享] 为什么下列连乘积皆为整数？