9
$\begingroup$

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

  • 0
    @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..2012-08-06

3 Answers 3

3

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.

  • 0
    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 :-(2012-08-06
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 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.

0

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.