# §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)!.$

# 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}\binom{k}{t}(k-t)^{n}.$

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