Inclusion-exclusion principle problems I've got huge problems with inclusion-exclusion principle. I know the formula, but always don't know how to use it, how to denote all the things. Hope it will pass when I do some excercises. I stuck with these two:


*

*How many are $8$-digit numbers (without $0$ at any position) that don't have subsequence $121$?


*Find the number of permutations of the set: $\left\{1,2,3,4,5,6,7\right\}$, that don't have four consecutive elements in ascending order.

And here are my propositions for solutions:

*

*On the whole, there are $9^8$ numbers this kind. Let think about numbers that have at least one subsequence: $121$. We choose place for first $1$ of this subsequence. There are six possibilities. After choosing place for $1$ we set $21$ after this digit, and the rest of digits are with no restrictions. So we have $6\cdot 9^5$ numbers with at least one subsequence $121$, so numbers without this subsequence are $9^8-6\cdot 9^5$. Is that correct?

*Let $X$ be a set of all permutations of a given set. $|X|=7!$. Let $A_i$ be a set of permutations that have numbers: $i, \ i+1, \ i+2, \ i+3$ consecutive in ascending order. In other words they have subsequence of this form. Hence $|A_i|=4\cdot 3!$, because we choose one of $4$ places for $i$ and the rest $3$ of digits are with no restrictions. Another observation is that for $i_1<...<i_k$ we have $\displaystyle |A_{i_1}\cap ... \cap A_{i_k} |=(3-i_k+i_1) \cdot (3-i_k+i_1)!$ which is that simple only because the set is $\left\{1,2,3,4,5,6,7 \right\}$. $A_{i_1}\cap ... \cap A_{i_k}$ is a set of permutations that have subsequence: $i_1,...,i_k,...,i_{k+3}$ so we choose place for $i_1$, set this subsequence starting from this place and permuting the rest of digits.

By the way I'm wondering if it was possible to solve this problem in general, I mean if the set was of the form $\left\{1,..,n \right\}$ for any natural number $n$?
Back to problem. Now, what I want to count is, by exclusion-inclusion principle, this sum: $\displaystyle \sum_{k=0}^{4}(-1)^kS_k$, where $\displaystyle S_k=\sum_{i_1<...<i_k\le 4}|A_{i_1}\cap ... \cap A_{i_k}|$, and $S_0=|X|$. The last observation: $A_{i_1}\cap ... \cap A_{i_k}=A_{i_1}\cap A_{i_k}$ (which again wouldn't be so easy in general unfortunately) and let's do it:
$$\sum_{k=0}^{4}(-1)^kS_k=|X|-|A_1|-|A_2|-|A_3|-|A_4|+|A_1\cap A_2|+|A_1\cap A_3|+|A_1\cap A_4|+|A_2\cap A_3|+|A_2\cap A_4|+|A_3\cap A_4|-|A_1\cap A_2\cap A_3|-|A_1\cap A_2\cap A_4|-|A_1\cap A_3\cap A_4|-|A_2\cap A_3\cap A_4|+|A_1\cap A_2\cap A_3\cap A_4|=\\=|X|-|A_1|-|A_2|-|A_3|-|A_4|+|A_1\cap A_2| + |A_2 \cap A_3|+|A_3\cap A_4|= \\ =7!-4\cdot 4\cdot 3! + 3\cdot 2\cdot 2!=4956$$
Is that correct? I'm afraid not :-( While waiting for answer I'll write a program that counts these permutations and check if it is a good answer.
I would be very grateful for any help, answering my questions, any advices and hints about this type of problems. I really want to finally understand this principle.
Regards

Here's my take on the second problem. It doesn't really need the Inclusion-Exclusion Principle (here one only set is included in the other). I can't see how to choose the sets that would lead to a nice and simple solution based on it, but I too would be interested to see it.
There are $7!$ permutations of the set $\{1, 2, 3, 4, 5, 6, 7\}$. We need to subtract from it the number of permutations that contain 4 consecutive elements in ascending order. Let's count it in 3 steps:


*

*How many sequences of 4 numbers from the given set are in ascending order, like $(2, 4, 5, 7)$? This is for instance how you would select this sequence:


$$1\ 2\ 3\ 4\ 5\ 6\ 7\\
0\ 1\ 0\ 1\ 1\ 0\ 1$$
So we just have to choose four numbers from left to right (1's), ignoring the others (0's). Every 7-bits binary string containing exactly 4 1's leads to a distinct ascending sequence. This gives us $\binom{7}{4}$ such sequences.


*

*For each of these sequences, how many spots are there to place it (as consecutive numbers) in a permutation of 7 numbers? Just 4:


$$2\ 4\ 5\ 7\ X\ X\ X,\quad X\ 2\ 4\ 5\ 7\ X\ X,\quad X\ X\ 2\ 4\ 5\ 7\ X,\quad X\ X\ X\ 2\ 4\ 5\ 7$$


*

*For each of these association sequence/spot, how many arrangements of the last 3 numbers to give us a full unique permutation? Of course: $3!$


Given all that, the final answer would be:
$$7! - \binom{7}{4}\cdot4\cdot3! = 4200$$
Let me know if I over-counted (or under-counted) somewhere.
