46.15 RestrictedPartitions

RestrictedPartitions( n, set )
RestrictedPartitions( n, set, k )

NrRestrictedPartitions( n, set )
NrRestrictedPartitions( n, set, k )

In the first form RestrictedPartitions returns the set of all restricted partitions of the positive integer n with the summands of the partition coming from the set set. In the second form RestrictedPartitions returns the set of all partitions of the positive integer n into sums with k summands with the summands of the partition coming from the set set.

In the first form NrRestrictedPartitions returns the number of restricted partitions of the positive integer n with the summands coming from the set set. In the second form NrRestrictedPartitions returns the number of restricted partitions of the positive integer n into sums with k summands with the summands of the partition coming from the set set.

A restricted partition is like an ordinary partition (see Partitions) an unordered sum n = p_1+p_2 +..+ p_k of positive integers and is represented by the list p = [p_1,p_2,..,p_k], in nonincreasing order. The difference is that here the p_i must be elements from the set set, while for ordinary partitions they may be elements from [1..n].

    gap> RestrictedPartitions( 8, [1,3,5,7] );
    [ [ 1, 1, 1, 1, 1, 1, 1, 1 ], [ 3, 1, 1, 1, 1, 1 ], [ 3, 3, 1, 1 ],
      [ 5, 1, 1, 1 ], [ 5, 3 ], [ 7, 1 ] ]
    gap> NrRestrictedPartitions( 50, [1,5,10,25,50] );
    50 

The last example tells us that there are 50 ways to return 50 cent change using 1, 5, 10 cent coins, quarters and halfdollars.

Previous Up Top Next
Index

GAP 3.4.4
April 1997