Discrete Mathematics: Exercises part 1.
Inclusion-exclusion methods
How many positive integers less than 10,000 are not the second or higher power of an integer?
In how many ways can seven different jobs be assigned to four different employees so that each employee is as- signed at least one job and the most difficult job is as- signed to the best employee?
\[\frac{4! \mathcal{S}_7^{(4)}}{4} \]Recurrence of derangements
Use a combinatorial argument to show that the sequence \(\left\{D_n\right\}\), where \(D_n\) denotes the number of derangements of \(n\) objects, satisfies the recurrence relation
\[\begin{equation*} D_n=(n-1)\left(D_{n-1}+D_{n-2}\right) \end{equation*} \]Suppose that \(p\) and \(q\) are distinct primes. Use the principle of inclusion-exclusion to find \(\phi(p q)\), the number of positive integers not exceeding \(p q\) that are relatively prime to \(p q\).
Solution Suppose we have already determined all \(D_i\) for \(i \leq n-1\). Consider the \(n\)th element.
- If we already have a derangement of the first \(n-1\) elements, we can obtain a derangement of all \(n\) elements by adding the \(n\)th element and exchanging it with any element with index from \(i\) to \(n-1\).
- If we already have a derangement of the first \(n-1\) elements, except for one element that is in its correct position, we can obtain a derangement of all \(n\) elements by exchanging the correctly placed element with the \(n\)th element. There are \(n-1\) ways to choose the correctly placed element.
Therefore, we have \(D_n=(n-1)\left(D_{n-1}+D_{n-2}\right)\) ways of obtaining a derangement of all \(n\) elements.
23. Use the principle of inclusion-exclusion to derive a formula for \(\phi(n)\) when the prime factorization of \(n\) is
\[\begin{equation*} n=p_1^{a_1} p_2^{a_2} \cdots p_m^{a_m} . \end{equation*} \]*24. Show that if \(n\) is a positive integer, then
\[\begin{equation*} \begin{aligned} n !=C(n, 0) D_n & +C(n, 1) D_{n-1}+\cdots+C(n, n-1) D_1+C(n, n) D_0, \end{aligned} \end{equation*} \]where \(D_k\) is the number of derangements of \(k\) objects.
? Inclusive or or exclusive or ?
"Either A or B" most precisely means, in symbolic logic terms, "A
XORB", whereXORis the "exclusive or". So yes, it means "A or B but not both". It isn't always actually used with full precision, though, so, as usual, context has to be taken into account. If somebody says, "select either A or B", for example, they definitely mean that you should not select both. If they say "if either A or B is true", though, they probably mean a non-exclusiveOR, and the condition is still true if both A and B are true. Unfortunately, if there's a generally reliable rule for telling which is meant, I'm failing to think of what it would be.Without the "either", the presumption would be more toward "A
ORB", whereORallows the case where both are true. Which is why computer geeks and propositional calculus nerds will, when asked "do you want to go to lunch now or later?", answer "yes". (Illustrating that the "either" part is implied by context as often as it's cancelled by context.)
8.1.15
a) Find a recurrence relation for the number of ternary strings of length \(n\) that do not contain two consecutive 0s or two consecutive \(1 \mathrm{~s}\).
b) What are the initial conditions?
c) How many ternary strings of length six do not contain two consecutive 0 s or two consecutive 1s?
Solution 0 a) A direct solution is
\[a_n = a_{n-1} + \sum_{0\leq i \leq n-2} a_i \]then
\[a_n = 2a_{n-1} + a_{n-2}, \quad n \geq 3. \](Is there an direct argument for the recurrence above?)
Solution 1
Suppose that
- \(b_{n}\) is the number of ternary strings of length \(n\) that do not contain two consecutive 0s or two consecutive 1s and ends with 0, and ends with 0 or 1.
- \(c_{n}\) is the number of ternary strings of length \(n\) that do not contain two consecutive 0s or two consecutive 1s and ends with 0, and ends with 2.
Now our goal is to figure out \(a_n = b_n + c_n\). Then we have
\[\begin{aligned} b_n &= 2c_{n-1}+b_{n-1} \\ c_n &= b_{n-1} + c_{n-1}. \end{aligned} \]By adding the above equations together, we have that
\[(b_n + c_n) = 2(b_{n-1} + c_{n-1}) + c_{n-1} \]where \(c_{n-1} = (b_{n-2} + c_{n-2})\). Hence if \(a_n = b_n + c_n\), then
\[a_n = 2a_{n-1} + a_{n-2}, \quad n \geq 3 \]Solution 1.1
The direct argument can be deduced by the above solution. Let \(a_n\) be the number of ternary strings of length \(n\) that do not contain two consecutive 0s or two consecutive 1s. Consider string with length \(n\).
- If the last digit is not 2, then there are \(2a_{n-1}\) solutions, since each strings whose end is not 2 can add either a 0 or 1 or a 2.
- If the last digit is 2, then there are \(a_{n-2}\) solutions.
Therefore, we have the recurrence relation
\[a_n = 2a_{n-1} + a_{n-2}, \quad n \geq 3 \]Remark The direct argument is sometimes hard to come up with. We can simplify thinking by assuming some intermediate recurrence terms.
b) The initial conditions are \(a_1 = 3\) (since there are three possible ternary strings of length 1: 0, 1, and 2) and \(a_2 = 7\) (since there are nine possible ternary strings of length 2: 01, 02, 10, 12, 20, 21, 22, and none of these contain two consecutive 0s or two consecutive 1s).
c)
RSolve[{a[n] == 2 a[n - 1] + a[n - 2], a[0] == 1, a[1] == 3}, a[n], n]
Simplify[%]
where \(a_6 = 239\).
8.1.16
a) Find a recurrence relation for the number of ternary strings of length \(n\) that contain either two consecutive 0s or two consecutive \(1 \mathrm{~s}\).
b) What are the initial conditions?
c) How many ternary strings of length six contain two consecutive 0 s or two consecutive 1s?
This is the counter part of 8.1.15.
8.1.22
*22. a) Find the recurrence relation satisfied by \(R_n\), where \(R_n\) is the number of regions into which the surface of a sphere is divided by \(n\) great circles (which are the intersections of the sphere and planes passing through the center of the sphere), if no three of the great circles go through the same point.
b) Find \(R_n\) using iteration.
Solution Let us consider some trivial circumstances first.
\(R_1 = 2\), because a plane passing through the center point can divide the sphere in to 2 parts.
\(R_2 = 4\), because 2 planes passing through the center point can divide the sphere in to 4 parts.
When \(n = 3\), consider the increment of this stage. Let us imagine now we already have a sphere which is already divided by 2 planes, and these planes have intersection with the sphere, clearly they are 2 circles. We choose a point not on the two circles and move around the sphere center for one lap. Then the intersection of the generated circle and the previous circle will form four points. For each additional intersection point generated, the number of divided regions on the sphere will increase by one. Hence there are \(R_3 = R_2 + 2*(2) = 7\) parts of the surface of sphere.
So clearly \(n = R_{n-1} +2(n-1),n\geq 2\).
Remark Here we cannot use the initial condition \(R_0 = 1\) to solve the recurrence relation, because when there is no plane, a new generated circle will intersect nothing on the sphere.
8.1.23
*23. a) Find the recurrence relation satisfied by \(S_n\), where \(S_n\) is the number of regions into which three-dimensional space is divided by \(n\) planes if every three of the planes meet in one point, but no four of the planes go through the same point.
b) Find \(S_n\) using iteration.