Digital Library of Mathematical Functions
About the Project
NIST
26 Combinatorial AnalysisProperties

§26.17 The Twelvefold Way

The twelvefold way gives the number of mappings f from set N of n objects to set K of k objects (putting balls from set N into boxes in set K). See Table 26.17.1. In this table \left(k\right)_{{n}} is Pochhammer’s symbol, and \mathop{S\/}\nolimits\!\left(n,k\right) and \mathop{p_{{k}}\/}\nolimits\!\left(n\right) are defined in §§26.8(i) and 26.9(i).

Table 26.17.1 is reproduced (in modified form) from Stanley (1997, p. 33). See also Example 3 in §26.18.

Table 26.17.1: The twelvefold way.
elements of N elements of K f unrestricted f one-to-one f onto
labeled labeled k^{n} (k-n+1)_{n} k!\mathop{S\/}\nolimits\!\left(n,k\right)
unlabeled labeled \dbinom{k+n-1}{n} \dbinom{k}{n} \dbinom{n-1}{n-k}
labeled unlabeled \begin{array}[]{c}\mathop{S\/}\nolimits\!\left(n,1\right)+\mathop{S\/}%
\nolimits\!\left(n,2\right)\\
+\cdots+\mathop{S\/}\nolimits\!\left(n,k\right)\end{array} \begin{cases}1&n\leq k\\
0&n>k\end{cases} \mathop{S\/}\nolimits\!\left(n,k\right)
unlabeled unlabeled \mathop{p_{{k}}\/}\nolimits\!\left(n\right) \begin{cases}1&n\leq k\\
0&n>k\end{cases} \mathop{p_{{k}}\/}\nolimits\!\left(n\right)-\mathop{p_{{k-1}}\/}\nolimits\!%
\left(n\right)