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
T(n+k,k) is the maximum number of divisors a number with k distinct and n total prime factors can have. - Felix Huber, Nov 25 2025
REFERENCES
Cees H. Elzinga and 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.
David W. Wilson, Posting to Sequence Fans mailing List, Mar 11 2009.
LINKS
David W. Wilson, Table of n, a(n) for n = 1..10011
Cees H. Elzinga and M. Studer, Normalization of Distance and Similarity in Sequence Analysis, Sociological Methods & Research, Volume 48, Issue 4, 2019.
Zhiwei Lin, H. Wang, and C. H. Elzinga, Concordance and the Smallest Covering Set of Preference Orderings, arXiv preprint arXiv:1609.04722 [cs.AI], 2016.
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.
FORMULA
T(n,k) = Product_{i=0..k-1} [(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] 1;
[ 2] 2, 1;
[ 3] 3, 2, 1;
[ 4] 4, 4, 2, 1;
[ 5] 5, 6, 4, 2, 1;
[ 6] 6, 9, 8, 4, 2, 1;
[ 7] 7, 12, 12, 8, 4, 2, 1;
[ 8] 8, 16, 18, 16, 8, 4, 2, 1;
[ 9] 9, 20, 27, 24, 16, 8, 4, 2, 1;
[10] 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
KEYWORD
nonn,tabl
AUTHOR
N. J. A. Sloane, Sep 16 2009
STATUS
approved