求L*语言最大长度9的组合数计算方法（L={pi,po}）

嘿，咱们先把问题里的关键概念理清楚，再一步步算，很快就能明白为什么结果是31啦：

首先明确几个核心点：

• 集合 L = {pi, po}，里面的每个元素都是2个字符长度的字符串；
• L* 是L的正则闭包，简单说就是所有用L里的元素任意次拼接出来的字符串（包括拼接0次的空串）；
• 我们要统计的是 L* 里字符长度不超过9的所有字符串总数。

接下来按「使用L中元素的个数」来分类计算：

• 用0个元素：就是空串，长度0，只有1种情况；
• 用1个元素：从L里挑一个，有pi和po两种选择，总长度2，数量是2；
• 用2个元素：每个位置都能选L里的任意元素，第一个元素2种选法，第二个也是2种，总共 2×2=4 种，总长度4，数量4；
• 用3个元素：同理，每个位置2种选择，2³=8 种，总长度6，数量8；
• 用4个元素：2⁴=16 种，总长度8，数量16；
• 用5个元素：总长度是 2×5=10，已经超过9了，这部分直接排除。

最后把所有符合条件的数量加起来：
1 + 2 + 4 + 8 + 16 = 31

其实这也是个等比数列求和的问题，首项是1，公比是2，一共5项，用求和公式 (2⁵ - 1)/(2-1) = 32-1=31，也能快速得到结果~

内容的提问来源于stack exchange，提问作者Diceble