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
Best Answer
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.