　　这一系列的第一篇文章说到，用插入排序 + 随机比较实现洗牌，在元素较多时，每个元素留在原位的概率趋于一个常数 $C \approx 0.220643036096533$ ，我称之为「乱排常数」；第二篇文章为这个常数找到了一个略复杂的数学表达式：

$C = \prod_{i=1}^\infty (1 - 2^{-i}) \cdot \sum_{k=0}^\infty \frac{2^{-(k+1)^2} }{\prod_{i=1}^k (1-2^{-i})^2} \\$

利用 q-Pochhammer 符号，可以略微化简这个式子：

$C = (1/2; 1/2)_\infty \cdot \sum_{k=0}^\infty \frac{2^{-(k+1)^2}}{(1/2; 1/2)_k^2} \\$

但依然显得复杂。

　　这个「乱排常数」，虽然在网上很难搜到，但也不是完全没有一点儿蛛丝马迹。比如这篇斯洛文尼亚语的习题解答，在第 2 页的第 3 题里就奇妙地出现了乱排常数：

看不懂斯洛文尼亚语没关系，只要能看懂里面的数学式子就行了。题目里提出了一个递推关系 $I_n = 2^{-n} \cdot (1 - I_{n+1})$ ，然后从 $I_{11} = 0$ 开始逆推，结果就发现 I_2 恰等于乱排常数。

　　等等！如果乱排常数真能这样推出来，岂不是说明它是一个有理数？！而且为什么要从 $I_{11}$ 开始推？这个初始下标也太神奇了……

　　原来，不管从哪一项为零开始推，只要初始项的下标足够大，推到 I_2 都能得到乱排常数。把 I_2 的递推式反复展开，就能看明白怎么回事了：

$\begin{align} I_2 &= 2^{-2} \cdot (1 - I_3) \\ &= 2^{-2} - 2^{-2} \cdot 2^{-3} \cdot (1 - I_4) \\ &= 2^{-2} - 2^{-5} + 2^{-5} \cdot 2^{-4} \cdot (1 - I_5) \\ &= 2^{-2} - 2^{-5} + 2^{-9} - 2^{-9} \cdot 2^{-5} \cdot (1 - I_6) \\ &= \ldots \\ &= 2^{-2} - 2^{-5} + 2^{-9} - 2^{-14} + 2^{-20} - 2^{-27} + \ldots \end{align} \\$

原来， I_2 是一个级数和，初始取哪一项为零，只是控制了级数截断的位置。如果不截断，那就可以得到一个无穷级数：

$\sum_{k=1}^\infty (-1)^{k-1} \cdot 2^{-k(k+3)/2} \\$

我用 Python 进行了高精度计算，发现这个级数和的前 100 位有效数字都与乱排常数相同，所以这应该就是乱排常数的另一种表达式了，它比上一篇文章找到的表达式更简洁。

　　根据 $C = 2^{-2} - 2^{-5} + 2^{-9} - 2^{-14} + 2^{-20} - 2^{-27} + \ldots$ 这个表达式，可以把乱排常数写成二进制的形式：

$C = 0.00\,111\,0000\,11111\,000000\,1111111\,\ldots \\$

这个形式应该是最容易记忆的。其规律是：小数点后 2 个 0，3 个 1，4 个 0，5 个 1，6 个 0，7 个 1 …… 这个形式也能说明，乱排常数确实是个无理数。

　　不幸的是，我没能证明出乱排常数的两种表达式是相等的。q-Pochhammer 符号的维基页面上给出了许多恒等式，但没有一个与上一篇文章的结论相符。最接近的一个公式中含有 $\sum_{k=0}^\infty \frac{q^{k^2}}{(q;q)_k^2}$ ，若取 q = 1/2 ，则乱排常数的表达式中会含有 $\sum_{k=0}^\infty \frac{q^{(k+1)^2}}{(q;q)_k^2}$ ，很不幸分子的指数并不一样。

　　所以我在此提出一个开放性问题：如何证明乱排常数的两种表达式确实相等？即证明

$(1/2; 1/2)_\infty \cdot \sum_{k=0}^\infty \frac{2^{-(k+1)^2}}{(1/2; 1/2)_k^2} = \sum_{k=1}^\infty (-1)^{k-1} \cdot 2^{-k(k+3)/2} \\$

另外还有一个值得思考的问题是：能否在插队模型中，直接解释级数 $\sum_{k=1}^\infty (-1)^{k-1} \cdot 2^{-k(k+3)/2}$ 的各项？

　　除此之外，还有一些好玩的问题值得研究：

