26 Combinatorial Analysis Properties 26.17 The Twelvefold Way 26.19 Mathematical Applications

§26.18 Counting Techniques

ⓘ

Keywords:: counting techniques
Notes:: See Riordan (1958, pp. 50–65).
Referenced by:: §26.17
Permalink:: http://dlmf.nist.gov/26.18
See also:: Annotations for Ch.26

Let $A_{1},A_{2},\ldots,A_{n}$ be subsets of a set $S$ that are not necessarily disjoint. Then the number of elements in the set $S\setminus(A_{1}\cup A_{2}\cup\cdots\cup A_{n})$ is

26.18.1		$\left\|S\setminus(A_{1}\cup A_{2}\cup\cdots\cup A_{n})\right\|=\left\|S\right\|+% \sum_{t=1}^{n}(-1)^{t}\sum_{1\leq j_{1}<j_{2}<\cdots<j_{t}\leq n}\left\|A_{j_{1% }}\cap A_{j_{2}}\cap\cdots\cap A_{j_{t}}\right\|.$
ⓘ Symbols: $\left\|\NVar{A}\right\|$ : number of elements of a finite set $A$ , $\cap$ : intersection, $\setminus$ : set subtraction, $\cup$ : union, $j$ : nonnegative integer, $n$ : nonnegative integer, $A_{k}$ : subsets and $S$ : set Permalink: http://dlmf.nist.gov/26.18.E1 Encodings: TeX, pMML, png See also: Annotations for §26.18 and Ch.26

Example 1

ⓘ

See also:: Annotations for §26.18 and Ch.26

The number of positive integers $\leq N$ that are not divisible by any of the primes $p_{1},p_{2},\ldots,p_{n}$ (§27.2(i)) is

26.18.2		$N+\sum_{t=1}^{n}(-1)^{t}\sum_{1\leq j_{1}<j_{2}<\cdots<j_{t}\leq n}\left% \lfloor\frac{N}{p_{j_{1}}p_{j_{2}}\cdots p_{j_{t}}}\right\rfloor.$
ⓘ Symbols: $\left\lfloor\NVar{x}\right\rfloor$ : floor of $x$ , $j$ : nonnegative integer, $n$ : nonnegative integer, $N$ : set and $p_{n}$ : primes Permalink: http://dlmf.nist.gov/26.18.E2 Encodings: TeX, pMML, png See also: Annotations for §26.18, §26.18 and Ch.26

Example 2

ⓘ

See also:: Annotations for §26.18 and Ch.26

With the notation of §26.15, the number of placements of $n$ nonattacking rooks on an $n\times n$ chessboard that avoid the squares in a specified subset $B$ is

26.18.3		$n!+\sum_{t=1}^{n}(-1)^{t}r_{t}(B)(n-t)!.$
ⓘ Symbols: $!$ : factorial (as in $n!$ ), $n$ : nonnegative integer, $r_{j}(B)$ : number of rook positions and $B$ : subset Permalink: http://dlmf.nist.gov/26.18.E3 Encodings: TeX, pMML, png See also: Annotations for §26.18, §26.18 and Ch.26

Example 3

ⓘ

See also:: Annotations for §26.18 and Ch.26

The number of ways of placing $n$ labeled objects into $k$ labeled boxes so that at least one object is in each box is

26.18.4		$k^{n}+\sum_{t=1}^{n}(-1)^{t}\genfrac{(}{)}{0.0pt}{}{k}{t}(k-t)^{n}.$
ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$ : binomial coefficient, $k$ : nonnegative integer and $n$ : nonnegative integer Permalink: http://dlmf.nist.gov/26.18.E4 Encodings: TeX, pMML, png See also: Annotations for §26.18, §26.18 and Ch.26

Note that this is also one of the counting problems for which a formula is given in Table 26.17.1. Elements of $N$ are labeled, elements of $K$ are labeled, and $f$ is onto.

For further examples in the use of generating functions, see Stanley (1997, 1999) and Wilf (1994). See also Pólya et al. (1983).

26.17 The Twelvefold Way 26.19 Mathematical Applications

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