erbin 发表于 2014-12-12 19:46:02

组合数学中的屡试不爽猜想









hjuy13 发表于 2014-12-17 19:01:48

非常有意思的猜想,验证了一下,简单情况好像都是对的。猜想很可能是对的,不过还未想出证明方法。

chuxuezhe2014 发表于 2014-12-17 23:00:28

谢谢分享哦哦哦!

youthfire2009 发表于 2014-12-18 09:43:56

下来学习了,希望有更加严格的证明

hjuy13 发表于 2014-12-19 23:49:15

不过非常遗憾,你的这个猜想是错的。
反例如下:
考虑3个红球和3个篮球的情形,且令m=0. 由你的猜想T(0) = 6! = 720,但是(f表示特数):r r r b b b ........... f = 180
r r b r b b ........... f = 12
r r b b r b ........... f = 8
r r b b b r ........... f = 40
r b r b b b ........... f = 30
r b b r b b ........... f = 18
r b b b r b ........... f = 12
r b b b b r ........... f = 60
r r r b b b ........... f = 180
r r b r b b ........... f = 12
r r b b r b ........... f = 8
r r b b b r ........... f = 40
b r r b b b ........... f = 90
b r b r b b ........... f = 6
b r b b r b ........... f = 4
b r b b b r ........... f = 20
b b r b b b ........... f = 60
b b b r b b ........... f = 36
b b b b r b ........... f = 24
b b b b b r ........... f = 120其和为960.

zhujiangjin 发表于 2014-12-21 13:37:55

Very good!

zhujiangjin 发表于 2014-12-21 13:38:07

Good.

bairuizheng 发表于 2014-12-22 01:53:14

Good.

snkparty 发表于 2014-12-22 20:30:45

2个红球,1个黄球的情况好像结果都不满足猜想公式啊!

zhangliang777 发表于 2014-12-22 22:40:39

能有人讲讲罗素悖论吗。

nkhqh 发表于 2014-12-23 11:27:16

归纳法可以证明, 不过应该有更直接的组合解释。

用1,2,...,r表示颜色,n1,n2,...,nr为对应的球的个数。
令pi表示颜色出现的先后顺序,则对于1,2,...,r的任意一个排列pi,
与之对应的重集排列可以一一对应于一个pi=1 2 3 ... r的重集排列,并且
两者的带权和相等。因此我们只需要证明对应于pi=1 2 3 ... r的重集排列的带权和为
(m+n1+n2+...+nr)!/(m+r)!

如果n1=1, 则重集排列必然形如12****, 于是利用归纳假设,带权和应为
((m+1)+n2+...+nr)!/((m+1)+(r-1))!, 命题成立。

如果n1>1, 有两种情况:一种是11****,由归纳假设,带权和为
(m+2) * ((m+1)+(n1-1)+n2+...+nr)!/((m+1)+r)!
一种是12****,此时考虑重集排列中第二个1之前最大的元素,设为a。则通过变换
2->1, 3->2, ... a->(a-1), 1->a得到一个新的重集排列,由归纳假设,带权和为
((m+1)+na+n_{a-1}+...+n2+(n1-1)+n_{a+1}+...+nr)!/((m+1)+r)!
a可以取2,3,...,r,有(r-1)种可能。加上第一种情况,总的带权和为
(m+2+r-1)*(m+n)!/(m+r+1)! = (m+n)!/(m+r)!, 命题成立。

hjuy13 发表于 2014-12-23 19:02:54

回复 nkhqh 的帖子

有一点不明白,为什么1...r的任意排列对应的重集排列的带权和相等?

absence 发表于 2014-12-24 08:22:46

https://www.sharelatex.com/templates/549a02f93a7834fb6516e88b

erbin 发表于 2014-12-24 09:08:17

这个组合数学中的小猜想(屡试不爽),是我研究素数和正整数的时候推导出来的,(或者说发现的)。

关于具体从素数和正整数的推导过程可以看下面这个文档:







我研究数论的全文是下面这个文档:







erbin 发表于 2014-12-24 09:24:36

回复 absence 的帖子

感谢您证明。我数学专业功底很差,所以一时半会还看不懂您的证明。

erbin 发表于 2014-12-24 09:36:59



















nkhqh 发表于 2014-12-24 16:35:35

回复 hjuy13 的帖子

hjuy13质疑的有道理,我们无法直接看出对于1^{n_1} 2^{n_2} ... r^{n_r}的所有重集排列,1,2,..,r出现顺序不同时权和相同。实际上是先证明对于出现顺序为1 2 ... r的重集排列满足权重为(m+n)!/(m+r)!,然后利用1,2, ..., r的置换证明权重之和不依赖于1...r的出现顺序。
例如1^2 2^1的排列可以分成两类:112 121 / 211
第一类对应于pi=1 2,权重和为(m+3)!/(m+2)!
第二类对应于pi=2 1,需要将12互换,一一对应于1^1 2^2的重集排列,然后再利用我们已证的结论得到权和也为(m+3)!/(m+2)!,从而第一类和第二类的权和相等。

huping1021 发表于 2014-12-24 22:54:53

好,应该顶,今后继续努力        http://www.dqjo.com/news/128.html

hylpy 发表于 2014-12-24 23:37:03

支持一下

erbin 发表于 2014-12-25 08:52:52

回复 absence 的帖子

虽然没有彻底看懂,但是您的证明应该是对的,十分感谢您的证明!
页: [1] 2
查看完整版本: 组合数学中的屡试不爽猜想