The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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! 1
 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, 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, 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS 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. The run lengths are given by A130477. - Andrey Zabolotskiy, Nov 02 2016 LINKS C. Elzinga, H. Wang, Z. Lin and Y. Kumar, Concordance and Consensus, Information Sciences, 181(2011), 2529-2549. FORMULA T(n,1)=n. 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!. EXAMPLE 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. The triangle begins: 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,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,... MATHEMATICA 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 *) CROSSREFS A277517: the maximum number of common subsequences of k distinct permutations of n items. A152072: the maximum number of length-k longest common subsequences of a pair of length-n strings. Sequence in context: A035181 A035151 A290536 * A136662 A023595 A177718 Adjacent sequences:  A277852 A277853 A277854 * A277856 A277857 A277858 KEYWORD nonn,tabf AUTHOR Cees H. Elzinga, Nov 02 2016 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 30 10:29 EDT 2020. Contains 333125 sequences. (Running on oeis4.)