阶乘到底有多大？
文章摘要
Eli Bendersky 的这篇文章起源于一个很随意的好奇：52!（52 的阶乘，也就是一副扑克牌所有可能排列数）到底有多大？更进一步——在没有计算器也没有电脑的情况下，怎么估出它的量级？结果发现这背后有一套相当有趣的数学。
文章先直接给出结论式的估算公式：n! 的十进制位数大约等于 n 乘以 log10(n/e) 再加 2。用它来算 52!：52 除以 e 大约是 20，log10(20) 约为 1.3，于是 52 乘 1.3 再加 2，得到约 69 位。真实答案是 68 位，误差只有一位。作者顺带提了个心算技巧：记住 log10(2) 约等于 0.3、log10(3) 约等于 0.5，再配合对数运算律，大部分常见数的常用对数都能估个八九不离十。在处理这种量级的数字时，差个一两位通常无伤大雅。
随后文章回过头补数学背景，分三步走。第一步是伽马函数。对正实数 n，伽马函数定义为一个从 0 到无穷的积分。这个积分一般没有解析表达式，但有一条极其有用的递推性质：对被积函数做分部积分，可以证明 Gamma(n+1) 等于 n 乘 Gamma(n)。再单独算出 Gamma(1) 等于 1（这个特例有解析解），归纳下去就得到 Gamma(2) = 1!、Gamma(3) = 2!、Gamma(4) = 3!，一路推出 Gamma(n+1) = n!。换句话说，伽马函数就是阶乘在全体正实数上的插值延拓。作者附了一张小范围内的伽马函数图，因为增长太快，纵轴用的是对数刻度。
第二步是从伽马函数推出斯特林近似，即 n! 约等于根号下 2πn 再乘以 (n/e) 的 n 次方。推导思路是：把 n! 写成伽马积分，先把被积函数中的幂次改写成指数形式，再做变量替换 x = ny，整理出一个形如”e 的 n 倍某函数”的积分。这个形式正好适用拉普拉斯方法——对于被积函数是 e 的 n·f(x) 次方、f 二阶可导、n 很大的定积分，可以用 f 的全局最大值点处的信息来近似整个积分。在这里 f(x) = ln x - x，容易验证它在 x 等于 1 处取全局最大值，且该点的函数值和二阶导数都等于 -1。把这些代入拉普拉斯近似公式，化简后就得到了斯特林公式。作者坦承他很想展开讲讲拉普拉斯方法本身为什么成立，但”这篇文章的兔子洞已经够深了”。
第三步是从斯特林公式反推位数。对公式两边取常用对数并拆开，得到位数约等于 log10(根号 2πn) 加上 n 乘 log10(n/e)。关键观察在于：第一项没有乘以 n，所以随着 n 增大它的相对影响越来越小，但它并不会消失，仍然贡献了大约 2 位——这正是开头公式里那个”加 2”的由来，把它算进去能让估算明显更准。作者在脚注里给出了这个常数项的适用范围：n 小于 1600 左右时它最多加 2 位，超过之后可能多于 2 位，但直到 n 达到 160000 都不会超过 3 位。他随即自嘲：实在想不出谁会需要估算 1600! 的位数（顺便，答案是约 4450 位），更别说 160000! 了。
HN 评论精华
这条讨论拿到 94 分。评论区的重心并不在推导本身，而是分裂成两股：一股在比拼各种”更好记的估算法”和数学补充，另一股则在集体沉迷于”如何让人直观感受 52! 有多大”。
估算方法的补充方面，Sharlin 给出了一个更快更脏的版本：n! 的位数可以用 n·lg n 粗估，它从上方逼近，依据是把连乘式里每一项都放大到 n 的不等式——”上过算法课的人应该都眼熟”。想要更紧的界，可以用 n·lg n - n/2，来源仍是斯特林近似的对数形式。qsort 补充说这个估计之所以在算法复杂度分析里重要，是因为 log(n!) 属于 Θ(n log n)，而其中一侧显然、另一侧不显然，并给出了一个用两个积分同时夹出上下界的经典技巧。abetusk 顺着这条线索给出了一个漂亮的信息论解读：长度为 n 的数组有 n! 种排列，区分每种排列需要约 n·lg n 比特，所以某种意义上，任何能把输入状态映射到有序状态的方法至少需要 O(n log n) 时间——这正是基本排序算法的标准复杂度下界（当然，加入额外假设可以降低）。
andrewla 提到 Bender 和 Orszag 的经典教材用了一条完全不同的路径：不引入伽马函数，而是从差分方程出发（他形容这是”有点失传的技艺，很有 19 世纪的味道”）——注意到 log(F_n) 减 log(F_{n-1}) 等于 log(n)，把差分类比成积分，立刻得出主导渐近行为，全程不需要微积分，”不过事先知道答案会有帮助”。movpasd 则指出斯特林近似在统计力学里用得极多，因为经常要算状态空间大小的对数，也就是大量组合数和阶乘，而且它是连续的，可以直接上微积分。
关于这篇文章有没有新意的小争议：smcin 说这不过是在复述斯特林近似，一个已经存在三个世纪的结果（1730 年斯特林，1721 年棣莫弗）。DerekL 回应说文章本身就提到了斯特林近似，smcin 澄清他知道，他的意思是”没加新东西的复述意义不大”。
大数直觉这条支线最受欢迎。ninju 因为开头提到 52! 而回忆起一个二十多年前的老网页（czep.net 上那篇关于 52 张牌的文章），并好奇怎么判断它的年代——TheRealPomax 从它引用的 CSS 文件日期（2005 年 3 月）和站点”远古史”栏目的截止时间（2010 年 10 月）圈定了范围，DavidSJ 用 Wayback Machine 的首次抓取（2009 年 10 月 13 日）进一步缩小，Dwedit 则从技术风格判断”这是 XHTML 短暂狂热期的产物（而且还是无效的 XHTML）”。
svobodamartin 分享了他最喜欢的一个 52! 秒的思想实验：设一个从 52! 秒倒数到零的计时器，然后每十亿年迈一步沿赤道绕地球一圈；每绕完一圈，从太平洋里取走一滴水；等太平洋被抽干，就把它重新灌满，并在脚下放一张纸；如此反复，直到纸堆高度触及太阳；再把整个过程重复一千遍——做完这一切，计时器大约才走了三分之一。davidnc 换了个角度：52! 大致相当于一个星系里的原子数，”星系是真的很大”。hermitcrab 给出了另一个我个人觉得最妙的版本：”60! 比可观测宇宙中的原子数还多。这就是为什么婚礼座位安排这么难。”ikesau 说他做过一个把宇宙尺度转换成直观空间感的小工具，觉得这类”理解大数的配方”也值得做成同样的东西；hermitcrab 回应说他也做过类似尝试，但不限于尺寸。
编程实践相关：pagade 回忆教授让他们先用 C、再用 Lisp 求”能算出的最大阶乘”，”结果你可以想象我们有多惊讶”。smcin 认为这个对比其实没什么好惊讶的，无非是 Lisp 内置任意精度算术而 C 没有。pkaye 介绍了 Prime Swing 算法，通过质因数分解精确计算大阶乘，”1000 万的阶乘不到一秒，大约比常规方法快 100 倍”。flcikfinder 补了一条很实用的提醒：如果是实际使用而非出于好奇，不少标准库（Python 的 math.factorial 就是一例）早已用分治式乘法取代了朴素的顺序连乘，所以大部分加速你本来就免费拿到了，不必自己去实现 Prime Swing。
其他零碎：saalweachter 指出 24! 大约就是阿伏伽德罗常数，只差约 3%；smcin 较真地算出阿伏伽德罗常数对应的伽马函数反函数值约为 24.99，saalweachter 回敬说”23.99067408! 等于阿伏伽德罗常数”既难记又没那么酷。brudgers 贡献了一条简洁事实：n 大于 24 时 n! 就超过 10 的 n 次方。emil-lp 说很多人会对 n! 小于 exp(n log n) 感到意外，Someone 用三行代数指出这不过就是 n! < n^n；emil-lp 承认自己也不知道为什么，但他在大学教计算机科学，”每次讲到这里学生都很惊讶”。mohamedmohey 则把话题引向了高德纳箭号表示法、超运算和 tetrofactorial 这类更疯狂的增长速度，感叹”这些数大到基本等同于无穷，可跟真正的无穷比起来又什么都不是”。