login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; table; graph; refs; listen; history; text; internal format)
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

David W. Wilson, Table of n, a(n) for n = 1..10011

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: A131967 A300670 A137679 * A105438 A062001 A181847

Adjacent sequences:  A152069 A152070 A152071 * A152073 A152074 A152075

KEYWORD

nonn,tabl

AUTHOR

N. J. A. Sloane, Sep 16 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 16:50 EDT 2019. Contains 328302 sequences. (Running on oeis4.)