这次的趣题来源于 UyHiP 今年八月份的谜题：概率均等地随机选取一个恰好含有 n 个 0 和 n 个 1 的 2n 位 01 串，这个 01 串平均会有多少个 0 和 1 个数相等的前缀（包括空串和整个串本身）？
为了叙述简便起见，下面我们把所含 0 和 1 个数恰好相等的 01 串叫做平衡的 01 串。例如， 010010110011 就是一个平衡 01 串，它有四个平衡前缀，空串、 01 、01001011 以及整个 01 串本身。我们需要求出的就是，任取一个长为 2n 的平衡 01 串，平衡前缀的个数的期望值是多少。
注意到，在所有长为 2n 的 01 串中，平衡 01 串一共有 C(2n, n) 个。下面我们证明，所有这些串的所有平衡前缀一共有 4n 个，从而得出问题的答案，即 4n / C(2n, n) 。
不妨把所有 2n 位平衡 01 串的所有平衡前缀的总数记作 F(n) ，容易得出：
利用生成函数，我们可以瞬间证明，这个和等于 4n 。由 Taylor 展开可知， 数列 C(2n, n) 所对应的生成函数为：
对上式平方，有：
但
因此 F(n) = 4n 。
Joseph DeVincentis 和 Daniel Bitin 给出了一个初等的证明。令 S 为某个平衡 01 串，令 k 为 S 的某个平衡前缀的长度（ k 有可能取 0 或者 2n ）。我们下面建立一个从所有可能的 (S, k) 到所有长为 2n 的 01 串的一一对应的关系，从而说明所有平衡前缀一共有 4n 个。
我们先给出把 (S, k) 变换为一个普通 01 串的方法。首先，取 S’ = S 。接下来，找出 S’ 中比 k 更长的平衡前缀中最短的那一个，把它的长度记作 l 。然后，对 S’ 中从第 k + 2 位到第 l 位的数字全部取反。继续寻找新的 l 并执行相应的取反操作，直到 S’ 中不再有比 k 更长的平衡前缀。
下面我们来说明，这个过程不会无限继续下去，总会有终止的时候。不妨假设 S 的第 k + 1 位是一个 0 。由于取反操作不影响前面 k + 1 位数字，因此 S’ 的前 k 位始终平衡，第 k + 1 位也始终是 0 。容易看出，每次取反前，第 k + 2 位到第 l 位中 1 的个数比 0 的个数多一个，因此对这一段数字取反将会让整个串少一个 1 多一个 0，从而让整个串的后半部分越来越不平衡。因此，总有一个时候，第 k 位以后将会不再有别的平衡点产生。如果 S 的第 k + 1 位是 1 ，类似的推理同样成立。
然后，我们需要说明，这个对应关系确实是一一对应的。为此，我们需要给出把 S’ 变回 (S, k) 的方法。首先，我们可以很快还原出 k 的值来：找出 S’ 中最长的平衡前缀，它的长度就是 k 。注意， k 一定是偶数，并且有可能是 0 或者 2n 。如果 k 是 2n ，即 S’ 本身就是一个平衡串，那么我们可以直接还原出 S = S’ 。下面只考虑 k < 2n 的情况。 不妨假设 S' 的第 k + 1 位是 0 ，由于在此之后 S' 没有其他平衡点了，因此从第 k + 2 位开始数下去， 0 的个数必须始终大于等于 1 的个数。由于从第 k + 2 位一直数到最后一位一共有奇数个数字，因此其中 0 的总个数也就一定严格大于 1 的总个数。找出从第 k + 2 位起， 0 的个数首次超过 1 的个数的地方，比如说第 l 位。对第 k + 2 位到第 l 位的数取反（此时 S' 的前 l 位将变成一个平衡前缀）。这样一来，整个串的后面部分将会少一个 0 多一个 1 ，但 0 的个数有可能仍然比 1 多。继续找出从第 k + 2 位起首次 0 的个数刚好比 1 多一个的地方，像刚才那样继续取反，让 0 越来越少， 1 越来越多，直到整个串变为平衡串为止。整个过程显然是从 (S, k) 变换到 S' 的逆操作，因而最后得到的串正是 S 。当然，如果 S' 的第 k + 1 位是 1 ，上面的推理同样成立。至此，我们便完成了全部证明。
沙发？
还真是啊······~
没有沙发了
Matrix67你好，你文章中提出的问题所使用的两种解决非常有代表性，前面用生成函数来解决，后面用构造对应关系的方法来解决，它们本质上应该是本同的。我记得，清华版的<>一书，计算N个节点所组成的二叉树的构型个数问题时，好像是用了三种方法，其中一种是用生成函数方法，一种是用线索二叉树来构造对应关系的方法，第三种我记不清了，很漂亮的是，最终的结果是C(2n,n)/(n+1)，也就是catalan数列的通项，这个结果我当时挺好奇的。
我比较好奇的是，这种构造对应关系的方法，它是否首先需要知道公式，再反过来确定这个构造，因为，这种公式的结构是千差万别的，从而构造那种对应关系的方法，也是各不一样的，那么如何“形式化的按照确定的步骤”来得出那种构造对应关系的方法呢？我觉得可能能够形式化，但是也不确定一定能，因为按照生成函数的方法，首先要确定生成函数，确定这个生成函数时，不一定都有“形式化”的方法，因为很多组合问题就始终构造不出生成函数来，对于那些确定出生成函数来的问题，在确定生成函数之后，所采用的方法就是形式化的了，所以，我的意思是这两种方法既然都能解决问题，那么它们在“本质”(因为都得到了同一个结果)上应该是相同的，也就是这两种方法之间存在一种一一对应关系，因为按照希尔伯特提出的形式化的观点来看，“方法本身”(或叫构造过程本身、或叫证明过程本身)就可以看做是符号串变换的序列，抛掉语义的东西，把这两个方法本身形式化(或符号号)，既然这二种方法都得到了最终同一个结果，那么这两个过程如果用抽象符号变换的序列来表示推理的过程，那么由两个方法所得到的两个抽象符号的变换的序列应该是一一对应的，在结构上应该是相同的，我在直觉上觉得应该是那个样子。
同时，我又想到了，平面几何的一些问题，用代数方法解决和用做辅助线、割补等方法来解决，与我上面的那个类比应该是相似的。但一个不同点是，好像所有平面几何问题(限于长度、角度之间的关系的平面几何问题，不涉及到存在性问题)，都能够用代数的方法来形式化的解决，也就是用坐标和距离公式能够解决所有的平面问题，但是做辅助线、割补等变换的方法却都没有一个统一的步骤，我要说的是这其中的最本质原因是什么？我觉得还有东西在里面没有被发现，值得思考。
另外，又想起一个问题，就是能不能把数学分析(微积分、复分析、实分析、调和分析)中得出的所有结果，用组合(也就是构造的方法)的方法来全部构造出来，而抛掉所谓的连续、极限、一致连续性、一致收敛等观点概念(因为我觉得那些好像都是语义上的，最终也是用cantor提出的自然数不可与实数建立一一对应这个结果来解释的，所以那些概念搞了半天，也没有把事情比较本质的东西揭示出来)，那么这个构造的过程是不是也可以形式化？齐民友翻译了国外的一本书，名字叫<>，是roger penrose(罗杰.彭罗斯)的学生，他对初等复分析做了一些全新的构造和解释，就是用几何化的方法来达到可视化的效果，能有不少启示，从中也可以看出很多值得思考的问题，比方说计算1/(x^n-1)的积分等等。
从现在观点来看，整个的代数学、数论本质上都是组合问题，可以与组合问题建立对应关系，就剩下微积分了。在这里不得不赞叹hilbert的心智，通过众多的历史上的具体数学问题，才能体会出Hilbert，他为什么要搞出个数学形式化出来，尽管被之后的Godel给否定了。
仅仅随兴写几段话，写出当下想起的事情，谢谢Matirx67的文章给我带来的启示，虽然不知对错。
Matrix67:把儿，越来越有意思了。哈哈~~~
翻了一下，原来生成函数就是母函数啊~利用生成函数证明好酷啊！
Taylor展开是在0处展开的，也叫做麦克劳林(Maclaurin)展开。
因为泰勒多项式的唯一性，所以F(n)=4^n。
复习了下大一所学的知识！^^
问一个和本文无关的问题：如何只生成1个随机数，可以将100个物品完全随机分成3份？要求每一份的期望值都是33.3。
第一个式子好多2n的2丢了
我觉得这个就像，matrix67的某些把二维几何题的辅助线作到三维中去的文章
最后说一句：其实不用三维也可以搞定的，虽然稍微麻烦点
就F(n)=C(0,0)C(2n,n)+C(2,1)C(2n-2,n-1)+C(4,2)C(2n-4,n-2)+…..+C(2n,n)C(0,0)中拿C(2,1)C(2n-2,n-1)和C(4,2)C(2n-4,n-2)而言，C(4,2)C(2n-4,n-2)遍历完长度为2n的平衡01串中(前)长度为2n-4的平衡01串的所有解。(对于后4个01串而言，有1100，0110，0011，1001，0101，1010六种，其中0110，1001，0101，1010已经保证了下面C(2,1)C(2n-2,n-1)的实现)
同理C(2,1)C(2n-2,n-1）已经遍历完长度为2n的平衡01串中(前)长度为2n-2的平衡01串的所有解。
所以一定有多余的解被添加进去了，如果我理解的没错的话。
我的想法跟10楼一样，比如当n等于3时,010101这个串同时在
C(2,1)C(2n-2,n-1)和C(4,2)C(2n-4,n-2)里被算了一次。
我的想法跟10楼一样,比如当n=3时,010101这个串分别在
C(2,1)C(2n-2,n-1)和C(4,2)C(2n-4,n-2)中被算了一次
数学不好的我每次都来围观下～ 挺有意思的 嘿嘿～
To 11楼
本来就是统计所有平衡前缀的个数啊。010101这个串它本身就含两个平衡前缀。所以算2次。
To 7 楼 地壳
生成一个3进制的100位的随机数？
总算有人回答了。谢谢15楼，好主意。
就是100位的随机数生成有点难，不过问题算是解决了。
我就是用第一种答的。。太不优美了。。后面那种虽然想到了Catalan数的证明方法但是还是没有想出来
数学好难呀！
计算一下很快就知道答案的
越来越有意思了。哈哈~~~