cp's OEIS Frontend

A277855 Irregular triangle read by rows: T(n,k) is the maximum length of the longest common subsequence of k distinct permutations of n items with n>=1 and 1<=k<=n!

%I A277855 #17 Jan 10 2018 20:28:50
%S A277855 1,2,1,3,2,2,1,1,1,4,3,3,3,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,5,
%T A277855 4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
%U A277855 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1
%N A277855 Irregular triangle read by rows: T(n,k) is the maximum length of the longest common subsequence of k distinct permutations of n items with n>=1 and 1<=k<=n!
%C A277855 The formulas given below are correct. The sequence can be used to normalize the length of the longest common subsequence of a set of k full preference orderings relative to the maximum attainable length. This normalized number is a measure of concordance in the set of preference orderings.
%C A277855 The run lengths are given by A130477. - _Andrey Zabolotskiy_, Nov 02 2016
%H A277855 C. Elzinga, H. Wang, Z. Lin and Y. Kumar, <a href="http://dx.doi.org/10.1016/j.ins.2011.02.001">Concordance and Consensus</a>, Information Sciences, 181(2011), 2529-2549.
%F A277855 T(n,1)=n.
%F A277855 For n>1, 1<=k<=n! and 1<=j<=n, T(n,k)=n-j if binomial(n,n-j+1)*(j-1)!+1<=k<=binomial(n,n-j)*j!.
%e A277855 The permutations {abc, acb} have 2 longest common subsequences of length 2: ab and ac. The permutations {abc, acb, cab} have one longest common subsequence: ab of length 2. The formula above yields T(3,3)= 2.
%e A277855 The triangle begins:
%e A277855 1
%e A277855 2,1
%e A277855 3,2,2,1,1,1
%e A277855 4,3,3,3,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1
%e A277855 5,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,...
%t A277855 Flatten[Table[(n - Select[Range@ n, Function[j, Binomial[n, n - j + 1] (j - 1)! + 1 <= k <= Binomial[n, n - j] j!]]) /. {} -> {n}, {n, 5}, {k, n!}], {3}] // Flatten (* _Michael De Vlieger_, Nov 04 2016 *)
%Y A277855 A277517: the maximum number of common subsequences of k distinct permutations of n items.
%Y A277855 A152072: the maximum number of length-k longest common subsequences of a pair of length-n strings.
%K A277855 nonn,tabf
%O A277855 1,2
%A A277855 _Cees H. Elzinga_, Nov 02 2016