Partition of A Set - Counting Partitions

Counting Partitions

The total number of partitions of an n-element set is the Bell number Bn. The first several Bell numbers are B0 = 1, B1 = 1, B2 = 2, B3 = 5, B4 = 15, B5 = 52, and B6 = 203. Bell numbers satisfy the recursion

and have the exponential generating function

The number of partitions of an n-element set into exactly k nonempty parts is the Stirling number of the second kind S(n, k).

The number of noncrossing partitions of an n-element set is the Catalan number Cn, given by

Read more about this topic:  Partition Of A Set

Famous quotes containing the words counting and/or partitions:

    “But counting up to two
    Is harder to do....”
    —Philip Larkin (1922–1986)

    “Great wits are sure to madness near allied,
    And thin partitions do their bounds divide.”
    —John Dryden (1631–1700)