TOPICS
Search

Twelvefold Way


The twelvefold way is a classification of twelve elementary counting problems involving the distribution of n balls into g boxes. The balls may be distinguishable or indistinguishable, the boxes may likewise be distinguishable or indistinguishable, and the occupancy of the boxes may be unrestricted, at most one ball per box, or at least one ball per box.

According to Stanley (1999, p. 41), the idea of the twelvefold way is due to G.-C. Rota's lectures, and the terminology to Joel Spencer.

With S(n,k) denoting a Stirling number of the second kind, (g)_n a falling factorial, p_(<=g)(n) the number of partitions of n into at most g parts, and p_g(n) the number of partitions of n into exactly g parts, the twelve cases are as follows. In the "at most one" column, the entries are understood to be 0 when n>g.

Balls and boxesUnrestrictedAt most oneAt least one
distinct balls, distinct boxesg^n(g)_ng!S(n,g)
identical balls, distinct boxes(n+g-1; n)(g; n)(n-1; g-1)
distinct balls, identical boxessum_(k=0)^(g)S(n,k)1S(n,g)
identical balls, identical boxesp_(<=g)(n)1p_g(n)

The g^n unrestricted assignments of distinct balls to distinct boxes form the sample space for the classical occupancy problem when the box choices are independent and identically distributed according to the discrete uniform distribution. This is the basic probabilistic case of the broader occupancy problem.

For example, distributing n distinct balls among an unrestricted number of identical boxes gives the Bell number B_n. Distributing them among exactly g nonempty identical boxes gives S(n,g). The same classification also occurs in physical counting problems when balls and boxes are interpreted as particles and available states, respectively (Akhanjee 2026).


See also

Bell Number, Classical Occupancy Problem, Discrete Uniform Distribution, Distinguishable Objects, Independent and Identically Distributed, Indistinguishable Objects, Nonempty Set, Occupancy Problem, Partition, Sample Space, Set Partition, Stirling Number of the Second Kind

Explore with Wolfram|Alpha

References

Akhanjee, S. "The Statistical Mechanics of Indistinguishable Energy States and the Glass Transition." 5 Mar 2026. https://arxiv.org/abs/2603.04823.Stanley, R. P. "The Twelvefold Way." §1.4 in Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, pp. 31-41, 1999.

Cite this as:

Weisstein, Eric W. "Twelvefold Way." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TwelvefoldWay.html

Subject classifications