Самые длинные возрастающие подпоследовательности
Число перестановок элементов
, в которых самая длинная возрастающая подпоследовательность, имеющая предельную длину
, может быть вычислена путём нахождения среднего значения
, где
являются матрицами, полученными из CircularUnitaryMatrixDistribution размера массива
.
In[1]:=
![Click for copyable input](assets.ru/longest-increasing-subsequences/In_86.png)
{k, n} = {6, 2};
Определите распределение матричных свойств и рассчитайте среднее значение.
In[2]:=
![Click for copyable input](assets.ru/longest-increasing-subsequences/In_87.png)
\[ScriptCapitalD] =
MatrixPropertyDistribution[Abs[Tr[\[ScriptCapitalU]]]^(
2 k), \[ScriptCapitalU] \[Distributed]
CircularUnitaryMatrixDistribution[n]];
N[Mean[\[ScriptCapitalD]]]
Out[2]=
![](assets.ru/longest-increasing-subsequences/O_43.png)
Сравните с прямым подсчётом.
In[3]:=
![Click for copyable input](assets.ru/longest-increasing-subsequences/In_88.png)
Count[Permutations[Range[k]],
perm_ /; Length[LongestOrderedSequence[perm]] <= n]
Out[3]=
![](assets.ru/longest-increasing-subsequences/O_44.png)
Для распределение нормированных длин самых длинных возрастающих подпоследовательностей случайных перестановок стремится к распределению Трейси-Видома с
.
In[4]:=
![Click for copyable input](assets.ru/longest-increasing-subsequences/In_89.png)
sample[n_] :=
1/n^(1/6) (Table[
Length[LongestOrderedSequence[
RandomSample[Range[n]]]], {2000}] - 2.0 Sqrt[n]);
Сравните сглаженную гистограмму выборочных нормированных длин для возрастающих измерений с функцией распределения плотности распределения Трейси-Видома.
код на языке Wolfram Language целиком
Out[5]=
![](assets.ru/longest-increasing-subsequences/O_45.png)