Math 5020: Fundamentals of Mathmatics for Teachers

Math 5020

Fundamentals of Mathematics for Teachers

Description: Number Theory and Combinatorics are branches of mathematics in which theorems and problems are usually easy to state but often difficult to prove or resolve. This course will deal with topics in these two fundamental mathematical fields, including modular arithmetic, linear and quadratic diophantine equations, continued fractions, permutations and combinations, distributions and partitions, recurrence relations, generating functions, formal power series. The use of computers for mathematical exploration will be encouraged through the computer program Maple. The course will cover material from 'Number Theory' by George Andrews and supplementary material on generating functions and species.

Professor Mike Zabrocki
Office: TEL 3046
Hours: Thursday 4-5:30pm
phone: 416-736-2100 x33980
e-mail: zabrocki at mathstat dot yorku dot ca

Class meets Thursday 6-9pm in VC 102

Text : Number Theory by George Andrews

A random picture by M. C. Escher that looks cool

We have a FORUM for math 5020. This is a web site that will allow you to post questions/comments/communications about the course. I will try to keep track of postings and answer them on a regular basis.

Forum problems for Fall:

section 1.1 #2 - Shirley Ting
section 1.1 #8 - Anna Yoon
section 1.1 #9 - Andrea Young
section 1.1 #10 - Dorota Mazur
section 1.1 #11 - Ada Tsui
section 1.1 #12 - Pauline Fu
section 1.1 #13 - Paul Attar
section 1.1 #14 - Taravat Moshtagh
section 1.1 #15 - Mike Eden
section 1.1 #16 - Kevin Smith
section 1.1 #18 - Pierre Lacoste
prove k^{n+2}+(k+1)^{2n+1} is divisiable by k^2+k+1 - Toni Katsinos
section 1.2 #3 - Inna Belozorovich
section 1.2 #4 - ? cant read
section 2.1 #6 - Melissa Giardina
section 2.2 #4 - Keith Auyeung
section 2.2 #7 - Samia Saleh
section 2.2 #10 - Mike Eden
section 3.1 #12 - Pauline Fu
section 3.1 #14 - Shirley Ting
prove by induction C(n,k) = n!/(k!(n-k)!) - Anisoara Preda
section 4.1 #4 - Toni Katsinos
section 4.1 #6 - Carol Miron
explain 1-pair - Paul Attar
explain 2-pair -
explain 3 of a kind - taken
explain straight - taken
explain flush - taken
section 4.3 #2 -
section 7-1 #1 - Paul Attar
section 8-1 #1 - Margarita
What fraction of all arrangements of the letters of the word 'GRACEFUL' have no pair of consecutive vowels - Pierre Lacoste
A bag contains 50 red balls and 50 blue balls. Ten balls are drawn at random from the bag. What is the probability that the balls are half red/blue? What if 20 balls are drawn at random (is this value higher or lower)? - Andrea Young
What is the probability that if a die is rolled a seqeunce of 5 times that only two different values appear? - Mike Eden
What is the probability that a random arrangment of REPLETE has no consecutive Es? - Pauline Fu
How many subsets of 3 different integers are there whose sum is divisiable by 4? - Anisoara Preda
If a coin is tossed eight times what is the probability of getting exactly 4 heads in a row? - Keith
If a coin is tossed eight times, what is the probability of getting at least 4 heads in a row? - Taravat
How many ways are there of rearranging the letters of the word MISSISSIPPI? - Keith
How many ways are there to arrange the letters in the word VISITING with no pair of consecutive Is? - Anna

Course presentation topics
Fermat's Little Theorem	Kevin Smith	Sept 29
Wilson's Theorem	Shirley Ting	Oct 6
card shuffling	Pierre Lacoste	Oct 20
solving congruences	Dorota Mazur	Oct 27
chinese remainder theorem	Pauline Fu	Nov 3
multiplicative functions	Mike Eden	Nov 10
Möbius inversion	Samia Saleh	Nov 17
primitive roots	Jeff Irwin	Nov 24
distrib. primes & Tchebychev's ineq	Toni Katsinos & Carol Miron	Dec 1
quadratic reciprocity	Melissa Giardina & Paul Attar	Jan 5
pseudo-primality testing Jacobi and Legendre symbols	Ada Tsui & Andrea Young	Jan 12
RSA and Digital Signatures	Taravat Moshtagh	Jan 19
Sum of 4 squares theorem	Keith Auyeung	Jan 26
Generating functions	Anisoara Preda	Feb 2
Jacobi triple product identity	Anna Yoon	Feb 9
Fermat's Last Theorem and A. Weil	Margarita Panayotova	Feb 16
Ferrer's diagrams and partition ident.
partitions which fit in a rectangle

Grades for the course will be based on the following criteria:

Class presentation	20%
Un-exams (4 x)	10%+10%+15%+15%
Forum exercises	Fall 15%+Winter 15%

We've been following the book very closely. I'll try to keep track of what sections we've covered.

Sept 12 - Sect 1.1, 1.2, 2.1

Sept 19 - Sect 2.2, 2.3

Sept 26 - Sect 3.1, 3.2

Oct 6 - Sect 3.3, 3.5, 4.1, 4.2

Oct 20 - Sect 4.3

Oct 27 - Sect 5.1, 5.2

Nov 3 - Sect 5.3

