Digital Library of Mathematical Functions
About the Project
NIST
26 Combinatorial AnalysisProperties

§26.18 Counting Techniques

Let A1,A2,,An be subsets of a set S that are not necessarily disjoint. Then the number of elements in the set S\(A1A2An) is

26.18.1 |S\(A1A2An)|=|S|+t=1n(-1)t1j1<j2<<jtn|Aj1Aj2Ajt|.

Example 1

The number of positive integers N that are not divisible by any of the primes p1,p2,,pn27.2(i)) is

26.18.2 N+t=1n(-1)t1j1<j2<<jtnNpj1pj2pjt.

Example 2

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

26.18.3 n!+t=1n(-1)trt(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 kn+t=1n(-1)t(kt)(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).