[SOLVED] CS Math 340 Tutorial 2

Math 340 Tutorial 2
1. Inclusion/Exclusion
(a) How many numbers in {1, . . . , 100} are not divisible by 5 or 8?
(b) Howmanynumbersin{1,,n}arenotdivisiblebyaorbwhere1<a<b<n and gcd(a, b) = 1.(c) How many solutions does the equation x1 + x2 + x3 = 12 have, where xi 2 {0,1,…,4} for each i 3?(d) Call a natural number n square free if n = p1 … pi for some collection of disctinct primes p1, …, pi. How many square free numbers are less than 50?Solution:(a) Let A {1,…,100} be the numbers divisible by 5 and B {1,…,100} be the numbers divisible by 8. Then A B are the numbers divisible by both 5 and 8, i.e. divisible by 40. Its clear that |A| = 20, and to count |B|, we consider the largest number up to 100 that is divisible by 8. This number is 96, and so |B| = 96/8 = 12. Lastly, A B = {40,80} meaning |A B| = 2. Therefore, by the principle of Inclusion/Exclusion, the number of elements in {1, . . . , 100} that are not divisible by 5 or 8 is100 |A| |B| + |A B| = 100 20 12 + 2 = 70.(b) This question is just a generalization of (a). Let A {1, . . . , n} be the numbers divisible by a and B {1,…,n} be the numbers divisible by b. Then AB are the number divisible by both a and b. Since gcd(a, b) = 1, it follows that A B are the numbers divisible by ab.To compute |A|, first consider the case where a divides n. In this case, A ={a,2a,3a,…,(n/a)a}, meaning |A| = n/a. If a does not divide n, then n = ca+rfor some 0 < r < a. In this case, A = {a,2a,3a,…,ca}, meaning |A| = c = bnc. na So in general, |A| = b a c, and similarly for |B| and |A B|. Therefore, by the principle of Inclusion/Exclusion, the number of elements in {1,…,n} that are not divisible by a or b is n |A| |B| + |A B| = n jnk jnk + j n k. a b ab (c) There is only 1 solution: x1 = x2 = x3 = 4. How about instead we insist that xi 2 {0, 1, . . . , 5} for each i? In this case we will end up needing Inclusion/Exclusion.Weknowthatthetotalnumberofsolutionstox +x +x =12withx ,x ,x 0 12+2 123 123is 2 . Now let A1 be the set of solutions such that x1 > 5, and similarly for A2 and A3.
To count |A1|, consider the number of solutions to x1 + x2 + x3 = 12 where x > 5. We can instead count the number of solutions to x0 +x +x = 6, where
1 123
x0 = x 6. Then x0 0. The number of solutions here is 6+2 , and the same
1112
argument works for |A2| and |A3|. For |A1 A2|, this is the case where x1 > 5
and x2 > 5. The only possibility here is that x1 = x2 = 6 and x3 = 0, meaning |A1 A2| = 1, and similarly for |A1 A3| and |A2 A3|. Lastly, it is impossible for x1, x2, x3 > 5 since then the sum is greater than 12. So |A1 A2 A3| = 0.
Therefore by the principle of Inclusion/Exclusion, the number of solutions to x1 +x2 +x3 =12withxi 2{0,1,,5}foreachiis
12+236+2+31. 22

(d) By this definition, a number is square free if and only if it is not divisible by p2 for any prime p. Since 82 = 64, a number in {1,,49} is square free if and only if it is not divisible by 22, 33, 52, or 72.
Let A2 be the elements in {1,,49} that are divisible by 22, and similarly for A3,A5 and A7. Using our argument from (b), we can quickly find our solution to
be:
4949494949+ 49 . 22 32 52 72 22 32
Notice that A2 A3 is the only non-zero intersection. An element of A2 A5 must be divisible by 22 52 = 100, and similarly for the other intersections. We could have written them in the solution as well, since the floor function would ensure that the terms are all zero.

2. Derangements
(a) Prove, either combinatorially or algebraically, that Dn = (n 1) (Dn1 + Dn2).
(b) Count the number of functions f : {1,,n} ! {1,,n} such that exactly k elements of {1,,n} are fixed by f.
(c) (8.6, question 24 in Rosen) Prove the following identity:
n ! = n0 D n + n1 D n 1 + + n n D 0 .

Solution:
(a) Lets prove this combinatorially. Let f : {1,,n} ! {1,,n} be a derange- ment function. The number of such functions is Dn, but we can instead count them by focusing on f(1). Let f(1) = i, where i 6= 1. Then there are two cases to consider:
Case 1: If f(i) = 1, then f : {2,,i1,i+1,,n} ! {2,,i1,i+1,,n} is a derangement of n 2 elements. So the number of possibilities for case 1 is Dn2 .
Case 2: If f(i) 6= 1, then we can consider f : {2,,n} ! {2,,i 1,i0,i + 1, . . . , n}, where i0 = 1. Writing it like this, it becomes clear that this is the same as a derangement of n 1 elements, since we know that f(i) 6= i0. Hence, the number of possibilities for case 2 is Dn1.
In total, the number of derangements with f(1) = i is Dn2 + Dn1. Summing over all 2 i n, we get that the total number of derangements is (n1)(Dn2 + Dn1). Since we have counted the same thing twice, it must follow that
Dn = (n 1)(Dn1 + Dn2).

