Lesson test: Inclusion and exclusion

1.[1p]
How many integers from $1$ to $1000$ are divisible by $3$ or by $7$ ?

CorrectNot quite: 428

2.[3p]
How many integers from $1$ to $1000$ are divisible by none of $2$ , $3$ , $5$ and $7$ ?

CorrectNot quite: 228

3.[1p]
An element lies in exactly four of the sets $A_{1}, \dots, A_{n}$ . How many times is it counted in $S_{2}$ , the sum of the sizes of all pairwise intersections?

CorrectNot quite: 6

4.[2p]
How many onto functions are there from a set of six elements to a set of three elements?

CorrectNot quite: 540

5.[2p]
Seven letters are put into seven addressed envelopes so that no letter is in its own envelope. In how many ways can this be done?

CorrectNot quite: 1854

6.[2p]
Six guests get their hats back at random. What is the probability that nobody gets their own hat? Give it to four decimal places.

CorrectNot quite: 0.3681

7.[2p]
Compute $φ (504)$ , where $504 = 2^{3} \times 3^{2} \times 7$ .

CorrectNot quite: 144

8.[3p]
Match each count to the sets $A_{i}$ whose union the sieve removes.

Onto functions
Derangements
Euler's totient of $n$

the permutations that fix a given element
the integers up to $n$ divisible by a given prime divisor of $n$
the functions that miss a given element of the target

Show the answer

Onto functions: the functions that miss a given element of the target Derangements: the permutations that fix a given element Euler's totient of $n$ : the integers up to $n$ divisible by a given prime divisor of $n$

9.[3p]
Which of these statements are correct?

Select all that apply

The proof of the general formula uses the fact that the alternating sum of a row of Pascal's triangle is zero

Correct

For every $n \geq 1$ , $D_{n}$ is $n! / e$ rounded to the nearest integer

Correct

$φ (n) = n (1 - \frac{1}{p_{1}}) \dots (1 - \frac{1}{p_{r}})$ , where $p_{1}, \dots, p_{r}$ are the distinct primes dividing $n$

Correct

The integers divisible by both $4$ and $6$ are the multiples of $24$

The answer is: The proof of the general formula uses the fact that the alternating sum of a row of Pascal's triangle is zero, For every $n \ge 1$, $D_n$ is $n!/e$ rounded to the nearest integer, $\varphi(n) = n\left(1 - \frac{1}{p_1}\right)\cdots\left(1 - \frac{1}{p_r}\right)$, where $p_1, \ldots, p_r$ are the distinct primes dividing $n$

As the number of guests grows, the probability that nobody gets their own hat tends to $0$

The answer is: The proof of the general formula uses the fact that the alternating sum of a row of Pascal's triangle is zero, For every $n \ge 1$, $D_n$ is $n!/e$ rounded to the nearest integer, $\varphi(n) = n\left(1 - \frac{1}{p_1}\right)\cdots\left(1 - \frac{1}{p_r}\right)$, where $p_1, \ldots, p_r$ are the distinct primes dividing $n$

The number of onto functions from a $k$ element set to an $n$ element set is $n^{k} - n (n - 1)^{k}$

The answer is: The proof of the general formula uses the fact that the alternating sum of a row of Pascal's triangle is zero, For every $n \ge 1$, $D_n$ is $n!/e$ rounded to the nearest integer, $\varphi(n) = n\left(1 - \frac{1}{p_1}\right)\cdots\left(1 - \frac{1}{p_r}\right)$, where $p_1, \ldots, p_r$ are the distinct primes dividing $n$

1.[1p] How many integers from 1 to 1000 are divisible by 3 or by 7?

2.[3p] How many integers from 1 to 1000 are divisible by none of 2, 3, 5 and 7?

3.[1p] An element lies in exactly four of the sets A1,…,An. How many times is it counted in S2, the sum of the sizes of all pairwise intersections?

4.[2p] How many onto functions are there from a set of six elements to a set of three elements?

5.[2p] Seven letters are put into seven addressed envelopes so that no letter is in its own envelope. In how many ways can this be done?

6.[2p] Six guests get their hats back at random. What is the probability that nobody gets their own hat? Give it to four decimal places.

7.[2p] Compute φ(504), where 504=23×32×7.

8.[3p] Match each count to the sets Ai whose union the sieve removes.

9.[3p] Which of these statements are correct?

1.[1p]
How many integers from $1$ to $1000$ are divisible by $3$ or by $7$ ?

2.[3p]
How many integers from $1$ to $1000$ are divisible by none of $2$ , $3$ , $5$ and $7$ ?

3.[1p]
An element lies in exactly four of the sets $A_{1}, \dots, A_{n}$ . How many times is it counted in $S_{2}$ , the sum of the sizes of all pairwise intersections?

4.[2p]
How many onto functions are there from a set of six elements to a set of three elements?

5.[2p]
Seven letters are put into seven addressed envelopes so that no letter is in its own envelope. In how many ways can this be done?

6.[2p]
Six guests get their hats back at random. What is the probability that nobody gets their own hat? Give it to four decimal places.

7.[2p]
Compute $φ (504)$ , where $504 = 2^{3} \times 3^{2} \times 7$ .

8.[3p]
Match each count to the sets $A_{i}$ whose union the sieve removes.

9.[3p]
Which of these statements are correct?