A152072 -id:A152072 - cp's OEIS frontend

A152074 Rows sums of triangle A152072.

1, 3, 6, 11, 18, 30, 46, 73, 111, 170, 254, 392, 574, 868, 1294, 1933, 2834, 4267, 6228, 9312, 13674, 20162, 29528, 44132, 63945, 94390, 138562, 203706, 296436, 438976, 635776, 936263, 1367034, 1997200, 2907862, 4290047, 6192784, 9070744, 13248374

Offset: 1

N. J. A. Sloane, Sep 16 2009

From David W. Wilson, Jul 07 2016: (Start)
Empirically, it appears that
lim n->inf a(n+3)/a(n) = 3.
lim n->inf a(3n+1)/a(3n) = 312/217.
lim n->inf a(3n+2)/a(3n+1) = 75/52.
lim n->inf a(3n+3)/a(3n+2) = 217/150. (End)

David W. Wilson, Posting to Sequence Fans mailing List, Mar 11 2009

David W. Wilson and Vaclav Kotesovec, Table of n, a(n) for n = 1..2000 (first 1000 terms from David W. Wilson)

A152072 := proc(n,k) mul(floor((n+i)/k),i=0..k-1) ; end: A152074 := proc(n) add( A152072(n,k),k=1..n) ; end: seq(A152074(n),n=1..80) ; # R. J. Mathar, Sep 18 2009

Table[Total@ Map[Product[Floor[(n + i)/#], {i, 0, # - 1}] &, Range@ n], {n, 40}] (* Michael De Vlieger, Jul 09 2016, after Robert G. Wilson v at A152072 *)

More terms from R. J. Mathar, Sep 18 2009

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

Original entry on oeis.org

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

Cees H. Elzinga, Oct 19 2016

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

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

C. Elzinga, H. Wang, Z. Lin and Y. Kumar, Concordance and Consensus, Information Sciences, 181(2011), 2529-2549.

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

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 *)

g(k) = my(i=1); while(i!Michel Marcus, Nov 27 2016

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

A277855 Irregular triangle read by rows: T(n,k) is the maximum length of the longest common subsequence of k distinct permutations of n items with n>=1 and 1<=k<=n!

Original entry on oeis.org

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, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Cees H. Elzinga, Nov 02 2016

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

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

C. Elzinga, H. Wang, Z. Lin and Y. Kumar, Concordance and Consensus, Information Sciences, 181(2011), 2529-2549.

A277517: the maximum number of common subsequences of k distinct permutations of n items.

A152072: the maximum number of length-k longest common subsequences of a pair of length-n strings.

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 *)

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

cp's OEIS Frontend

A152074 Rows sums of triangle A152072.

Views

Author

Keywords

Comments

References

Links

Programs

Maple

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A277855 Irregular triangle read by rows: T(n,k) is the maximum length of the longest common subsequence of k distinct permutations of n items with n>=1 and 1<=k<=n!

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula