将$n$个小球随机放进$n$个盒子里(1)

KeyTo9_Fans 发表于 2013-1-11 22:57:29

如题，放法如下：

————————————————
对于每个小球，无论其它小球放在哪里，

它被放进任意一个盒子的概率都是$1/n$。
————————————————

于是一个盒子可能有多个小球，也可能没有小球。

我们将装球数最多的盒子所装的小球个数记为$m$，

$m$的均值记为$m_a$，方差记为$m_s$。

问题$1$：

给定$n=1,2,3,...$，求$m_a$和$m_s$的值分别是多少。

问题$2$：

求证：$\lim_{n->\infty}m_a/ln(n)=0$。

问题$3$：

求$\lim_{n->\infty}m_a/ln(n)*ln(ln(n))$等于多少？

wayne 发表于 2013-1-12 00:39:52

问题1：
求方程 \sum_{i=1}^{m} i*a_i=n (am>0) 的非负整数解1 {1}
2 {1, 2}
3 {1, 6, 3}
4 {1, 18, 12, 4}
5 {1, 50, 50, 20, 5}
6 {1, 140, 195, 90, 30, 6}
7 {1, 392, 735, 392, 147, 42, 7}
8 {1, 1106, 2716, 1652, 672, 224, 56, 8}
9 {1, 3138, 9912, 6804, 2970, 1080, 324, 72, 9}
10 {1, 8952, 35850, 27600, 12825, 4950, 1650, 450, 90, 10}
算得ma:
1 1
2 5/3
3 11/5
4 89/35
5 178/63
6 706/231
7 2797/858
8 22129/6435
9 43742/12155
10 172870/46189
11 1366223/352716
12 2699500/676039
13 762106/185725
14 14059873/3343050
15 83396903/19389690
16 1319518817/300540195
17 2610502618/583401555
18 939297818/206253075
19 81814263569/17672631900
20 12461952164/2650894785
是这个结果吗

KeyTo9_Fans 发表于 2013-1-12 01:27:52

不是。

当$n=1$时，$m_a=1$。

当$n=2$时，$m_a=(1*2+2*2)/4=3/2$。

当$n=3$时，$m_a=(1*6+2*18+3*3)/27=17/9$

当$n=4$时，$m_a=(1*24+2*180+3*48+4*4)/256=17/8$

当$n=5$时，$m_a=(1*120+2*2100+3*800+4*100+5*5)/3125=1429/625$

……

将前$5$项拿去OEIS上查，发现OEIS还没有收录这个数列。

恭喜数学研发论坛即将再次向 OEIS 贡献新数列！

wayne 发表于 2013-1-12 01:29:45

在OEIS上找到数据了
http://oeis.org/A180281

wayne 发表于 2013-1-12 08:04:58

3# KeyTo9_Fans
很不幸，我一时迷糊搞混淆了，一个是有区别，一个是无区别。
不过fans也很不幸，OEIS仍然有这数列
http://oeis.org/A019575
有了这个数列就足可以算出期望值和方差

KeyTo9_Fans 发表于 2013-1-12 08:51:41

很好！问题$1$解决了。

接下来该解决问题$2$和问题$3$了。

wayne 发表于 2013-1-12 09:03:44

6# KeyTo9_Fans
这个是解析分析，
得要得到ma的显式表达了。

KeyTo9_Fans 发表于 2013-1-12 21:29:48

问题$2$已经证出来了:victory:

接下来我们看看问题$3$的答案是多少:)

KeyTo9_Fans 发表于 2013-1-13 22:23:57

问题$3$也做出来了，答案是$1$:victory:

接下来做做问题$4$吧:)

问题$4$：

给定$k=1,2,3,...$，求最小的$n$，使得$m_a>=k$。

===========================================================
http://images.5d6d.net/dz7/common/online_admin.gif发表于 2013-1-14 20:23|只看该作者 9.1 #
-----------------------------------------------------------------------------------------------------------
$10#$ wayne

$m_a={\ln n}/{\ln \ln n}(1+o(1))$，所以

$\lim_{n->\infty}m_a/{\ln n}=0$，

$\lim_{n->\infty}m_a/{\ln n}*\ln \ln n=1$。
------------------------------------------------------------------------------------------------------------

wayne 发表于 2013-1-14 14:58:10

9# KeyTo9_Fans
进展这么快，能否share一下，:victory:

页: [1] 2

数学研发论坛's Archiver

将$n$个小球随机放进$n$个盒子里(1)