HW#3: 8.1: #30,32,34 8.2: #20,24 8.3: #18,27 12.3: #18
8.2 #24: Let A be the set of numbers which begin with 3, and end with 5. Let B be the set of numbers which have a 7.
|A|=1*10*10*10*1, |B|= 9*10*10*10*10- 8*9*9*9*9 (all -no 7's)
|A \intersect B|=1*(10*10*10-9*9*9)*1.
#1: Proof #1: This is the same as
Dn/n!=(1-1/n)*Dn-1/(n-1)!+1/n*Dn-2/(n-2)!.
Using the explicit formula for Dn/n!, we see that we need to show
(-1)n-1/(n-1)!+(-1)n/(n)!=(1-1/n)*(-1)n-1/(n-1)!
which is true.
Proof #2: We give a combinatorial proof: Split the derangements of n into 2 disjoint sets:
Set #1: Last element is i (not equal to n), and the ith element is n. The other n-2 elements then form a derangement of n-2, so there are (n-1)*Dn-2 elements in Set #1.
Set #2: Last element is i (not equal to n), and the ith element is not n. Then deleting the last element, we get a derangement of n-1, with n replacing the element i. There are (n-1)*Dn-1 elements in Set #2.
2. This is just
Dn/n!=Dn-1/(n-1)!+(-1)n/(n)!.
3. Let A_i be those integers at most n which are divisible by pi. We need the intersectino of the complements. So by PIE, this is
n-(n/p1+n/p2+..+ n/pk)+ (n/p1p2+n/p1p3+... ) -....
=n(1-1/p1)(1-1/p2)...(1-1/pk).
For example if n=24 k=2, p1=2, p2=3, we get
24*(1/2)*(2/3)=8, and there are 8 numbers relatively prime to 24: 1,5,7,11,13,17,19,23.
4. Apply d/dx(x d/dx) to the binomial theorem and then put x=1. You get n*2n-1+n(n-1)*2n-2.
5. We'll include 1 later if necessary. Let Ai be the set of perfect ith powers at most 1000 and at least 2. We need only take i between 2 and 9 since 210=1024. We need the size of the union of the Ai. By PIE, using
Ai \intersect Aj= A LCM(i,j),
we get
(30+9+4+2+2+1+1+1)-(2+4+2+1+2+1+1)+(2+1+1)=50-13+4=41.
6. There are (n+1 choose m) such words. Build a subset of size m of {0,1,..,n} from such a word in the following way: the ith element of the m-set is the number of 1's to the left of the ith 0.
7. (n-1 choose k-1). Again build a (k-1)-subset of {1,2,...,n-1} by taking the partial sums except the for total sum which is always n. For example if n=12, k=6, we have 12=2+3+2+1+1+3, the partial sums are 2,5,7,8,9, so the 5-set of {1,2,...,11} is {2,5,7,8,9}.