The procedure ** Partition** significantly generalizes the standard procedure **combinat[partition]** in several ways. The user specifies the number of parts of the partition, and can also set different limitations on parts partition.

Required parameters: **n** - a nonnegative integer, **k **- a positive integer or a range (**k** specifies the number of parts of the partition). The parameter **res** is the optional parameter (by default **res** is **1 **). If **res** is a number, all elements of **k**-tuples must be greater than or equal ** res **. If **res** is a range ** a .. b** , ** **all elements of** ****k**-tuples must be greater than or equal** **** a **and less than or equal** **** b** . The optional parameter **S** - set, which includes elements of the partition. By default ** S = {$ 0.. n} **.

The code of the procedure:

**Partition:=proc(n::nonnegint, k::{posint,range}, res::{range, nonnegint} := 1, S::set:={$0..n}) **# Generates a list of all partitions of an integer n into k parts

**local k_Partition, n1, k1, L;**

** **

**k_Partition := proc (n, k::posint, res, S)**

**local m, M, a, b, S1, It, L0;**

**m:=S[1]; M:=S[-1];**

**if res::nonnegint then a := max(res,m); b := min(n-(k-1)*a,M) else a := max(lhs(res),m); b := min(rhs(res),M) fi;**

**S1:={$a..b} intersect S;**

**if b < a or b*k < n or a*k > n then return [ ] fi;**

**It := proc (L)**

**local m, j, P, R, i, N;**

**m := nops(L[1]); j := k-m; N := 0;**

**for i to nops(L) do**

**R := n-`+`(op(L[i]));**

**if R <= b*j and a*j <= R then N := N+1;**

**P[N] := [seq([op(L[i]), s], s = {$ max(a, R-b*(j-1)) .. min(R, b)} intersect select(t->t>=L[i,-1],S1) )] fi;**

**od;**

**[seq(op(P[s]), s = 1 .. N)];**

**end proc;**

**if k=1 then [[b]] else (It@@(k-1))(map(t->[t],S1)) fi;**

**end proc;**

** **

**if k::posint then return k_Partition(n,k,res,S) else n1:=0;**

**for k1 from lhs(k) to rhs(k) do**

**n1:=n1+1; L[n1]:=k_Partition(n,k1,res,S)**

**od;**

**L:=convert(L,list);**

**[seq(op(L[i]), i=1..n1)] fi;**

** **

**end proc:**

Examples of use:

**Partition(15, 3);**

**Partition(15, 3..5, 1..5); **# The number of parts from 3 to 5, and each summand from 1 to 5

**Partition(15, 5, {seq(2*n-1, n=1..8)}); **# 5 summands and all are odd numbers

** **

A more interesting example.

There are **k** banknotes in possible denominations of 5, 10, 20, 50, 100 dollars. At what number of banknotes **k** the number of variants of exchange **$140** will be maximum?

**n:=0:**

**for k from 3 to 28 do**

**n:=n+1: V[n]:=[k, nops(Partition(140, k, {5,10,20,50,100}))];**

**od:**

**V:=convert(V, list);**

**max(seq(V[i,2], i=1..nops(V)));**

**select(t->t[2]=8, V);**

Here are these variants:

**Partition(140, 10, {5,10,20,50,100});**

**Partition(140, 13, {5,10,20,50,100});**

Partition.mws