3. a) How many permutations of the set $\{1,2,3, \ldots, n\}$ are there in which the numbers 1 and 2 are not adjacent?

b) How many permutations of the set $\{1,2,3, \ldots, n\}$ are there in which no two elements of the set $\{1,2,3\}$ are adjacent?
3. a) From the number of all permutations of the set $\{1,2,3, \ldots, n\}$, i.e., $n$!, we need to subtract the number of permutations in which 1 and 2 appear together. The number of permutations in which $\overline{12}$ appears is $(n-1)$!, since $\overline{12}$ is considered as one element. Similarly, the number of permutations in which $\overline{21}$ appears is also $(n-1)$!. Therefore, the number of all permutations in which $\overline{12}$ or $\overline{21}$ does not appear is equal to

$$
n!-2 \cdot(n-1)!
$$

10 points

b) The set A of all permutations of the set $\{1,2,3, \ldots, n\}$ has $n$! elements. Let B, C, D be the sets of permutations in which 1 and 2, 1 and 3, 2 and 3 are adjacent, respectively. According to the proof in a), each of the sets B, C, D has $2 \cdot(n-1)!$. Each permutation in which $\overline{a b c}$ appears, where $\{a, b, c\}=\{1,2,3\}$, was counted twice, once in the set where $\overline{a b}$ appears and once in the set where $\overline{b c}$ appears. The number of permutations in which a given $\overline{a b c}$ appears is $(n-2)$!. Since the number of permutations of the set $\{1,2,3\}$ is 6, the number of all permutations in which some two of the numbers 1, 2, 3 are adjacent is $6 \cdot(n-1)!-6 \cdot(n-2)!$. Therefore, the number of all permutations in which no two of the numbers 1, 2, 3 are adjacent is equal to

$$
n!-6 \cdot(n-1)!+6 \cdot(n-2)!
$$