

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 nth row are the same as in the (n1)th row followed by n2 ones followed by A001563(n)(n2).  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), 25292549.


FORMULA

T(n,k) = 2^(ng(k))+g(k)2^(ng(k))+max{0,g(k)2(k(g(k)1)!1)}2^(ng(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(n1,k) for 1<=k<=(n1)!,
T(n,k) = 2*T(n1,(n1)!)(k(n1)!) for (n1)!+1<=k<=(n1)!+n2,
T(n,k) = n+1 for (n1)!+n1<=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 nth 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 <= (n1)!, 2 T[n1, k], (n1)! + 1 <= k <= (n1)! + n  2, 2*T[n1, (n1)!]  (k  (n1)!), (n  1)! + n  1 <= k <= n!, n+1, True, 2^(ng[k])*Max[0, (g[k1]! + k  1) + g[k]  2] + g[k]*2^(ng[k]) + 2^(ng[k])]; Table[T[n, k], {n, 1, 5}, {k, 1, n!}] // Flatten (* JeanFrançois Alcover, Nov 28 2016 *)


PROG

(PARI) g(k) = my(i=1); while(i!<k, i++); i;
T(n, k) = 2^(ng(k)) + g(k)*2^(ng(k)) + max(0, g(k)2(k(g(k)1)!1))*2^(ng(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 lengthk common subsequences of a pair of lengthn strings).
Cf. A090529 (a(n)=the smallest m such that n<=m!)
Sequence in context: A054427 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



