§26.18 Counting Techniques

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

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:: $\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

¶ 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}<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 x\right\rfloor$ : floor of $x$ , $j$ : nonnegative integer, $n$ : nonnegative integer, $p_{n}$ : primes and $N$ : number
Permalink:: http://dlmf.nist.gov/26.18.E2
Encodings:: TeX, pMML, png

¶ 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:: $!$ : $n!$ : factorial, $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

¶ 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}.$

Symbols:: $\binom{m}{n}$ : binomial coefficient, $k$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.18.E4
Encodings:: TeX, pMML, png

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