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 distinct or identical, the boxes may be distinct or identical, 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)

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, Partition, 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