令$q(n)$为由前n个字母组成的、长度为n且恰有一个字符的字典序比其左侧相邻的字符大的字符串总数。则显然$q(1)=0$、$q(2)=1$，且
$$q(n)=2q(n-1)+n-1.$$
这是因为若把这n个字母按升序记作$a_1,\ldots,a_n$，那么首先考虑字符串$a_{n-1}\ldots a_{1}$，把$a_n$插入到其中任意一个字母之后都可得一个满足要求的字符串，共有n-1个位置可以插入。
其次若$a_1'\ldots a_{n-1}'$是一个由前$n-1$个字母组成的、满足要求的字符串，那么可以从某个位置k'处将其分成两部分: $a_1'\ldots a_{k}'$和$a_{k+1}'\ldots a_{n-1}'$，这两个子串都递减且$a_{k+1}'>a_{k}'$，从而把$a_n$插入到$a_1'$或$a_{k+1}'$之前都可以得到一个长度为n的满足要求的字符串。
递推计算$q(n)$以及
$$p(n)=q(n)\cdot \binom{26}{n}.$$
可得结果为$p(18)=409511334375$。
import math
q=[0,0]
for i in range(2,27):
q.append(2*q[-1]+i-1)
print(max([q[i]*math.comb(26,i),i]for i in range(1,27)))
|
