Editing Bell number (section)

==Counting==

===Set partitions===
{{main article|Partition of a set}}
[[File:Bell numbers subset partial order.svg|thumb|right|Partitions of sets can be arranged in a partial order, showing that each partition of a set of size ''n'' "uses" one of the partitions of a set of size&nbsp;''n''&nbsp;−&nbsp;1.]]
[[File:Set partitions 5; circles.svg|thumb|The 52 partitions of a set with 5 elements]]
In general, <math>B_n</math> is the number of partitions of a set of size <math>n</math>. A partition of a set <math>S</math> is defined as a family of nonempty, pairwise disjoint subsets of <math>S</math> whose union is <math>S</math>. For example, <math>B_3 = 5</math> because the 3-element set <math>\{a,b,c\}</math> can be partitioned in 5 distinct ways:

:<math>\{ \{a\}, \{b\}, \{c\} \},</math>
:<math>\{ \{a\}, \{b, c\} \},</math>
:<math>\{ \{b\}, \{a, c\} \},</math>
:<math>\{ \{c\}, \{a, b\} \},</math>
:<math>\{ \{a, b, c\} \}.</math>

As suggested by the set notation above, the ordering of subsets within the family is not considered; [[Weak ordering|ordered partitions]] are counted by a different sequence of numbers, the [[ordered Bell number]]s. <math>B_0</math> is 1 because there is exactly one partition of the [[empty set]]. This partition is itself the empty set; it can be interpreted as a family of subsets of the empty set, consisting of zero subsets. It is [[vacuous truth|vacuously true]] that all of the subsets in this family are non-empty subsets of the empty set and that they are pairwise disjoint subsets of the empty set, because there are no subsets to have these unlikely properties.

The partitions of a set [[bijection|correspond one-to-one]] with its [[equivalence relation]]s. These are [[binary relation]]s that are [[Reflexive relation|reflexive]], [[Symmetric relation|symmetric]], and [[Transitive relation|transitive]]. The equivalence relation corresponding to a partition defines two elements as being equivalent when they belong to the same partition subset as each other. Conversely, every equivalence relation corresponds to a partition into [[equivalence class]]es.<ref>{{cite book | last = Halmos | first = Paul R. | mr = 0453532 | pages = 27–28 | publisher = Springer-Verlag, New York-Heidelberg | series = Undergraduate Texts in Mathematics | title = Naive set theory | url = https://books.google.com/books?id=jV_aBwAAQBAJ&pg=PA27 | year = 1974| isbn = 9781475716450 }}</ref> Therefore, the Bell numbers also count the equivalence relations.

===Factorizations===
If a number <math>N</math> is a [[squarefree]] positive [[integer]], meaning that it is the product of some number <math>n</math> of distinct [[prime number]]s, then <math>B_n</math> gives the number of different [[multiplicative partition]]s of <math>N</math>. These are [[factorization]]s of <math>N</math> into numbers greater than one, treating two factorizations as the same if they have the same factors in a different order.<ref>{{harvnb|Williams|1945}} credits this observation to Silvio Minetola's ''Principii di Analisi Combinatoria'' (1909).</ref> For instance, 30 is the product of the three primes 2, 3, and&nbsp;5, and has <math>B_3</math> = 5 factorizations:
:<math>30 = 2\times 15=3\times 10=5\times 6=2\times 3\times 5</math>

===Rhyme schemes===
The Bell numbers also count the [[rhyme scheme]]s of an ''n''-line [[poem]] or [[stanza]]. A rhyme scheme describes which lines rhyme with each other, and so may be interpreted as a partition of the set of lines into rhyming subsets. Rhyme schemes are usually written as a sequence of Roman letters, one per line, with rhyming lines given the same letter as each other, and with the first lines in each rhyming set labeled in alphabetical order. Thus, the 15 possible four-line rhyme schemes are AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, and ABCD.{{sfn|Gardner|1978}}

===Permutations===
The Bell numbers come up in a card [[shuffling]] problem mentioned in the addendum to {{harvnb|Gardner|1978}}. If a deck of ''n'' cards is shuffled by repeatedly removing the top card and reinserting it anywhere in the deck (including its original position at the top of the deck), with exactly ''n'' repetitions of this operation, then there are ''n''<sup>''n''</sup> different shuffles that can be performed. Of these, the number that return the deck to its original sorted order is exactly ''B<sub>n</sub>''. Thus, the probability that the deck is in its original order after shuffling it in this way is ''B<sub>n</sub>''/''n''<sup>''n''</sup>, which is significantly larger than the 1/''n''! probability that would describe a uniformly random permutation of the deck.

Related to card shuffling are several other problems of counting special kinds of [[permutation]]s that are also answered by the Bell numbers. For instance, the ''n''th Bell number equals the number of permutations on ''n'' items in which no three values that are in sorted order have the last two of these three consecutive. In a notation for generalized [[permutation pattern]]s where values that must be consecutive are written adjacent to each other, and values that can appear non-consecutively are separated by a dash, these permutations can be described as the permutations that avoid the pattern 1-23. The permutations that avoid the generalized patterns 12-3, 32-1, 3-21, 1-32, 3-12, 21-3, and 23-1 are also counted by the Bell numbers.{{sfnp|Claesson|2001}} The permutations in which every 321 pattern (without restriction on consecutive values) can be extended to a 3241 pattern are also counted by the Bell numbers.{{sfnp|Callan|2006}} However, the Bell numbers grow too quickly to count the permutations that avoid a pattern that has not been generalized in this way: by the (now proven) [[Stanley–Wilf conjecture]], the number of such permutations is singly exponential, and the Bell numbers have a higher asymptotic growth rate than that.