# §26.18 Counting Techniques

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}

## Example 1

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}

## Example 2

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 26

## Example 3

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 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).