/* -*- gp-script -*- */
\\% integer partitions
\\ Author: Richard J. Mathar
\\ cf. http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=671
\\ Added function partitv(), Joerg Arndt, 2012-August-14
\\ online at http://www.jjj.de/pari/
\\ version: 2014-October-16 (18:30)
/** Create partitions of n with exactly m terms, each term >= nmin.
* @param[in] n the number to be partitionend
* @param[in] m the number of (nonzero) terms in the partitions
* @param[in] nmin a minimum set to each term in each of the partitions
* @return A matrix of m columns. Terms of each row represent
* a partition of n. All values in the matrix are larger than or
* equal to nmin and smaller than or equal to n. In each row, values are sorted
* in ascending order, and sum to n. The criterion of ordering is that
* the rows with the smallest minimum term have smallest row numbers.
* (If these are equal, the 2nd smallest minmum term takes over and so on.)
*
* @remarks This is mainly an auxiliary function to partit(). Negative values
* of n or m return the empty matrix.
*
* @test For n = 5, m=2, nmin=1 the return value is the 2x2 matrix
* [ 1, 4; 2, 3]
*
* @since 2007-09-24
* @author Richard J. Mathar
*/
partitm(n, m, nmin)=
{
my(resul,partj);
if( type(n) != "t_INT" || type(m) != "t_INT" || type(nmin) != "t_INT",
error("One argument ", n, " or ", m, " or ", nmin, " to partitm() is not an integer!")
);
if( n < 0 || m <0 ,
return([;]);
);
resul=matrix(0,m);
if(m==0,
return(resul);
);
/* The strategy is recursion. We split off any number j starting with
* the minimum allowed and increasing it within the natural limits
* set by n. Then we look which partitions could result supposed this
* term had been removed from the sum and supposed the number of terms
* were reduced by 1.
*/
for(j=max(1,nmin),n\m,
partj=partitm(n-j,m-1,j);
/* Essentially attach the number j to the front of each of the
* subpartitions of n-j, and append that to the matrix of the
* results.
*/
for(r1=1,matsize(partj)[1],
resul=concat(resul,concat([j],partj[r1,]));
);
);
if(m==1 && n >= nmin,
resul=concat(resul,[[n]]);
);
return(resul);
} /* ----- */
/** Create partitions of n.
* @param[in] n The positive integer to be decomposed into a sum (partition)
* of nonzero terms.
* @return A matrix of n columns and numbpart(n) rows, with the exception of
* n=0 where zero rows are returned, not one. Each row represents
* a different partition of n. The rows are sorted with respect to the
* number of terms in the partitions; the first row contains the partition
* into a single term (which is n itself), the second row and following
* contains the partitions with 2 terms, the next row the partitions into
* 3 terms, and so on until the last row, which contains the partition
* [1,1,1,...,1] into n terms. Within each group of rows with the same
* number of terms, as a secondary criterion for sorting, the partitions
* with the smaller terms are placed at smaller row numbers. Sometimes this
* is called the Abramowitz-Stegun order. The columns contain the individual
* terms for the partition in ascending order, filled with zeros after
* the last term in all but the last rows.
* @remarks For non-integer arguments, an error is created. For negative n,
* the emtpy matrix is returned.
*
* @test For n = 5 the return value is the 7x5 matrix
* [5, 0, 0, 0, 0;
* 1, 4, 0, 0, 0;
* 2, 3, 0, 0, 0;
* 1, 1, 3, 0, 0;
* 1, 2, 2, 0, 0;
* 1, 1, 1, 2, 0;
* 1, 1, 1, 1, 1]
* with numbpart(5)=7 rows, describing 5=1+4=2+3=1+1+3=1+2+2=1+1+1+2=1+1+1+1+1.
* @see table 24.2 in M. Abramowitz and I. A. Stegun, Handbook of Mathematical
* Functions, Dover.
* @since 2007-09-24
* @author Richard J. Mathar
*/
partit(n)=
{
my(resul,partm,filr);
if( type(n) != "t_INT",
error("Argument ", n, " to partit() is not an integer!")
);
if( n < 0,
return([;]);
);
resul=matrix(0,n);
/* For each number of terms from 1 to n, we create the partitions
* with that number of terms, fill the corresponding matrices with
* zeros to the right and add them to the bottom of the existing
* intermediate set of results.
*/
for(m=1,n,
partm=partitm(n,m,1);
filr=vector(n-m);
for(r1=1,matsize(partm)[1],
resul=concat( resul,concat(partm[r1,],filr) );
);
);
return(resul);
} /* ----- */
partitv(n)=
\\ Return vector of partitions.
\\ partitv(5) ==>
\\ [[5], [1, 4], [2, 3], [1, 1, 3], [1, 2, 2], [1, 1, 1, 2], [1, 1, 1, 1, 1]]
{
my(np,v,P,ct=0);
np = numbpart(n);
v = vector(np);
for(m=1,n,
P=partitm(n,m,1);
for(r=1,matsize(P)[1],
ct += 1;
v[ct] = P[r,];
);
);
return(v);
} /* ----- */
/** Count number of partitions into distinct parts.
* @param[in] n the number to be decomposed.
* @return The number of ways of partitioning n into a sum of strictly positive
* and distinct terms.
* @test The case n=5 returns 3, which represents the 3 different sums
* 5, 1+4, and 2+3.
* @see table 24.5 in M. Abramowitz and I. A. Stegun, Handbook of Mathematical
* Functions, Dover.
* @since 2007-09-24
* @author Richard J. Mathar
*/
numbpartq(n)=
{
if( type(n) != "t_INT",
error("Argument ", n, " to numbpartq() is not an integer!")
);
/* We simply refer to the generating function. This correctly returns
* zero for negative n.
*/
polcoeff(prod(j=1,n,1+x^j),n);
} /* ----- */
\\ ==== end of file ====