login
A152072
Triangle read by rows: T(n,k) = the largest product of a partition of n into k positive integers (1 <= k <= n).
4
1, 2, 1, 3, 2, 1, 4, 4, 2, 1, 5, 6, 4, 2, 1, 6, 9, 8, 4, 2, 1, 7, 12, 12, 8, 4, 2, 1, 8, 16, 18, 16, 8, 4, 2, 1, 9, 20, 27, 24, 16, 8, 4, 2, 1, 10, 25, 36, 36, 32, 16, 8, 4, 2, 1, 11, 30, 48, 54, 48, 32, 16, 8, 4, 2, 1, 12, 36, 64, 81, 72, 64, 32, 16, 8, 4, 2, 1
OFFSET
1,2
COMMENTS
The optimal partition is P(n,k) = ([(n+i)/k] : 0 <= i < k).
The table also appears in the solution of a maximum problem in arithmetic considered by K. Mahler and J. Popken. - J. van de Lune and Juan Arias-de-Reyna, Jan 05 2012
T(n,k) is the number of ways to select k class representatives from the mod k partitioning of {1,2,...,n}. - Dennis P. Walsh, Nov 27 2012
T(n,k) is the maximum number of length-k longest common subsequences of a pair of length-n strings. - Cees H. Elzinga, Jun 08 2014
REFERENCES
Cees H. Elzinga, M. Studer, Normalization of Distance and Similarity in Sequence Analysis in G. Ritschard & M. Studer (eds), Proceedings of the International Conference on Sequence Analysis and Related Methods, Lausanne, June 8-10, 2016, pp 445-468.
K. Mahler and J. Popken, Over een Maximumprobleem uit de Rekenkunde (in Dutch), (On a Maximum Problem in Arithmetic), Nieuw Archief voor Wiskunde (3) 1 (1953), 1-15.
David W. Wilson, Posting to Sequence Fans mailing List, Mar 11 2009
LINKS
Zhiwei Lin, H. Wang, C. H. Elzinga, Concordance and the Smallest Covering Set of Preference Orderings, arXiv preprint arXiv:1609.04722 [cs.AI], 2016.
FORMULA
T(n,k) = PROD(0 <= i < k; [(n+i)/k]).
T(n,n-d) = 2^d = A000079(d) (d <= n/2).
MAX(1 <= k <= n, T(n,k)) = A000792(n).
T(n,k) = (ceiling(n/k))^(n mod k)*(floor(n/k))^(k-n mod k). - Dennis P. Walsh, Nov 27 2012
Sum_{k = 1..n} T(n,k) = A152074(n). - David W. Wilson, Jul 07 2016
EXAMPLE
Triangle begins:
1
2,1
3,2,1
4,4,2,1
5,6,4,2,1
6,9,8,4,2,1
7,12,12,8,4,2,1
8,16,18,16,8,4,2,1
9,20,27,24,16,8,4,2,1
10,25,36,36,32,16,8,4,2,1
...
T(7,3)=12 since there are 12 ways to selected class representatives from the mod 3 partitioning of {1,..,7} = {1,4,7} U {2,5} U {3,6}. - Dennis P. Walsh, Nov 27 2012
MAPLE
T:= (n, k)-> mul(floor((n+i)/k), i=0..k-1):
seq(seq(T(n, k), k=1..n), n=1..12);
MATHEMATICA
T[n_, k_] := Product[ Floor[(n + i)/k], {i, 0, k - 1}]; Flatten@ Table[ T[n, k], {n, 12}, {k, n}] (* Robert G. Wilson v, Jul 08 2016 *)
PROG
(C++)
#include "boost/multiprecision/cpp_int.hpp"
using bigint = boost::multiprecision::cpp_int;
using namespace std;
bigint A152072(int n, int k)
{
bigint v = 1;
for (int i = 0; i < k; ++i)
v *= (n + i)/k;
return v;
}
int main()
{
for (int i = 1, n = 1; i < 10000; n++)
for (int k = 1; k <= n; ++k, ++i)
cout << i << " " << A152072(n, k) << endl;
}
// David W. Wilson, Jul 07 2016
CROSSREFS
T(n,1) = n = A000027(n).
T(n,2) = A002620(n-2).
T(n,3) = A006501(n).
T(n,4) = A008233(n).
T(n,5) = A008382(n).
T(n,6) = A008881(n).
T(n,7) = A009641(n).
T(n,8) = A009694(n).
T(n,9) = A009714(n).
T(n,n)=1, T(n,n-1)=A040000(n+1), T(n,n-2)=A113311(n+1).
Cf. A152074 (row sums).
Sequence in context: A300670 A355474 A137679 * A105438 A062001 A361043
KEYWORD
nonn,tabl
AUTHOR
N. J. A. Sloane, Sep 16 2009
STATUS
approved