Math Problems Vault

Problem 8.21

Consider a set of $N$ objects. Let $N_\alpha$ be the number of those objects that have a certain property $\alpha$ , $N_\beta$ the number of those that have the property $\beta$ , , $N_\kappa$ and $N_\lambda$ the number of those that have the property $\kappa$ and $\lambda$ respectively. Similarly let $N_{\alpha \beta }, N_{\alpha \gamma }, \ldots , N_{\alpha \beta \gamma }, \ldots , N_{\alpha \beta \gamma \ldots \kappa \lambda }$ denote the number of those objects that have simultaneously the properties $\alpha$ and $\beta$ , $\alpha$ and $\gamma$ , , $\alpha$ , $\beta$ and $\gamma$ , , $\alpha , \beta , \gamma , \ldots , \kappa$ and $\lambda$ , respectively. Then the number $N_0$ of those objects that have none of the properties $\alpha , \beta , \gamma , \ldots , \kappa , \lambda$ , is given by

N - N_\alpha - N_\beta - N_\gamma - \cdots - N_\kappa - N_\lambda

{}+ N_{\alpha \beta } + N_{\alpha \gamma } + \cdots \phantom{{}-{}} + N_{\kappa \lambda }

{}- N_{\alpha \beta \gamma } - \cdots

\cdots

\pm N_{\alpha \beta \gamma \ldots \kappa \lambda } .

?

Remark.

?

The principle stated by 21 deserves another proof which, although needing some introduction, exhibits more clearly the underlying basic set-theoretical (logical) ideas. We consider a finite or infinite set $U$ (the ``universe of discourse''). The characteristic function $A(x)$ of a subset $A$ of $U$ is a function of the variable element $x$ of $U$ : $A(x) = 1$ or $0$ according as $x$ does, or does not, belong to $A$ . The characteristic function of $U$ has the constant value 1 ( $U$ thus stands also for unity) and the characteristic function of the empty set (the null set) has the constant value 0. The characteristic functions of the subsets $A, B, C, \ldots$ will be denoted by $A(x), B(x), C(x), \ldots$ , respectively. If there is no danger of misunderstanding, we may simplify the notation by writing $A$ for $A(x)$ , etc., that is, by using the same symbol for a subset and its characteristic function. $A$ is a subset of $B$ if, and only if, $A(x) \leq B(x)$ for all values of $x$ , or, more simply, $A \leq B$ . If $U$ is a finite set, the number of elements of the subset $A$ is $\sum A(x)$ , where the summation is extended over all the elements of $U$ .

Problem 8.21.1

(1)(2)(3)

What is the characteristic function of

?

(1)

the complement of $A$ ,

(2)

the intersection of $A$ and $B$ ,

(3)

the union of $A$ and $B$ ?

Problem 8.21.2

Give another proof for Problem 21.

?

Problem 8.22

Assume that we have $n$ objects, $n>1$ . Let these all have property $\alpha$ with the exception of the first object, all property $\beta$ with the exception of the second object, , and all property $\lambda$ with the exception of the last $n$ th object. What do we obtain from Problem 21 applied to this case?

?

Problem 8.22.1

Prove Problem 189 of Part I by a combinatorial argument (cf. Problem 21 above and Problem 192 of Part I).

?

Problem 8.22.2

Prove Problem 208 of Part I by a combinatorial argument.

?

Problem 8.22.3

Prove that

\widetilde{S}_k^n = S_k^n - \binom {n}{1}S_{k-1}^{n-1} + \binom {n}{2}S_{k-2}^{n-2} - \cdots + (-1)^n S_{k-n}^0 .

?

Remark.

?

See the definitions in Part I, Chap. 4, § 3; if the condition $1 \leq k \leq n$ is not satisfied, $S_k^n$ must be interpreted as having the value 0.

Problem 8.23

How many of the $n!$ terms in the expansion of a determinant of the $n$ th order remain, if all the elements of the principal diagonal are set equal to 0?

?

Remark.

?

Observe 21: Let those terms have property $\alpha$ that contain $a_{11}$ as a factor, etc.

Problem 8.24

Let $a, b, c, \ldots , k, l$ be positive integers any two of which are relatively prime. How many numbers are there among the numbers $1, 2, 3, \ldots , n$ , that are not divisible by any of the numbers $a, b, c, \ldots , k, l$ ?

?

Remark.

?

