科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 case. The conjecture asserts that root n is a lower bound on this expectation, but we only obtain (3)root n for it.
- 出版日期2018-6-22