(b) We first choose which k elements are fixed, and there are nk ways to do this. Then, the remaining function is a derangement of n k elements. Hence, the
number of functions is
(c) Lets count the number of permutations of (1, . . . , n). The obvious solution is n!, but we can also break this up into cases based on the number of fixed elements in our permutation. By (b), if there are k fixed elements in the permutation, the number of such permutations is nkDnk. Summing over all possible numbers of fixed elements, we get that the total number of permutations is
Xn nkDnk. k=0
Since we have counted the same thing twice, it must follow that
n!=Xn nkDnk. k=0
nk D n k .

3. Given the sequence of coecients, find the corresponding generating function:
(a) 0,0,1,0,1,0,0,0, (b) 1,1,2,1,2,1,1,1,
(c) 1,0,1,2,3,4,5,6,7,8, (d) 0,0,1,0,0,1,0,0,1,
(e) n,n,, n ,n,0,0,0,0, 01 n1n
(f) 0,1,2,4,8,16,32,64,

Solution:
(a) x2 +x4.
(b) We can combine the sequences 0,0,1,0,1,0,0,0, and 1,1,1,1,1, to get
1, 1, 2, 1, 2, 1, 1, 1, . . . . Hence, the generating function is
x2+x4+ 1 . 1x

(c) First, consider the power series for 1 : 1x
1 =Xxn. 1x n0
1 = X nxn1.
Now take the derivative:
(1x)2
Hence, 1 correspondstothesequence1,2,3,4,5,6,. Multiplyingthisby
n1
x2 gives us 0,0,1,2,3,4,5,6,, and adding 1 gives us the sequence in question.
x2 (1x)2 1.
(1x)2
So the generating function is

(d) To stretch a sequence, we replace x by xk where k is the amount of stretching
we need. In this case, we need to stretch by a factor of 3, so our generating
function is something like 1 . However, this gives 1,0,0,1,0,0,1,0,0,, and 1x3
so we need to slide over twice, meaning our generating function is
x2 1x3.

(e) The corresponding power series is
Xn nkxk. k=0
From the Binomial Theorem, it follows that the generating function is (x + 1)n.

(f ) Lets start with something easier: What is the generating function for 1, 2, 4, 8, 16, . . . ?
In this case, the coecient of xn is 2n, so we can deduce that the generating func-
tion is 1 . Then, to make the coecients alternate parody, we have 1 . Lastly, 12x 1+2x
we multiply by x to slide everything over. So the generating function is
x. 1+2x

4. Given the generating function, find the corresponding list of coecients: (a) x(x1)(x2)
(b) x4 1x
(c) (d) (e) (f)
1 1+x2
1 (1x)3
1 1+3x+22
1 (for some constant ) 1x

Solution:
(a) Expanding this gives x(x2 3x+2) = x3 32 +2x. So the sequence of coecients is
0,2,3,1,0,0,0,0,
(b) The sequence of x4 is just the sequence of 1 slid over 4 times. So its
1x 1x 0,0,0,0,1,1,1,1,1,1,1,
(c) x2 stretchesoursequencebyafactorof2,so 1 givesthesequence1,0,1,0,1,0,. 2 2 1x2
The +x instead of x causes our coecients to alternate. So the sequence is 1,0,1,0,1,0,1,0,

(d) The derivative of 1 is (1x)
(1x)2 Taking the derivative again gives us
1 =Xnxn1 =X(n+1)xn.
n1 n0
2 =X(n+1)nxn1 =X(n+2)(n+1)xn.
(1x)3
Dividing by 2 gives us our generating function, and so the sequence is
n1 n0
2 1 , 3 2 , 4 3 , . . . , (n + 2)(n + 1) , . . .
222 2 In fact, this turns out to be
2, 32, 42, . . .

(e) The best course of action is to use partial fractions to turn this into a sum of two generating functions that are easy to analyse.
1=1=A+B. 1+3x+22 (1+2x)(1+x) 1+2x 1+x
WeneedA+B=1andA+2B=0,andsoA=2andB=1. Soweget 1 =2+1.
1+3x+22 1+2x 1+x The corresponding sequences are
and
2,4,8,16,32,2(2)n 1,1,1,1,1,1,(1)n
respectively. So the overall sequence is 1,3,7,15,31,,2(2)n (1)n

(f) 1,,2,3,

5. Given the sequences of coecients for A(x) and B(x), find the closed form of A(x)B(x) using Cauchys Theorem:
(a) A(x) : 1,1,1,1,1, B(x) : 1,1,0,0,0,0,
(b) A(x) : 1,2,3,4,5, B(x) : 1,1,1,0,0,0,0,
(c) A(x) : 1,0,1,0,1,0, B(x) : 0,1,0,1,0,1,

Solution:
(a) The coecient of xn is Pnk=0 akbnk. Notice that b0 = 1, b1 = 1, and bk = 0 for
allk>1.So Xn
akbnk = anb0 + an1b1 = an an1. k=0
Hence, the coecient of A(x)B(x) is 0 for all n 1. Furthermore, the coecient of x0 is 1, meaning A(x)B(x) = 1.

6. Given A(x) and B(x) as in the previous question, find the closed form of A(x)B(x) by finding the closed forms of A(x) and B(x), then multiplying them together.

Solution:
(a) 1,1,1,1, corresponds to 1 , and 1,1,0,0,0,0, corresponds to 1 x. Hence, 1x
A(x)B(x)= 1x =1. 1x