Bell numbers Wiki — STIMSMITH

Bell numbers

Concept WIKI v1 · 5/31/2026

Bell numbers are the numbers of set partitions: the nth Bell number b_n is the number of partitions of an n-element set. In the provided sources, they are given with the recurrence b_0 = 1 and b_{n+1} = \sum_{k=0}^n \binom{n}{k} b_k, and they are used to count possible index-relationship patterns in array-oriented test generation and to state hard bounds in hashing/min-entropy condenser analysis.

Definition

Bell numbers count set partitions. The provided TACAS source states that the number of partitions of an n-set is the nth Bell number, written (b_n).

Recurrence

The same source gives the following recurrence:

(b_0 = 1)
(b_{n+1} = \sum_{k=0}^{n} \binom{n}{k} b_k), for (n \ge 0)
with (\binom{n}{k} = \frac{n!}{k!(n-k)!})

Use in the provided sources

Array-index relationship enumeration

In the TACAS source on code-based test generation, Bell numbers are used to count relationship patterns among indices. The text states that, for (n) indices, the number of possible partitions corresponds to the nth Bell number. This is used in discussing alias-coverage style criteria for array manipulation, where different choices of index relationships must be explored.

That source also remarks that the Bell-number-based enumeration has exponential complexity, but says this is acceptable in that setting because only a correct combination for indices is searched.

Hashing and min-entropy condensers

The provided arXiv paper on q-wise independence tails states that it gives hard bounds in terms of Bell numbers. In that context, Bell numbers appear as part of quantitative bounds connected to hashing and min-entropy condenser analysis.

Scope note

This article only includes properties and applications that are explicitly supported by the provided evidence.

LINKED ENTITIES

2 links

Code-based Test Generation for Validation of Functional Processor Descriptions USES

array constraints USES

CITATIONS

5 sources

5 citations

[1] Bell numbers count partitions of an n-element set. Fabrice.Baray,Henri.Michel

[2] The provided source gives the recurrence b_0 = 1 and b_{n+1} = sum_{k=0}^n binom(n,k) b_k, with binom(n,k) = n!/(k!(n-k)!). Fabrice.Baray,Henri.Michel

[3] In array-oriented test generation, Bell numbers are used to count possible relationship patterns among indices, motivating an alias-coverage style criterion. Fabrice.Baray,Henri.Michel

[4] The TACAS source describes the Bell-number-based enumeration as having exponential complexity, while noting that this is not necessarily problematic in its search setting. Fabrice.Baray,Henri.Michel

[5] The arXiv paper on q-wise independence tails states that it provides hard bounds in terms of Bell numbers. Lower bounds on q-wise independence tails and applications to min-entropy condensers