This is the second of our two Maple Assignments. It is due on Thursday May 3. Please read and follow all
instructions carefully. You may work in groups of three this time ( no more ) if you wish ,
but this is not required. You should submit printed Maple worksheets , not photocopies of Maple
worksheets and not floppy disks. Each team to submit one report only.
Part One From our Finite Mathematics textbook. These are from our textbook and
are from the problems where use of calculator or computer is required. The answers are frequently at
the back of the book. It is therefore essential that you show the commands that you used to
get the answers. (e.g. it won't do to simply type the answers in).
1. Page 83 # 59 , 60 , 61 , 62 ( What laws are being investigated? Which one fails? )
2. Page 92 # 31 Do it a second time using rref command on the augmented matrix
3. Page 104 # 11
4. Page 376 # 25
5. Page 385 # 21
Part Two From Our Math 150/151 Maple/ Calculus Lab Manual
6. Page 216 # 12
7. Page 217 # 1
8. Page 218 # 9
9. Page 220 # 5
10. Page 223 # 4
Part Three Some Extra Fun
11. Find Example 3 on page 41 of our Finite Mathematics Text. Solve the least squares problem
which is solved there by using our At A x =Atb method.
12. (i) Substitute : x-> - x2 in the famous geometric series to get the series for 1/ ( 1+x2)
(ii) Ask Maple for the derivative of arctan(x).
(iii) Therefore term by term integration of your series fom (i) will certainly give the series
for arctan(x). Explain why this is so and have Maple give directly the series for
arctan(x) up to degree 47.
(iv) Convert your series from (iii) into a polynomial by using the convert (% , polynom)
command. You are doing this so that you can safely:
(v) Substitute x=1 into that 47th degree polynomial. But then
(vi) Have Maple verify that arctan(1)= 9 /4 (Pi/4).
(vii) So multiply your result from (v) by 4 to get an estimate for 9 (Pi).
(viii) Comment on the accuracy of this estimate.
13. Look at problem #11 from your Mid Term Exam #2. There it was to be noted that the error
in estimating the number e from it's Taylor polynomial of degree three ( at x=0 ) was
exactly exp(c) * /4! where 02c21. Use Maple to find (nearly) the number c for this case.
14. (i) Let A be the generic 2 by 2 matrix: First Row a , b : Second Row c , d
Following the idea presented in problem 98 page 224 nd 225 of our Maple Manual,
use Maple to prove that A^2 = ( a+d ) A - ( ad-bc ) Id , where Id is the 2 by 2 identity
matrix.
(ii) Apply this to the B matrix whose first row is 1 , 17 second row is 0 -1.
(iii) Write down instantly the power B^100 , B^101. Maple verify.
Part Four
15 "Probleme des Rencontres" II. (continued from first assignment) Recall your calculation:
Fix [3, {1 }] + Fix [3, {2 }] + Fix [3, {3 }]
- Fix [3, {1 , 2}] - Fix [3, {1 , 3 }] - Fix [3, {2 , 3 }]
+ Fix [3, {1 , 2 , 3 }]
here , Fix [3, {1 }] is the number of permutations of the set {1 , 2 , 3 } that leave 1 in first position.
There are two such permutations {1 , 2 , 3 } and {1 , 3 , 2 }. And Fix [3, {2 , 3 }] is the number
of permutations of the set {1 , 2 , 3 } that leave 2 AND 3 in their original positions. There is only one such. In fact
the calculation of
Fix [3, {1 }] + Fix [3, {2 }] + Fix [3, {3 }]
- Fix [3, {1 , 2}] - Fix [3, {1 , 3 }] - Fix [3, {2 , 3 }]
+ Fix [3, {1 , 2 , 3 }] gives 2 + 2+ 2 - 1- 1- 1+ 1 =4. And this is the total number of permuations of {1 , 2 , 3 }
that have a t least one fixed point. Therefore the number of permutaions of {1 , 2 , 3 } that have no fixed points
(successful Polyannas) is 3! -4 =2. Therefore the probability that a random polyanna drawing works is
(3! -4) / 3! or (6-4)/6 = 1/3. But this is assuming there were three people in the office. What if there are four?
Exercise 1. We will find out how many permutations of {1 , 2 , 3 , 4 } have no fixd points by calculating how many
have at least one and subtracting that number from 4! Then that difference will be divided by 4! Explain why this
will work.
Exercise 2 Calculate :
Fix [4, {1 }] + Fix [4, {2 }] + Fix [4, {3 }] + Fix [4, {4 }]
- Fix [4, {1 , 2}] - Fix [4, {1 , 3 }] - Fix [4, {1 , 4}] -Fix [4, {2 , 3 }] - Fix [4, {2 , 4}] - Fix [4, {3 , 4}]
+ Fix [4, {1 , 2 , 3 }] + Fix [4, {1 , 3 , 4 }] +Fix[4, {2 , 3 , 4 }] + Fix [4, {1 , 2 , 4 }]
- Fix [4, {1 , 2 , 3 ,4 } ]
Exercise 3 Explain why the number you calcuated in Exercise 2 gives the total number of permutations of
{1 , 2 , 3 ,4 } that have at least one fixed point.
Exercise 4 Explain why the numbers you calculated in Exercise 2 are (line by line)
3! + 3! + 3! + 3!
-2! -2! -2! -2! -2! -2! -2!
+1! +1! +1! +1! +1!
-0!
Which , for the purpose of exposing the underlying pattern ,we may write as:
4* 3! - 6*2! + 4 * 1! - 1 *0! And , still better as:
C(4 , 1 ) * (4-1)! - C(4,2) * (4-2)! + C(4,3) * (4-3)! -C(4,4 ) *(4-4) !
Exercise 5 The number from exercises 2 , 3 and 4 is 15. So the probability that the polyanna succeeds in an
office of four people is what?
Exercise 6 The pattern is now evident. When th number of people is 5 the probability of a successful
drawing is ( 5! - (?) )/ 5! . It remains to fill in the ? But that will be :
? = C(5, 1 ) * (5-1)! - C(5,2) * (5-2)! + C(5,3) * (5 -3)! - C(5,4 ) *(5-4)! + C(5,5 ) *(5-5)!
But C ( 5, k ) * ( 5-k )! = 5! / k! Explain why...it's easy.
Exercise 7 Then our probability , ( 5! - (?) )/ 5! becomes :
(1/5! ) * [ (5!) - ( 5 ! / 1! ) + ( 5 ! / 2! ) - ( 5 ! / 3! ) + ( 5 ! / 4! ) + ( 5 ! / 5! ) ] , which is
[ ( 1/ 2! ) - (1 / 3! ) + ( 1/ 4! ) + ( 1 / 5! ) ]
Explain why this is so.
Exercise 8 Go back and redo the probabilities for four people and for three people to see that the final
result is in accordance with the the lst line of Exercise 7.
Exercise 9 Write out the probability that an office with six people will have a successful drawing.
And for seven. And for eight.
Execise 10 Now that we know how to write the answer to the "Probleme des Rencontres" (which is
the formal name of our Polyanna problem ) as soon as we know how many people there are , we will have
Maple finish these calculations. Have Maple produce the Taylor series for ex centered at x=0 , up to
degree three . The command for this is
> series(exp(x),x=0,4); ( This is pretty self explanatory..the x=0 tells Maple where the center is,
and the 4 tells it to go to degree three .. degree 0 ,1 , 2 ,3 includes 4 terms.
Now have Maple convert this into a usable polynomial by using
> convert(% , polynom ); ( This gets rid of the O (x4) thing...which is telling us that the rest of the
series has only terms of degree 4 or higher)
Now plug x=-1 into your polynomial of degree three
> subs( x=-1 , % ); Explain why this gives our answer in caase there were three people in the office.
Execise 11 This works because the pattern we first observed back in Exercise 7 is seen to be exactly
what results when we take the series for ex and substitute x = - 1 . The first two terms cancel , the signs
alternate and the result is beautiful. Calculate the probability for 4 people , 5,then 6 then 7 .
Exercise 12 Here is a little program which will compute the probability for any given number of people
> P:=n->evalf(subs(x=-1,(convert(series(exp(x),x=0,n+1),polynom))));
Type this in exactly as you see it. Then compute:
P(2) , P(3) P(4) to make sure it's doing what it should.
Then do P(20) , P (30) P(40).
What is happening ? Could it be that P (30) and P(40) differ by so little ?
What is limit ( P(n) ) as n-> infinity?
This is the first of our two Maple Assignments. It is due on Thursday March 22 at Lecture. Please
read and follow all instructions carefully. You may work in groups of two ( no more ) if you wish
but this is not required. You should submit printed Maple worksheets , not photocopies of Maple
worksheets and not floppy disks.
Part One From our Finite Mathematics textbook. These are from our textbook and
are from the problems where use of calculator or computer is required. The answers are at
the back of the book. It is therefore essential that you show the commands that you used to
get the answers. (e.g. it won't do to simply type the answers in)
1. Page 220 # 71
2. Page 226 # 47
3. Page 236 # 27
4. Page 270 # 47 (you can experiment with various numbers of topics to select from until it works)
5. Page 323 # 23
Part Two From Our Math 150/151 Maple/ Calculus Lab Manual
6. Page 207 # 5
7. Page 208 # 6
8. Page 208 # 8
9. Page 208 # 9
Part Three Combinatorial Fun
Introduction. We are going to have Maple prove some combinatorial formulas. Begin with a definition:
ncom:=(n,k)->factorial(n)/(factorial(n-k)*factorial(k));
So that ncom(n,k) is C(n,k). For an example of what you will be doing here remember that we proved
(see page 231 # 52 of Finite Mathematics) that C(n,k-1) + C(n,k) = C(n+1,k). This is a key fact in
the construction of Pascal's Triangle. Our proof was based on singling out an element of the set of
(n+1) members and looking at subsets which did or did not contain that element. We can have Maple
prove this identity like so:
> exp1:=ncom(n,k)+ncom(n,k-1);
exp1:= n! / ((n-k)! * k!) + n! / ((n-k+1)! * (k-1)!)
> exp2:=ncom(n+1,k);
exp2 := (n+1)! / ( (n-k+1)! k!)
> exp2-exp1;
(n+1)! / ( (n-k+1)! k!) - n! / ((n-k)! * k!) - n! / ((n-k+1)! * (k-1)!)
> simplify(%);
0
Be sure you understand why we should regard the above steps as a proof of the identity.
And now:
10. Use Maple to "prove" n * C (n-1 , k-1 ) = k* C ( n , k ) ( we needed this one to derive the
correct expression for the mean of a Binomial probability distribution)
11. Use Maple to " prove " C ( 2n , 2) = 2 * C (n , 2 ) + n^2 . You should amuse yourself
by figuring out via purely combinatorial reasoning why this is true.
12. Start with two disjoint sets. One has n elements , the other m elements. We wish to count
the number of ways to choose r elements from the union of the two sets. We assume that
r exceeds neither n nor m. Clearly there are C ( m + n , r ) ways to do this. However we can
accomplish the same thing by choosing k elements from the set of n and then choosing r-k from the
set of m. That can be done in C ( n , k ) * C (m , r - k ) ways. But k ( the number we choose from
the set of n ) can be any number from 0 to r inclusive. Therefore we expect that
C ( m + n , r ) = sum ( C ( m , r -k ) * C ( n , k), k = 0..r)
Use Maple to "prove" this. It's called Vandermonde's Formula
13. An organization has 100 members . They have to choose 20 members to send to the annual
convention and 5 of the 20 are to be designated as delegation leaders. The group may first
choose the 20 and then choose the delegation leaders from those. But they can just as easily
select the 5 leaders first and then choose the remaining members of the delegation. This
suggests a combinatorial identity of the form:
C ( 100 , 20 ) * C ( 20 , 5 ) = C ( _? , _? ) * C ( _? , _? ).
The left hand side counts the number of ways one can first choose the entire delegation and
then the delegation leaders from among them. The right hand side is to count the number
of ways the delegation can be chosen if the delegation leaders are chosen first.
(i) Fill in the right hand side and verify that it is correct (using Maple)
(ii) Figure out and prove the correct " general " statement.
Part Four
14. "Probleme des Rencontres" I.
You are one of n people who work in an office. As holiday time approaches you all
decide on a Pollyanna as a sensible alternative to everyone buying gifts for everyone else.
So everyone writes his/her name on a slip of paper and places the slip into a bowl.
Everyone is to draw a name from the bowl and a to give a holiday gift to the person
whose name is on the slip and to no one else. There is one possible technical difficulty
with this plan however. It is not OK for someone to draw his/her own name. It is therefore
agreed that if this happens the drawing has to be restarted with all names back into the bowl.
Our problem is to investigate , for various (indeed all possible ) values of n , the probability
that the drawing of names is successfully completed. The definition of successful completion
is of course that no one draws his/her own name.
Our first job is to cast this into a suitable mathematical form. We think of a set of n elements
as the set { 1 , 2 ...n} and a permutation as a derangement of the set from its original , natural
order. Some permutations will derange the set more than others...i.e some permutations will leave
some of the elements in their original position while displacing others. We are interested in
permutations which displace every element. ( no one draws his/her own name). Be sure you
understand this simple point before proceeding. An element of the set which is not displaced by a
given permutation is called a fixed point of the permutation. A successful completion of the
Pollyanna drawing corresponds to a permutation with no fixed points at all.
Example: If n=4 the permutation { 3 , 1 , 4 , 2 } has no fixed points while the permutation
{ 2 , 4 , 3 , 1 } has one fixed point. The 3 is still in its original position.
Exercise 1 To calculate the probability that a given attempt to draw names from the
bowl succeeds we have to count the number of permutations of {1 , 2 , ....n} which
do / do not ( you decide) have fixed points and then divide by what?
Exercise 2 If there are only two people in the office what is the probability of a successful
drawing?
Exercise 3 If there are only three people in the office what is the probability of a successful
drawing?
Exercise 4 Suppose there are four people in the office. Have Maple list all permutations
of the set { 1 , 2 , 3 , 4} Use the command ( after loading the combinatorial package)
> permute({1,2,3,4});
Count by hand the number of permutations that result in a successful drawing. So for n=4
what is the probability that a given drawing succeeds? ( Be sure to turn in the list of permutations
that Maple produced)
Exercise 5 Same as Exercise 4 but now n=5. This is quite a bit less convenient than the precceding
case.
We are not interested in continuing in this manner. We need a systematic method of attack. Although
we are interested in the number of permutaions without fixed points we will count the number of
permutations that do have fixed points and subtract that number from n! . Let's go back to the case
n=3 for a minute. To count the number of permutations of { 1 , 2 , 3 } that do have fixed points
why can't we do this? First count the number of permutaitons for which 1 is a fixed point , then
count the number of permutations for which 2 is a fixed point , then count the number of permutatons
for which 3 is a fixed point and then add these numbers up. This doesn't quite work. We run into the
old principle of "inclusion exclusion". A permutaion which leaves more than one of the items fixed has
been counted more than once. So we try this. Let Fix [n,{x,y,....}] be the number of permutaions of
the set { 1 ,2 ...n} that leave {x , y ....} fixed , without regard to whether or not they leave any other
elements fixed. For example Fix [3,{1}] is the nnumber of permutions of {1,2,3} that leave 1 fixed.
Fix [3,{1}] = 2 . There are two permutaions of { 1,2 3 } that leave 1 fixed. They are { 1 ,2 , 3} and
{1 , 3 , 2}. Similarly Fix [5,{1 , 3}] = 3! =6. Why? Because we are starting with a five element
set { 1, 2 , 3 , 4 , 5 } and making all permutations as we please but we are not allowed to move the
1 and not allowed to move the 3. So we are really only permuting three elements , the 2 , the 4 and
the 5.
Exercise 6 What are each of these numbers?
(i) Fix [5, {1 , 4}]
(ii) Fix [7,{ 6 }]
(iii) Fix [6,{2, 3 , 4}]
(iv) Fix [8,{2 , 4 ,5 , 7}]
(v) Fix [5,{ 1, 2 , 3 , 4 , 5 }]
Exercise 7 Consider the following calculation:
Fix [3, {1 }] + Fix [3, {2 }] + Fix [3, {3 }]
- Fix [3, {1 , 2}] - Fix [3, {1 , 3 }] - Fix [3, {2 , 3 }]
+ Fix [3, {1 , 2 , 3 }]
Work this out. It equals 4. Explain Why this is an exact and correct calculation of the number of
permutaions of a a three element set that leave one or more points fixed. Therefore there are
six - four = two permutaions that have no fixed points. So the probability that the Pollyanna
drawing in an office of three people will succeed is one third.
In the second Maple assignment you will complete this analysis. You will figure out the probability
of a successful drawing for n= 4 , 5 , 6 , 7 ...... You will write a little Maple program command that
produces these probabilities and notice how much the probabilities change as the number of people
in the office changes. The results are amazing and quite famous.