Combinatorial explosion

In mathematics, a combinatorial explosion describes the effect of functions that grow very rapidly as a result of combinatorial considerations.

Examples of such functions include the factorial function and related functions. Pathological examples of combinatorial explosion include functions such as the Ackermann function.

Combinatorial explosion can occur in computing environments in a way analogous to communications and multi-dimensional space. Imagine a simple system with only one variable, a boolean called A. The system has two possible states, A = true or A = false. Adding another boolean variable B will give the system four possible states, A = true and B = true, A = true and B = false, A = false and B = true, A = false and B = false. A system with n booleans has 2ⁿ possible states, while a system of n variables each with Z allowed values (rather than just the 2 (true and false) of booleans) will have Zⁿ possible states.

The possible states can be thought of as the leaf nodes of a tree of height n, where each node has Z children. This rapid increase of leaf nodes can be useful in areas like searching, since many results can be accessed without having to descend very far. It can also be a hindrance when manipulating such structures.

A class hierarchy in an object-oriented language can be thought of as a tree, with different types of object inheriting from their parents. If different classes need to be combined, such as in a comparison (like A < B) then the number of possible combinations which may occur explodes. If each type of comparison needs to be programmed then this soon becomes intractable for even small numbers of classes. Multiple inheritance can solve this, by allowing subclasses to have multiple parents, and thus a few parent classes can be considered rather than every child, without disrupting any existing hierarchy.

...
Wikipedia