Subsecuencias crecientes más largas
El número de permutaciones de elementos
en donde la subsecuencia creciente más larga está en la mayor parte de la longitud
, puede ser calculada promediando
, donde
son matrices extraídas de CircularUnitaryMatrixDistribution de dimensión
.
In[1]:=
![Click for copyable input](assets.es/longest-increasing-subsequences/In_86.png)
{k, n} = {6, 2};
Defina la distribución de propiedades de matriz y calcule la media.
In[2]:=
![Click for copyable input](assets.es/longest-increasing-subsequences/In_87.png)
\[ScriptCapitalD] =
MatrixPropertyDistribution[Abs[Tr[\[ScriptCapitalU]]]^(
2 k), \[ScriptCapitalU] \[Distributed]
CircularUnitaryMatrixDistribution[n]];
N[Mean[\[ScriptCapitalD]]]
Out[2]=
![](assets.es/longest-increasing-subsequences/O_43.png)
Compare con el conteo directo.
In[3]:=
![Click for copyable input](assets.es/longest-increasing-subsequences/In_88.png)
Count[Permutations[Range[k]],
perm_ /; Length[LongestOrderedSequence[perm]] <= n]
Out[3]=
![](assets.es/longest-increasing-subsequences/O_44.png)
Para , la distribución de las longitudes escaladas de subsecuencias crecientes más grandes de permutaciones aleatorias converge con la distribución Tracy–Widom con
.
In[4]:=
![Click for copyable input](assets.es/longest-increasing-subsequences/In_89.png)
sample[n_] :=
1/n^(1/6) (Table[
Length[LongestOrderedSequence[
RandomSample[Range[n]]]], {2000}] - 2.0 Sqrt[n]);
Compare el histograma alisado de longitudes escaladas muestreadas para aumentar las dimensiones con la función de densidad de probabilidad de la distribución de Tracy–Widom.
muestre la entrada completa de Wolfram Language
Out[5]=
![](assets.es/longest-increasing-subsequences/O_45.png)