

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

Table of n, a(n) for n=1..100.
C. Elzinga, H. Wang, Z. Lin and Y. Kumar, Concordance and Consensus, Information Sciences, 181(2011), 25292549.


FORMULA

T(n,1)=n.
For n>1, 1<=k<=n! and 1<=j<=n, T(n,k)=nj if binomial(n,nj+1)*(j1)!+1<=k<=binomial(n,nj)*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 lengthk longest common subsequences of a pair of lengthn 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



