/* -*- 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 ====