Permutation checking and Inclusion-Exclusion

• February 2nd 2008, 11:55 AM
Permutation checking and Inclusion-Exclusion
Firstly i was wondering whether someone could check if ive done this right...

Suppose f is the permutation (1, 2, 3, 4)(5, 6, 7)(8, 9)(10) of the set X = {1, 2, . . . , 10} and let g be the permutation (1, 4)(2, 7)(3, 10)(5, 9)(6, 8)
of X. Calculate f o g and g o f.

I got f o g = (1)(2 3 4 5 7 8 10)(6 9)
and g o f = (1 2 3 6 7 9 10)(4)(5 8)

Now the question i have no idea about...

Let S be the set of 3-digit decimal integers {000, 001, 002, . . . , 999}. Use Inclusion-Exclusion to find how many such integers contain at least one 7. (Hint. Let S1 be the subset of S consisting of elements with first digit equal to 7, etc.)

I have no idea how to use the inclusion-exclusion principle so can anyone help with that please?

cheers
• February 2nd 2008, 12:07 PM
Plato
If $S_i \,,\,i = 1,2,3$ stand for a three digit integer with a 7 in the i-th place.
Then $\left( {S_1 \cap S_3 } \right)$ means numbers with 7’s in the first and third place.
What you want is:
$\left| {S_1 \cup S_2 \cup S_3 } \right| = \left| {S_1 } \right| + \left| {S_2 } \right| + \left| {S_3 } \right| - \left| {S_1 \cap S_2 } \right| - \left| {S_1 \cap S_3 } \right| - \left| {S_2 \cap S_3 } \right| + \left| {S_1 \cap S_2 \cap S_3 } \right|$.