Nov 10 - Sect 6.1,6.2,6.3

Nov 17 - Sect 6.4

Announcements

March 30, 2006- Now we have the tools, we can write down the generating functions for every set of partitions under the sun (worksheet #9). You should be able to do all of these exercises once you know what a Durfee square is. It is the largest square which fits inside the diagram for the partition. Every partition with a Durfee square of size k x k can be decomposed (uniquely) into a tuple consisting of a Durfee square, a partition of length <= k and a partition with parts of size <= k. (sorry, but the following picture is upside down compared to what we have been doing in class...also height = length).

Most of them take 30 seconds to write down the answer. Just glancing through it, number 19 is one of the few challenging ones on this list.

March 23, 2006- I announced the last unexam. This will be due for next week. If you cannot get it to me by then you will have to send it to me by email (NO Microsoft Word documents with equations please) no later than April 7.

March 23, 2006- We will consider partitions as combinatorial objects and dissect these to write down generating functions (worksheet #8).

March 9, 2006- I have been handing out roughly one set of problems and this week was no exception. We showed that some combinatorial identities (worksheet #7) could be proved by taking coefficients in generating function expressions. We did these in class.

March 2, 2006- I gave you a handout with some combinatorial problems which can be solved by generating functions. Worksheet #6. We will do more of these, but make sure that you understand (10), (11), (13), (14), (15), (16) which we did in class. For homework I asked you to do (10) and (11) on WS #4 because we didn't get to it that night.

February 27, 2006- We talked about the ADDITION AND MULTIPLICATION PRINCIPLE OF GENERATING FUNCTIONS.
For homework I asked people to prove (10) and (11) on Worksheet #4
I also handed out a worksheet consisting of a few expressions that I want to take coefficients (Worksheet #5) in. Please do these exercises for next week.

February 16, 2006- I had very few people do the exercise that I assigned at the end of class last week and so I assigned it as the next unexam problem.
Unexam #3 is due February 23, 2006. Sorry for the short notice but we are coming close to the end of this course and I was expecting this to be an easy question that everyone had an answer for this week.

February 16, 2006- We are slowly building up connections between three classes of mathematical concepts

Making these connections will require building up certain skills. This next set of exercises makes the connection between class 1 and class 3. Each one of these should take you no more than a couple of minutes. Please take the time to do all 26 of them for next week.
Worksheet 3: Algebraic expressions and sequences
The other worksheet I gave out was a list of a library of generating functions that you can refer to. We will prove all of these. So far Anasoria proved (1) and (9) and I proved (2) in class
Worksheet 4: Examples of generating functions

February 2, 2006- I gave a matching worksheet which we did half of in class. The purpose of this exercise is to make connections between algebraic expressions in variables a0, a1, a2, a3,.... and combinatorial descriptions of objects. I use word 'widget' to represent 'some combinatorial object.' An example of a 'widget of size n' might be 'a partition of the integer n into parts of size at most 3' or a 'a word of length n in the letters a and b such that a's are separated by at least two bs.'
Worksheet 2: Sequences and sets of objects

January 26, 2006- I gave worksheets about the online-encyclopedia of integer sequences. To everyone who was there I gave them a question off of this worksheet. If you did not get one, please ask me for a question. We will come back to this when we know more generating functions.
Worksheet 1: Sequences and sets of objects

January 20, 2006- Here is the Microsoft word document that Taravat gave copies of last night (the text version of the powerpoint presentation). I will try to convert it to PDF later.

January 18, 2006- For tomorrow nights class we will be going to the Gauss lab because Taravat will be doing a presentation using Maple. Please be in the classroom ON TIME because we will leave from there and go to the computer lab.

January 6, 2006- Last night I announced the next 'unexam.' The first of these unexams was an exercise that was quite straightforward and I didn't see a lot of variation on the assignment. This one I should see much more.

November 17, 2005- Last week I announced the first 'unexam.' I wanted to write some expectations (as well as the question) and place it on this web page. This assignment is due November 24, 2005.

I've had to make some changes to the schedule of presentations this term. As you might know Inna dropped the class suddently and so we don't have someone for November 17. If a brave soul would like to take up her topic or date then I wouldn't have to feel uncomfortable about not having time for everyone next term. If not, we will make due.

Dorota has been practicing using excell to compute greatest common divisors, exponentiation and chinese remainder theorems using Excel. I am posting her worksheets in Chinese Rem theorem PDF exponentiation PDF and Chinese Rem theorem Excel and exponentiation Excel format here. I like the use computers to do where possible because they are efficient ways of doing mathematics and in order to explain to a computer how to compute something, you must understand that computation yourself on some level.

I don't remember who asked to do the 3 of a kind, straight and flush in class. I'll ask you next week to fill them in. Get them done though because I had one solution already posted but not by the people who asked for them.

Oct 25 - The web server holding this web page crashed and some information on this page may have been lost. Please let me know if you notice anything missing.

I've decided not to emphasize the use of computers although I may do occasional demonstrations in class (as I did on section 3.5). The reason for this is that it takes enormous amounts of time to learn a computer language. I would like the people who do the presentation topics to consider using the computer when they think it is possible. I am willing to help in any way I can (and we can also reserve a computer lab if you want to take the whole class to do experments on the computers). If you want to learn a computer program you should take a look at the program MuPad.