最长增长子序列
对于含 个元素的排列
,它的最长增长子序列的长度最多为
,其排列数可以通过在
上取平均计算,其中
是从维度为
的 CircularUnitaryMatrixDistribution 中抽取的矩阵.
In[1]:=
![Click for copyable input](assets.zh/longest-increasing-subsequences/In_86.png)
{k, n} = {6, 2};
定义矩阵属性分布,并计算均值.
In[2]:=
![Click for copyable input](assets.zh/longest-increasing-subsequences/In_87.png)
\[ScriptCapitalD] =
MatrixPropertyDistribution[Abs[Tr[\[ScriptCapitalU]]]^(
2 k), \[ScriptCapitalU] \[Distributed]
CircularUnitaryMatrixDistribution[n]];
N[Mean[\[ScriptCapitalD]]]
Out[2]=
![](assets.zh/longest-increasing-subsequences/O_43.png)
与直接计数比较.
In[3]:=
![Click for copyable input](assets.zh/longest-increasing-subsequences/In_88.png)
Count[Permutations[Range[k]],
perm_ /; Length[LongestOrderedSequence[perm]] <= n]
Out[3]=
![](assets.zh/longest-increasing-subsequences/O_44.png)
对于 ,随机排列的最长增长子序列的缩放长度分布收敛于
的特雷西–维多姆分布.
In[4]:=
![Click for copyable input](assets.zh/longest-increasing-subsequences/In_89.png)
sample[n_] :=
1/n^(1/6) (Table[
Length[LongestOrderedSequence[
RandomSample[Range[n]]]], {2000}] - 2.0 Sqrt[n]);
将维数增加的缩放长度采样的平滑直方图与特雷西–维多姆分布的概率密度函数比较.
显示完整的 Wolfram 语言输入
Out[5]=
![](assets.zh/longest-increasing-subsequences/O_45.png)