login
Triangle read by rows: T(n,k) = the largest product of a partition of n into k positive integers (1 <= k <= n).
4

%I #54 Sep 04 2017 09:02:00

%S 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,

%T 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,

%U 48,32,16,8,4,2,1,12,36,64,81,72,64,32,16,8,4,2,1

%N Triangle read by rows: T(n,k) = the largest product of a partition of n into k positive integers (1 <= k <= n).

%C The optimal partition is P(n,k) = ([(n+i)/k] : 0 <= i < k).

%C 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

%C 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

%C 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

%D 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.

%D 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.

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

%H David W. Wilson, <a href="/A152072/b152072.txt">Table of n, a(n) for n = 1..10011</a>

%H Zhiwei Lin, H. Wang, C. H. Elzinga, <a href="https://arxiv.org/abs/1609.04722">Concordance and the Smallest Covering Set of Preference Orderings</a>, arXiv preprint arXiv:1609.04722 [cs.AI], 2016.

%F T(n,k) = PROD(0 <= i < k; [(n+i)/k]).

%F T(n,n-d) = 2^d = A000079(d) (d <= n/2).

%F MAX(1 <= k <= n, T(n,k)) = A000792(n).

%F T(n,k) = (ceiling(n/k))^(n mod k)*(floor(n/k))^(k-n mod k). - _Dennis P. Walsh_, Nov 27 2012

%F Sum_{k = 1..n} T(n,k) = A152074(n). - _David W. Wilson_, Jul 07 2016

%e Triangle begins:

%e 1

%e 2,1

%e 3,2,1

%e 4,4,2,1

%e 5,6,4,2,1

%e 6,9,8,4,2,1

%e 7,12,12,8,4,2,1

%e 8,16,18,16,8,4,2,1

%e 9,20,27,24,16,8,4,2,1

%e 10,25,36,36,32,16,8,4,2,1

%e ...

%e 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

%p T:= (n,k)-> mul(floor((n+i)/k), i=0..k-1):

%p seq(seq(T(n, k), k=1..n), n=1..12);

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

%o (C++)

%o #include "boost/multiprecision/cpp_int.hpp"

%o using bigint = boost::multiprecision::cpp_int;

%o using namespace std;

%o bigint A152072(int n, int k)

%o {

%o bigint v = 1;

%o for (int i = 0; i < k; ++i)

%o v *= (n + i)/k;

%o return v;

%o }

%o int main()

%o {

%o for (int i = 1, n = 1; i < 10000; n++)

%o for (int k = 1; k <= n; ++k, ++i)

%o cout << i << " " << A152072(n, k) << endl;

%o }

%o // _David W. Wilson_, Jul 07 2016

%Y T(n,1) = n = A000027(n).

%Y T(n,2) = A002620(n-2).

%Y T(n,3) = A006501(n).

%Y T(n,4) = A008233(n).

%Y T(n,5) = A008382(n).

%Y T(n,6) = A008881(n).

%Y T(n,7) = A009641(n).

%Y T(n,8) = A009694(n).

%Y T(n,9) = A009714(n).

%Y T(n,n)=1, T(n,n-1)=A040000(n+1), T(n,n-2)=A113311(n+1).

%Y Cf. A152074 (row sums).

%K nonn,tabl

%O 1,2

%A _N. J. A. Sloane_, Sep 16 2009