在元素有无限多时，每个元素的最终位置相对于初始位置的位移的分布列是怎样的？这一系列文章只计算了位移为 0 的概率，那么位移为其它值时，概率的一般表达式是什么？
我在 OEIS 上发现， $\sqrt[5]{54} \approx 2.220643034922920$ ，其小数部分与乱排常数 $C \approx 0.220643036096533$ 的前 8 位都是一模一样的。这是巧合吗？它与「 $\text{e}^{\pi\sqrt{163}}$ 几乎是一个整数」有没有联系？

　　可惜我的数学能力就只能走这么远了，希望「有志与力」的朋友继续研究，揭示这个问题深处的奇伟、瑰怪、非常之观。

　　以上发表于 12 月 1 日大约晚上 11 点（美东时间）。

晚上 12 点更新： @Octolet 找到了插队成功概率取一般值时，各个元素留在原位的概率 C(q) 的表达式（我只研究了 q=1/2 的情形）。

　　比较复杂的表达式是：

$C(q) = (1-q) \cdot (q;q)_\infty \cdot \sum_{k=0}^\infty \frac{q^{k(k+2)}}{(q;q)_k^2} \\$

注意原来分子上的那些 1/2 里面，有一个是 1-q 而不是 —— 它是「前进」过程中最后一步被挡住的概率。在 q=1/2 时看不出这个区别。

　　比较简单的表达式是：

$\begin{align} C(q) &= 1 + 2 \cdot \sum_{k=1}^\infty (-1)^k \cdot q^{k(k+1)/2} \\ &= 1 - 2q + 2q^3 - 2q^6 + 2q^{10} - 2q^{15} + 2q^{21} - 2q^{28} + \ldots \end{align} \\$

q=1/2 同样掩盖了一些规律： 1-2q 这部分抵消了；后面的项的系数 2 可以乘到的幂上，让指数减小 1。

　　第二个表达式说明：

在三进制下的表示为 0.1 01 221 0001 22221 000001 2222221 ……
在四进制下的表示为 0.2 01 332 0001 33332 000001 3333332 ……
在五进制下的表示为 0.3 01 443 0001 44443 000001 4444443 ……

以此类推。

　　证明两个表达式相等，仍然是一个未解决的问题。

凌晨 1 点更新： @刘奔说 ta 证明了 C(q) 的复杂表达式和简单表达式相等。没想到砖才抛出去两个小时，就把玉引来了！

.　　@刘奔的证明见这篇文章：乱排常数的一个恒等式。文章开头的 (2) 式，两边同乘以 1-q ，右边就是乱排常数的复杂表达式，左边稍加整理可以得到乱排常数的简单表达式。

　　证明过程利用了 Jacobi 三重积恒等式。这个恒等式的日文维基页面上有一个证明，但步骤较繁杂；意大利语维基页面上有一个步骤比较简洁的证明，但我怀疑跳步很严重。所有这些证明（包括 @刘奔的证明），都有一个特点，就是依赖于「神来之笔」，不知道怎么想出来的……

12 月 2 日晚上 10 点更新：我算出了插队成功概率取一般值时，每个元素的最终位置与初始位置相比前进了步的概率 C(q,d) ，即位移的分布列。

　　用与上一篇文章相同的方法，可以算出 C(q,d) 的复杂表达式：

$C(q,d) = (1-q) \cdot (q;q)_\infty \cdot \sum_{k=0}^\infty \frac{q^{(k+1)(k+d+1)-1}}{(q;q)_k \cdot (q;q)_{k+d}} \\$

这个式子只适用于 $d \ge 0$ 的情况。不过位移的分布列是对称的，后退若干步的概率与前进相同步数的概率相等。

　　本文的第一个更新表明， C(q,0) 在 1/q 进制下的表示会比较有规律。受此启发，我计算了 q = 0.1 时的若干个 C(q,d) 的值，因为在十进制下就能看出规律。

$\begin{align} C(0.1, 0) &= 0.\,8\,01\,998\,0001\,99998\,000001\,9999998 \ldots \\ C(0.1, 1) &= 0.0\,89\,010\,9989\,00010\,999989\,0000010\,99999989 \ldots \\ C(0.1, 2) &= 0.00\,899\,0100\,99899\,000100\,9999899\,00000100\,999999899 \ldots \\ C(0.1, 3) &= 0.000\,8999\,01000\,998999\,0001000\,99998999\,000001000\,9999998999 \ldots \\ C(0.1, 4) &= 0.0000\,89999\,010000\,9989999\,00010000\,999989999\,0000010000\,99999989999 \ldots \end{align} \\$