The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A277517 Irregular triangle read by rows: T(n,k) is the maximum number of common subsequences of k distinct permutations of n items, with n>=1 and 1<=k<=n!. 1
 2, 4, 3, 8, 6, 5, 4, 4, 4, 16, 12, 10, 8, 8, 8, 7, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 32, 24, 20, 16, 16, 16, 14, 12, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 8, 7, 6, 6, 6, 6, 6, 6 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,1 COMMENTS The sequence can be used to normalize the number of common distinct subsequences of k full preference orderings of n items relative to its maximum attainable value. This normalized number can be used as measure of concordance. According to the formula, the run lengths in the n-th row are the same as in the (n-1)-th row followed by n-2 ones followed by A001563(n)-(n-2). - 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,k) = 2^(n-g(k))+g(k)2^(n-g(k))+max{0,g(k)-2-(k-(g(k)-1)!-1)}2^(n-g(k)) with g(k) = min{i: i>0 and i!>=k}. Consecutive rows of the array can be generated from T(2,1)=4 and T(2,2)=3 for n>3 by the recursion: T(n,k) = 2*T(n-1,k) for 1<=k<=(n-1)!, T(n,k) = 2*T(n-1,(n-1)!)-(k-(n-1)!) for (n-1)!+1<=k<=(n-1)!+n-2, T(n,k) = n+1 for (n-1)!+n-1<=k<=n!. EXAMPLE T(3,3) = 5 since the 3 distinct permutations {abc, bac, bca} have 5 subsequences in common: {a, b, c, bc, empty}. The n-th row of the array has a length of n!. Triangle begins: 2; 4,3; 8,6,5,4,4,4; 16,12,10,8,8,8,7,6,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5; 32,24,20,16,16,16,14,12,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,9,... MATHEMATICA g[k_] := Reduce[i >= 0 && i! >= k, i, Integers][[2, 2]]; T[1, 1] = 2; T[2, 1] = 4; T[2, 2] = 3; T[n_, k_] := T[n, k] = Which[1 <= k <= (n-1)!, 2 T[n-1, k], (n-1)! + 1 <= k <= (n-1)! + n - 2, 2*T[n-1, (n-1)!] - (k - (n-1)!), (n - 1)! + n - 1 <= k <= n!, n+1, True, 2^(n-g[k])*Max[0, -(-g[k-1]! + k - 1) + g[k] - 2] + g[k]*2^(n-g[k]) + 2^(n-g[k])]; Table[T[n, k], {n, 1, 5}, {k, 1, n!}] // Flatten (* Jean-François Alcover, Nov 28 2016 *) PROG (PARI) g(k) = my(i=1); while(i!

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

Last modified October 3 17:17 EDT 2022. Contains 357237 sequences. (Running on oeis4.)