Cf. Problem 12.

Problem 8.25

Let the different prime factors of the number $n$ be denoted by $p, q, r, \ldots$ . The number of numbers less than $n$ that have no common divisors different from 1 with $n$ is equal to

n\left(1-\frac1p\right)\left(1-\frac1q\right)\left(1-\frac1r\right)\cdots .

?

Remark.

?

This number is generally denoted by $\varphi (n)$ (the Euler function). We set $\varphi (1)=1$ ; $\varphi (n)$ is thus the number of those numbers $\leq n$ that are relatively prime to $n$ . This is the case for $n \geq 1$ , since 1 has no common divisors different from 1 with itself.

Problem 8.26

Assume that we have any $N$ objects, that, as in 21, can have the properties $\alpha , \beta , \ldots , \kappa , \lambda$ . Associate with each individual object a value. Denote by $W_\alpha$ the total value (the sum of the values) of those objects that have property $\alpha$ , $W_\beta$ the total value of those with property $\beta$ , etc. Similarly let $W_{\alpha \beta }, W_{\alpha \gamma }, \ldots , W_{\alpha \beta \gamma }, \ldots , W_{\alpha \beta \gamma \ldots \kappa \lambda }$ denote the total value of those objects that have simultaneously the properties $\alpha$ and $\beta$ , $\alpha$ and $\gamma$ , , $\alpha , \beta$ and $\gamma$ , , $\alpha , \beta , \gamma , \ldots , \kappa$ and $\lambda$ , respectively. If $W$ is the total value of all the objects, then the total value of those objects that have none of the properties $\alpha , \beta , \ldots , \kappa , \lambda$ is equal to

W - W_\alpha - W_\beta - W_\gamma - \cdots - W_\kappa - W_\lambda

{}+ W_{\alpha \beta } + W_{\alpha \gamma } + \cdots \phantom{{}-{}} + W_{\kappa \lambda }

{}- W_{\alpha \beta \gamma } - \cdots

\cdots

\pm W_{\alpha \beta \gamma \ldots \kappa \lambda } .

?

Problem 8.27

Let $n>1$ ; and $r_1, r_2, \ldots , r_{\varphi (n)}$ be the numbers less than $n$ that have no common divisors different from 1 with $n$ . We then have

r_1^2+r_2^2+\cdots +r_{\varphi (n)}^2 = \frac{\varphi (n)}{3}\left(n^2 + \frac{(-1)^\nu }{2}pqr\cdots \right) ,

where $p,q,r,\ldots$ are the different prime factors of $n$ , and $\nu$ is their number.

?

Problem 8.27.1

The number $N_0$ sought in 21 is

\leq N

\geq N - N_\alpha - N_\beta - N_\gamma - \cdots - N_\kappa - N_\lambda

\leq N - N_\alpha - N_\beta - N_\gamma - \cdots - N_\kappa - N_\lambda + N_{\alpha \beta } + N_{\alpha \gamma } + \cdots + N_{\kappa \lambda } .

\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots

?

Remark.

?

Briefly, in a somewhat extended meaning of the term (see the introduction to Problems 140 and 144 of Part I), the expression given in 21 ``envelops'' $N_0$ .

Problem 8.27.2

Let $l$ stand for the number of properties considered in 21. Define

S_0=N, \qquad S_1=N_\alpha +N_\beta +N_\gamma +\cdots +N_\kappa +N_\lambda , \qquad S_2=N_{\alpha \beta }+N_{\alpha \gamma }+\cdots +N_{\kappa \lambda }, \qquad \ldots , \qquad S_l=N_{\alpha \beta \gamma \ldots \kappa \lambda } ,

and let $s_k$ denote the number of those objects that possess precisely $k$ of the $l$ properties considered, $0 \leq k \leq l$ . It is easily seen (recognize the relation to binomial coefficients) that

S_0=s_0+s_1+s_2+s_3+\cdots +s_l ,

S_1=\phantom{s_0+{}}s_1+2s_2+3s_3+\cdots +ls_l ,

S_2=\phantom{s_0+s_1+{}}s_2+3s_3+\cdots +\binom {l}{2}s_l ,

S_3=\phantom{s_0+s_1+s_2+{}}s_3+\cdots +\binom {l}{3}s_l ,

\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots

S_l=\phantom{s_0+s_1+s_2+s_3+\cdots +{}}s_l .

?