46.14 OrderedPartitions

OrderedPartitions( n )
OrderedPartitions( n, k )

NrOrderedPartitions( n )
NrOrderedPartitions( n, k )

In the first form OrderedPartitions returns the set of all ordered partitions of the positive integer n. In the second form OrderedPartitions returns the set of all ordered partitions of the positive integer n into sums with k summands.

In the first form NrOrderedPartitions returns the number of ordered partitions of the positive integer n. In the second form NrOrderedPartitions returns the number of ordered partitions of the positive integer n into sums with k summands.

An ordered partition is an ordered sum n = p_1 + p_2 + .. + p_k of positive integers and is represented by the list [ p_1, p_2, .., p_k ]. There are totally 2^{n-1} ordered partitions and {n-1 choose k-1} (see Binomial) partitions with k summands.

Do not call OrderedPartitions with an n larger than 15, the list will simply become too large.

    gap> OrderedPartitions( 5 );
    [ [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 2 ], [ 1, 1, 2, 1 ], [ 1, 1, 3 ],
      [ 1, 2, 1, 1 ], [ 1, 2, 2 ], [ 1, 3, 1 ], [ 1, 4 ], [ 2, 1, 1, 1 ],
      [ 2, 1, 2 ], [ 2, 2, 1 ], [ 2, 3 ], [ 3, 1, 1 ], [ 3, 2 ], 
      [ 4, 1 ], [ 5 ] ]
    gap> OrderedPartitions( 6, 3 );
    [ [ 1, 1, 4 ], [ 1, 2, 3 ], [ 1, 3, 2 ], [ 1, 4, 1 ], [ 2, 1, 3 ],
      [ 2, 2, 2 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ], [ 4, 1, 1 ] ]
    gap> NrOrderedPartitions(20);
    524288 

The function Partitions (see Partitions) is the unordered counterpart of OrderedPartitions.

Previous Up Top Next
Index