7
$\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<...

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

$$\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

  • 3
    +1 for showing your work and where you are having problems.2012-08-05
  • 0
    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!2012-08-06
  • 0
    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..2012-08-06
  • 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