Inclusion-exclusion principle problems

Question

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:

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

2. 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:

1. 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?
2. 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

Answer 1

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.

Answer 2

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 $8\times T_{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 $8\times T_{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 $8\times T_{n-3}$.

Therefore you have the relationship $T_{n}=8\times(T_{n-1}+T_{n-2}+T_{n-3})$. You can find the values for $T_{1}, T_{2}$a nd $T_{3}$ (which will be $9$, $9\times9=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.