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
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 1 2 3
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+2◆ 3·✓6+2◆+3·1. 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:
49 49⌫ 49⌫ 49⌫ 49⌫+ 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) (Dn 1 + Dn 2).
(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) Let’s 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,…,i 1,i+1,…,n} ! {2,…,i 1,i+1,…,n} is a derangement of n 2 elements. So the number of possibilities for case 1 is Dn 2 .
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 Dn 1.
In total, the number of derangements with f(1) = i is Dn 2 + Dn 1. Summing over all 2 i n, we get that the total number of derangements is (n 1)(Dn 2 + Dn 1). Since we have counted the same thing twice, it must follow that
Dn = (n 1)(Dn 1 + Dn 2).
(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) Let’s 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 nk Dn k. Summing over all possible numbers of fixed elements, we get that the total number of permutations is
Xn ✓nk◆Dn k. k=0
Since we have counted the same thing twice, it must follow that
n!=Xn ✓nk◆Dn k. k=0
✓ nk ◆ D n k .
3. Given the sequence of coe cients, 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 n 1n
(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 . 1 x
(c) First, consider the power series for 1 : 1 x
1 =Xxn. 1 x n 0
1 = X nxn 1.
Now take the derivative:
(1 x)2
Hence, 1 correspondstothesequence1,2,3,4,5,6,…. Multiplyingthisby
n 1
x2 gives us 0,0,1,2,3,4,5,6,…, and adding 1 gives us the sequence in question.
x2 (1 x)2 1.
(1 x)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 1 x3
so we need to slide over twice, meaning our generating function is
x2 1 x3.
(e) The corresponding power series is
Xn ✓nk◆xk. k=0
From the Binomial Theorem, it follows that the generating function is (x + 1)n.
(f ) Let’s start with something easier: What is the generating function for 1, 2, 4, 8, 16, . . . ?
In this case, the coe cient of xn is 2n, so we can deduce that the generating func-
tion is 1 . Then, to make the coe cients alternate parody, we have 1 . Lastly, 1 2x 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 coe cients: (a) x(x 1)(x 2)
(b) x4 1 x
(c) (d) (e) (f)
1 1+x2
1 (1 x)3
1 1+3x+2×2
1 (for some constant ↵) 1 ↵x
Solution:
(a) Expanding this gives x(x2 3x+2) = x3 3×2 +2x. So the sequence of coe cients 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 it’s
1 x 1 x 0,0,0,0,1,1,1,1,1,1,1,…
(c) x2 stretchesoursequencebyafactorof2,so 1 givesthesequence1,0,1,0,1,0,…. 2 2 1 x2
The +x instead of x causes our coe cients to alternate. So the sequence is 1,0, 1,0,1,0, 1,0,…
(d) The derivative of 1 is (1 x)
(1 x)2 Taking the derivative again gives us
1 =Xnxn 1 =X(n+1)xn.
n 1 n 0
2 =X(n+1)nxn 1 =X(n+2)(n+1)xn.
(1 x)3
Dividing by 2 gives us our generating function, and so the sequence is
n 1 n 0
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+2×2 (1+2x)(1+x) 1+2x 1+x
WeneedA+B=1andA+2B=0,andsoA=2andB= 1. Soweget 1 =2+ 1.
1+3x+2×2 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 coe cients for A(x) and B(x), find the closed form of A(x)B(x) using Cauchy’s 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 coe cient of xn is Pnk=0 akbn k. Notice that b0 = 1, b1 = 1, and bk = 0 for
allk>1.So Xn
akbn k = anb0 + an 1b1 = an an 1. k=0
Hence, the coe cient of A(x)B(x) is 0 for all n 1. Furthermore, the coe cient 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, 1 x
A(x)B(x)= 1 x =1. 1 x