|
%I #66 Dec 07 2016 11:14:19
%S 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,
%T 32,24,20,16,16,16,14,12,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,
%U 10,9,8,7,6,6,6,6,6,6
%N 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!.
%C 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.
%C 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
%H C. Elzinga, H. Wang, Z. Lin and Y. Kumar, <a href="http://dx.doi.org/10.1016/j.ins.2011.02.001">Concordance and Consensus</a>, Information Sciences, 181(2011), 2529-2549.
%F 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}.
%F Consecutive rows of the array can be generated from T(2,1)=4 and T(2,2)=3 for n>3 by the recursion:
%F T(n,k) = 2*T(n-1,k) for 1<=k<=(n-1)!,
%F T(n,k) = 2*T(n-1,(n-1)!)-(k-(n-1)!) for (n-1)!+1<=k<=(n-1)!+n-2,
%F T(n,k) = n+1 for (n-1)!+n-1<=k<=n!.
%e T(3,3) = 5 since the 3 distinct permutations {abc, bac, bca} have 5 subsequences in common: {a, b, c, bc, empty}.
%e The n-th row of the array has a length of n!.
%e Triangle begins:
%e 2;
%e 4,3;
%e 8,6,5,4,4,4;
%e 16,12,10,8,8,8,7,6,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5;
%e 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,...
%t 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 *)
%o (PARI) g(k) = my(i=1); while(i!<k, i++); i;
%o 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));
%o tabf(nn) = {for (n = 1, nn, for (k= 1, n!, print1(T(n, k), ", ");); print(););} \\ _Michel Marcus_, Nov 27 2016
%Y Cf. A277855 (the maximum length of the longest common subsequence of k distinct permutations of n items).
%Y Cf. A152072 (the maximum number of length-k common subsequences of a pair of length-n strings).
%Y Cf. A090529 (a(n)=the smallest m such that n<=m!)
%K nonn,tabf
%O 1,1
%A _Cees H. Elzinga_, Oct 19 2016
|
