Editing Partition of a set (section)

== Counting partitions ==
The total number of partitions of an ''n''-element set is the [[Bell numbers|Bell number]] ''B<sub>n</sub>''. The first several Bell numbers are ''B''<sub>0</sub> = 1,
''B''<sub>1</sub> = 1, ''B''<sub>2</sub> = 2, ''B''<sub>3</sub> = 5, ''B''<sub>4</sub> = 15, ''B''<sub>5</sub> = 52, and ''B''<sub>6</sub> = 203 {{OEIS|A000110}}. Bell numbers satisfy the [[recursion]]

: <math>B_{n+1}=\sum_{k=0}^n {n\choose k} B_k</math>

and have the [[generating function|exponential generating function]]

:<math>\sum_{n=0}^\infty\frac{B_n}{n!}z^n=e^{e^z-1}.</math>

[[Image:BellNumberAnimated.gif|right|thumb|Construction of the [[Bell triangle]]]]
The Bell numbers may also be computed using the [[Bell triangle]]
in which the first value in each row is copied from the end of the previous row, and subsequent values are computed by adding two numbers, the number to the left and the number to the above left of the position. The Bell numbers are repeated along both sides of this triangle. The numbers within the triangle count partitions in which a given element is the largest [[singleton (mathematics)|singleton]].

The number of partitions of an ''n''-element set into exactly ''k'' (non-empty) 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]] 
:<math>C_n={1 \over n+1}{2n \choose n}.</math>