26 Combinatorial Analysis Properties 26.17 The Twelvefold Way 26.19 Mathematical Applications

§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 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, : nonnegative integer, : nonnegative integer, $A_{k}$ : subsets and : 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 , : nonnegative integer, : nonnegative integer, $p_{n}$ : primes and : 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 nonattacking rooks on an $n\times n$ chessboard that avoid the squares in a specified subset is

26.18.3 $n!+\sum_{{t=1}}^{n}(-1)^{t}r_{t}(B)(n-t)!.$

Symbols:: : : factorial, : nonnegative integer, $r_{j}(B)$ : number of rook positions and : subset
Permalink:: http://dlmf.nist.gov/26.18.E3
Encodings:: TeX, pMML, png

¶ Example 3

The number of ways of placing labeled objects into 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, : nonnegative integer and : 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 are labeled, elements of are labeled, and 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).

© 2010–2013 NIST / Privacy Policy / Disclaimer / Feedback; Version 1.0.6; Release date 2013-05-06 Math-Image version (See MathML) . A Printed Companionis available. 26.17 The Twelvefold Way 26.19 Mathematical Applications