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
KEYWORD
nonn,tabf
AUTHOR
Cees H. Elzinga, Nov 02 2016
STATUS
approved