26 Combinatorial Analysis Properties 26.16 Multiset Permutations 26.18 Counting Techniques

§26.17 The Twelvefold Way

ⓘ

Keywords:: permutations, twelvefold way
Permalink:: http://dlmf.nist.gov/26.17
See also:: Annotations for Ch.26

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 $S\left(n,k\right)$ and $p_{k}\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}$	${\left(k-n+1\right)_{n}}$	$k!S\left(n,k\right)$
unlabeled	labeled	$\dbinom{k+n-1}{n}$	$\dbinom{k}{n}$	$\dbinom{n-1}{n-k}$
labeled	unlabeled	$\begin{array}[]{c}S\left(n,1\right)+S\left(n,2\right)\\ +\cdots+S\left(n,k\right)\end{array}$	$\begin{cases}1&n\leq k\\ 0&n>k\end{cases}$	$S\left(n,k\right)$
unlabeled	unlabeled	$p_{k}\left(n\right)$	$\begin{cases}1&n\leq k\\ 0&n>k\end{cases}$	$p_{k}\left(n\right)-p_{k-1}\left(n\right)$

ⓘ

Symbols:: ${\left(\NVar{a}\right)_{\NVar{n}}}$ : Pochhammer’s symbol (or shifted factorial), $S\left(\NVar{n},\NVar{k}\right)$ : Stirling number of the second kind, $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$ : binomial coefficient, $!$ : factorial (as in $n!$ ), $p_{\NVar{k}}\left(\NVar{n}\right)$ : total number of partitions of $n$ into at most $k$ parts, $k$ : nonnegative integer, $n$ : nonnegative integer, $f$ : mapping and $N$ : set
Referenced by:: §26.17, §26.17, §26.18
Permalink:: http://dlmf.nist.gov/26.17.T1
See also:: Annotations for §26.17 and Ch.26

26.16 Multiset Permutations 26.18 Counting Techniques

NIST

Site Privacy Accessibility Privacy Program Copyrights Vulnerability Disclosure No Fear Act Policy FOIA Environmental Policy Scientific Integrity Information Quality Standards Commerce.gov Science.gov USA.gov