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!.

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

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

Table of n, a(n) for n=1..66.

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!<k, i++); i;
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));
tabf(nn) = {for (n = 1, nn, for (k= 1, n!, print1(T(n, k), ", "); ); print(); ); } \\ Michel Marcus, Nov 27 2016

Crossrefs

Cf. A277855 (the maximum length of the longest common subsequence of k distinct permutations of n items).

Cf. A152072 (the maximum number of length-k common subsequences of a pair of length-n strings).

Cf. A090529 (a(n)=the smallest m such that n<=m!)

Sequence in context: A363537 A232563 A048672 * A248513 A266414 A245613

Adjacent sequences: A277514 A277515 A277516 * A277518 A277519 A277520

Keyword

nonn,tabf

Author

Cees H. Elzinga, Oct 19 2016

Status

approved