A Note on the Expected Length of the Longest Common Subsequences of two i.i.d. Random Permutations

Electronic Journal Of Combinatorics

Christian Houdré¹ 

关键词: Random permutation;    Longest common subsequence;   

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

We address a question and a conjecture on the expected length of the longest common subsequences of two i.i.d. random permutations of $[n]:=\{1,2,...,n\}$. The question is resolved by showing that the minimal expectation is not attained in the uniform cas

【 授权许可】

Others