# 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:

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

-
+1 for showing your work and where you are having problems. – Ross Millikan Aug 5 '12 at 16:08
The 2nd problem seems ambiguous to me. The permutation 2,3,5,7,1,4,6 - is it forbidden? The entries 2,3,5,7 are consecutive entries, and they are in ascending order. What about 1,7,2,6,3,5,4? The numbers 1,2,3,4 are consecutive numbers, and they appear in ascending order. Or is it only things like 5,1,2,3,4,7,6 that are forbidden, where consecutive numbers appear in consecutive positions, in ascending order? Hard to count, when I'm not sure what I'm counting! – Gerry Myerson Aug 6 '12 at 0:09
I wrote this programm to check if my outcome is correct. It gave result $4962$, while my result is $4956$ and now I don't know if my method is completely wrong, or I just missed one detail.. – ray Aug 6 '12 at 11:35
@GerryMyerson, now I see I didn't understand the problem. I understood that forbidden are only permutations like: 5,1,2,3,4,7,6. But now I see that forbidden are 2,3,5,7,1,4,6 and 5,1,2,3,4,7,6 because they have four consecutive entries in ascending order. It seems very hard.. – ray Aug 6 '12 at 11:49

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.

-
$12121214$ has more than two substrings "$121$". – Marc van Leeuwen Aug 5 '12 at 16:13
@MarcvanLeeuwen: Yes, it is a messy inclusion/exclusion, we can have $3$. – André Nicolas Aug 5 '12 at 16:24
Then I'm totally lost. I don't know how to find all sequences that I counted twice (or more..). Is it possible to define all the sets, as I tried to do in the second problem, and as simply as possible (but not simpler) use inclusion/exclusion? I'm wondersing if this is correct: denote $A_i$ - set of all sequences that have $\ge i$ substrings $121$, then $|A_1|=6\cdot 9^5, \ |A_2|=4\cdot 9^3 + 6 \cdot 9^2 , \ |A_3|=18+2$ and result is: $9^8-|A_1|+|A_2|-|A_3|$. But, honestly, I simply don't feel it, I think I'm still counting twice some sequences :-( – ray Aug 6 '12 at 12:24

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.

-