# 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<... 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<..., 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. Aug 5, 2012 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! Aug 6, 2012 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, 2012 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, 2012 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$". Aug 5, 2012 at 16:13
• @MarcvanLeeuwen: Yes, it is a messy inclusion/exclusion, we can have $3$. Aug 5, 2012 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, 2012 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.

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.

• I think you're over-counting. For example, 1234xxx and xxx4567. Oct 17, 2021 at 7:02
• Don't forget the sequences with length $5$, $6$, and $7$ Dec 2, 2021 at 14:19