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
 A: For the first problem, you did not quite use inclusion/exclusion. Let us count the number that contain the substring $121$. From your $6\cdot 9^5$ we need to subtract the sequences that have been double-counted by $6\cdot 9^5$.
How many sequences are there that have two or more substrings of shape $121$? It is trickier than it looks. We have counted $121121xy$ twice, but we also have counted $12121xyz$ twice. 
After you do the subtraction, it will turn out you have subtracted too much, for example the sequences $1212121x$, so they will have to be added back.
A: I think I would solve the first problem by means of recursive relations. 
Let's say you have a n-digit sequence containing integers 1-9 only, and you want to find T(n), which we define as the number of such sequences that don't contain a subsequence "121". 
What I would do is consider splitting into the following cases: 
Case 1: If T(n) starts with anything except 1 then you have effectively 8T(n-1) since there are 8 choices for the first number and T(n-1) choices for the (n-1) term sequence. 
Case 2: If T(n) starts with 1 then you look at the second number. If it starts with anything except 2 then you have 8T(n-2) for similar reasons. 
Case 3: If T(n) starts with "12" then the third number can't be "1" or it would violate the relationship so you have 8T(n-3). 
Therefore you have the relationship T(n)=8[T(n-1)+T(n-2)+T(n-3)]. You can find the values for T(1), T(2) and T(3) (which will be 9, 9x9=81, and 9^3-1=728) and solve for T(8). :)
Hope this helped, and please do tell me if I made a mistake anywhere. 
A: 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.
