combinat-0.2.8.2: Generate and manipulate various combinatorial objects.

Math.Combinat.Partitions.Set

Description

Set partitions.

Synopsis

# The type of set partitions

newtype SetPartition Source #

A partition of the set [1..n] (in standard order)

Constructors

 SetPartition [[Int]]

Instances

 Source # Methods Source # Methods Source # Methods Source # MethodsshowList :: [SetPartition] -> ShowS # Source # Methods

# Forgetting the set structure

The "shape" of a set partition is the partition we get when we forget the set structure, keeping only the cardinalities.

# Generating set partitions

Synonym for setPartitionsNaive

Arguments

 :: Int k = number of parts -> Int n = size of the set -> [SetPartition]

Synonym for setPartitionsWithKPartsNaive

sort (setPartitionsWithKParts k n) == sort [ p | p <- setPartitions n , numberOfParts p == k ]

List all set partitions of [1..n], naive algorithm

Arguments

 :: Int k = number of parts -> Int n = size of the set -> [SetPartition]

Set partitions of the set [1..n] into k parts

Set partitions are counted by the Bell numbers

Arguments

 :: Int k = number of parts -> Int n = size of the set -> Integer

Set partitions of size k are counted by the Stirling numbers of second kind