转自mathoverflow的一道有趣的题

有n个球，初始被染上n种不同的颜色。每一次从中随机取出2个球，将第2个球染成与第1个球相同的颜色。求将所有球都染成一种颜色的期望次数。

答案在一楼网址中有（不过是英文的），如果有吧友需要的话，我再贴出其中文翻译。

好难

令N={1,...,n}。
令F是满足这样性质的从N到N的函数的集合：除了某个j，函数将一个数映射到其自身
(即F={f:N->N|存在某个j，当i≠j时，f(i)=i，而且f(j)≠j}）。
定义

其中是从F中均匀随机选取的。
令=min{t|是常数}，那么原题等价于求
(事实上，相当于原题中在第i步将j号球染成与号球相同的颜色）

继续定义

=min{t|是常数}。
易知当t给定时
P(不是常数)=P(不是常数)

于是
P(>t)P(不是常数)=P(不是常数)=P(>t)
这意味着
和有相同的分布，即相同的期望。
接下来即求的期望。

注意到如果的值域有k个互不相同的值，那么接下来再加个后，有k(k-1)/n(n-1)的概率k会减1，否则会保持原样。所以是参数为k(k-1)/n(n-1)的几何分布的叠加，其期望为

为什么n=3时，是2次，不是应该至少2次吗？