аЯрЁБс>ўџ ;=ўџџџ:џџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџьЅСY ПA-bjbjѓWѓW B==A)џџџџџџ] 44444@44_ђ$&&&&&&$Q
єEИJ Jц цццV $44 $цицОтjЄ $t TэlЁrУ44цArrive ten minutes early
Write on board: Prof. Jim Propp (call me Prof. Propp in the
context of Math 491)
Write on board: http://www.math.wisc.edu/~propp/491
My goal is to inculcate two things: knowledge of the basic tools of algebraic combinatorics, and an ability to wield those tools creatively the way a researcher does. As in most math courses, youll be learning facts and mastering techniques, but youll also have opportunities to explore problems for which you havent been given all the tools yet, for which youll need to use a mix of rigorous and non-rigorous reasoning. Youll also have opportunities to communicate ideas orally and in writing.
Im excited because I love this material, and also because many of you are going to be taking these new tools and putting them to immediate use as members of SSL. (Do you all know what SSL is? ...) There are research questions Ive been curious about for the past four or five years, some of which I expect will be settled during the coming year by some of you.
Part of my contract with you is that each time we meet Ill have something new to tell you, that Ill tell it to you clearly and if possible entertainingly, and that Ill let you go by the time the bell rings.
Before I go into telling you about the mechanics of the course, let me illustrate something about the subject matter and nature of algebraic combinatorics, and give you some of the flavor of the course.
Combinatorics is about counting: permutations, combinations, and other things.
Example A: In how many ways can we divide a 2-by-4 rectangle into 1-by-2 and 2-by-1 rectangles?
Example B: In how many ways can we draw line segments pairing up the six vertices of a hexagon, so that none of the three line segments cross?
Example C: In how many ways can we divide a pentagon into triangles by drawing non-crossing diagonals?
In each case, the answer (as well see) turns out to be 5. In fact, the answers to B and C are the same 5, while the answer to A is a different 5. Well see what that means!
Algebra is about operations like addition and multiplication, and variables like x, and polynomials like x^2+2x+1. Its also about matrices (linear algebra) and groups and rings and fields (abstract or modern algebra). Well see how these kinds of algebra can be profitably applied to combinatorial problems.
Lets start by seeing how polynomials can help us understand combinations.
Pascals Triangle (go up through n=6)
Did Pascal discover it first? ... No, the Chinese did!.
Algebraic interpretation: Coefficient of x^k y^{n-k} in (x+y)^n.
Binomial theorem: For n a non-negative integer,
(x+y)^n = sum_{k=0}^n (n choose k) x^k y^{n-k}
Replace y by 1: (1+x)^n = sum_{k=0}^n (n choose k) x^k
Combinatorial interpretation: Number of combinations of n
objects, taken k at a time. Talk about I Ching hexagrams
(stress: theres no evidence that the Chinese had this in
mind!)
{n choose k} = {n choose n-k}
1. The sum of the nth row of the triangle is ...; how to prove? ...
induction
algebra (substitution: x=1, y=1) [remember this for later: the usefulness of substitution!]
combinatorics (counting all subsets)
2. What about the alternating sum of the entries in the nth row?
Observation: sum_{k=0}^n (-1)^k (n choose k) = 0 for n>0.
induction (not hard)
algebra (substitution: ... x=1, y=-1) [what about n=0?]
combinatorics (number of subsets of odd size = number of subsets of even size); whats a bijection between odd-sized-subsets and even-sized subsets? ... Signed enumeration. Breaking the symmetry by picking a class clown.
3. What about the sum of the squares of the elements in the nth row? ...
1, 2, 6, 20, 70, 252, ...
Maple: If you type sum(binomial(5,k)^ 2,k=0..5); after the
prompt, Maple says 252.
Or: f := proc(n) RETURN(sum(binomial(n,k)^2,k=0..n)); end;
and f(5);
Mathematica? ...
Handbook of Integer Sequences (mention link to Sloane from the
SSL home-page)
www.research.att.com/~njas/sequences/
Pattern hunting: ratios!
2/1 = 2, 6/2 = 3, 20/6 = 10/3, 70/20 = 7/2, 252/70 = 18/5, ...
Lets rewrite 7/2 as 14/4:
2/1, 6/2, 10/3, 14/4, 18/5, ...
Aha!
In fact, these are just the central entries in alternate rows of
Pascals triangle
So we conjecture:
sum_{k=0 to n} {n choose k}^2 = {2n choose n}.
Proof by induction? Its not easy to see where one would even
start.
Proof by algebra:
We want to prove LHS = RHS.
Well derive this from the fact that (1+x)^n (1+x)^n = (1+x)^{2n}.
Look at the coefficient of x^n in this polynomial.
On the one hand, its equal to
sum_{k=0}^n
(coeff of x^k in (1+x)^n) (coeff of x^{n-k} in (1+x)^n)
= sum_{k=0}^n (n choose k) (n choose n-k)
= sum_{k=0}^n (n choose k) (n choose k)
= sum_{k=0}^n (n choose k)^2
= LHS.
On the other hand, (1+x)^n (1+x)^n = (1+x)^{2n}, in which the
coefficient of x^n is
(2n choose k) = RHS.
You can train yourself to recognize when a trick like this will
work.
The Algebraic Strategy: To prove LHS=RHS, come up with a
polynomial that can be written in two different ways, so that
a certain coefficient can be shown to equal both LHS and
RHS.
Proof by bijection:
We want to prove LHS = RHS.
Look at the set of all ways of choosing a committee of n students
from a class of n boys and n girls.
Let k be the number of boys on the committee. What are the
possible values of k? ... 0 through n.
For each such value of k, how many committees consist of k boys
and n-k girls?... (n choose k) (n choose n-k) = (n choose k)^2.
So the total number of different possible committees is
sum_{k=0}^n (n choose k)^2= LHS.
But the number of different possible committees is also
(2n choose n) = RHS
(just ignore the sex of the students).
Ive just shown you three examples. Whats Example 4? ...
Hint: Pretend I called them Examples 1(a), 1(b), and 2(a); whats
example 2(b)? ...
Right! You should always be on the lookout for things like this.
Incomplete analogies are one of the great motors of mathematical
progress.
So, half of your homework assignment for a week from today is to
tabulate values of the alternating sum of squares, formulate a
conjecture, prove it algebraically, and prove it combinatorially.
Three components of the grade: in-class participation (10%), homework (50%), take-home exams (50%), with the lowest 10% being dropped. (No in-class tests.)
Class participation:
Attendance
Tell students I plan to start 5 (not 7 or 10) minutes past the hour (ask them to remind me what the custom is here!)
I expect you to have done the assigned reading, or the assigned skimming. This will make for a more lively class, since youll be less busy scribbling everything down; youll be able to get the big picture and ask questions.
Lots of ways to participate: answering a question (correctly or not) in a way that propels the discussion forward; asking a good question; giving a synthesis or a recapitulation. (Or, occasionally: I think Joe was trying to say something.)
The only dumb questions are the ones that dont get asked. In asking a question, you show that you know whats confusing you. Dont ridicule other students questions.
Feel free to interupt with questions. But you should also respect my decision if I feel the need to rein in the discussion (say, so that we can cover everything youll need to know in order to do the homework).
Its my hope that everyone in the class will get 100% on participation
Lets start formally, with hand-raising, and loosen up later in the semester. If I dont use your name, please say it!
What it means when I stand aside and avoid eye-contact (look at the person whos talking, not me!)
Homework:
6 hours per week of homework, on average (youll keep me on track by telling me how much time you spent on each problem on each assignment)
Some problems will call for discovery and exploration; others will call for rigorous solution
High marks for judicious use of empirical reasoning.
Computers (Maple vs. Mathematica); some programming will be involved (nothing major; ten-line programs, typically.) Do you all have access to computers? ... Do you have access to training? ... Lets help each other; let me know how I can help. East Side, West Side gives a good way to jump right into Maple; is there anything like this for Mathematica?
For some assignments, Ill want you to write code; you should email the code to me (so that I or the grader can run your program without having to type it)
Homework sets and take-homes will be graded not just on the basis of correctness but also on the basis of clarity.
Collaboration is encouraged, but try the problems on your own first, and only take what fits in your brain. Also, write down the names of people you worked with (explain how I use this).
Write down how much time you spent on each problem.
Please staple your assignments.
You can submit homework by email, but NOT in Word.
Policy on late HW: To be fair to the grader and to the students, its important that the homeworks be graded promptly and all at the same time. So Im going to be strict about deadlines. If you hand in a paper late, and for whatever reason it doesnt get to the grader in time, youll get a zero for that assignment. (Ill only make exceptions for unusual circumstances. If youve got such a circumstance, please tell me ahead of time if you can.)
Lowest 10% of homework grade is dropped. So you get one or two free excuses from doing an assignment.
Take-home exams:
Two: one due in the middle of the term (lets pick a date later this month, to suit your schedules; right now Im leaning towards a due-date of November 1), the other due at the end of Reading Period.
No collaboration with each other, but you can consult with me.
When theres a take-home, there wont be homework.
In lieu of taking the final exam, you can opt to write a research paper; advance approval of topic is required.
Prerequisites: High school algebra, linear algebra, basic combinatorics. If you know what a ring is, youll recognize lots of examples in this course; but we wont use any of the general theory of rings.
If you have suggestions about the way the course is run, let me know. Dont wait until its too late for me to change what Im doing.
Keep track of your good ideas! If you find clever alternative solutions to homework problems, or simpler proofs of the theorems we discuss, make a note of them, so that two years from now, when you ask me to write a letter of recommendation for grad school, and I ask Who are you?, youll be able to say Im the person who ...
`br -G"S"@-A-§їѓ§я§я§я§я§я§я§я§ьCJ5CJ >*CJ
56CJ CJ XmЁЂйкЅ І ѕ U
ф
Kџ7
8
Њ
т
#S§§§љ§§§§§§§§§§§§§§§§§§§§§§§љљаXmЁЂйкЅ І ѕ U
ф
Kџ7
8
Њ
т
#SКє/jqдо:_`Ёмё) RlЊФ_nь',nСТ
8{ЎЮл@h
Ысј9?yИќі№ъфо
XКє/jqдо:_`Ёмё) RlЊФ_nћљћћћљљљєєєљљљєєєљљљљћљћљљћљ
&Fаь',nСТ
8{ЎЮл@h
Ысј9?§§§§§§љ§§§§љ§§§§§§љљљљљљ§љ§§ља?yИђїј
)lЭє5uЎЯDEУеYcЅх'§љљљљ§§§љ§љ§љ§љ§љ§§ї§љ§§љ§љѓааИђїј
)lЭє5uЎЯDEУеYcЅх'(ХЦмч\>1лЏ і n!б!в!м!h"Ц"ћ"b$ќљіѓ№эъчфсоливЪТКВЊЂ|v
iјџџ sјџџtјџџ
зјџџ Oљџџ
љџџ
jњџџ
ћџџ
ќџџ
щќџџ
^§џџ
i§џџ §џџ§џџўџџўџџ`ўџџ ўџџтўџџьўџџ.џџџpџџџџџџХџџџ-'(ХЦмч\>1лЏ і n!б!в!м!h"Ц"ћ"b$ў$q%/&c&&Ж&z(с(§§§§јјјјјјјјѓ§§юююююююююююю
&F
&F
&Fb$ў$q%/&c&&Ж&z(с(т(ѓ(М)ћ).***l+m+є+ѕ+A-њєёёыхпйгЭЧС
с(т(ѓ(М)ћ).***l+m+є+ѕ+A-§§јјјј§§§§§§
&FАа/ Ар=!А"А# $ %А
[$@ёџ$NormalmH 0@0 Heading 1$@&CJ44 Heading 2$@&>*CJ<A@ђџЁ<Default Paragraph Font(U@Ђё( Hyperlink>*B*A)BџџџџA-?'с(A- Иb$A-} №§7:SVgtІГiq
T
W
v
y
Е
И
#:G)
6
ЮвъэяїNT_bn-036пфшыљўкнѓі`gщьђѕ
!$'ЪЭ%ш№U ` Х"Ч"##й&ц&m'o'C)џџJames Propp$C:\WINDOWS\Desktop\192\Lecture 1.docJames Propp2C:\WINDOWS\Desktop\Teaching\491\Lectures\09-02.docJames Propp.C:\WINDOWS\TEMP\AutoRecovery save of 09-02.asdJames Propp3C:\WINDOWS\Desktop\Teaching\491\Lectures\Sept 2.docJames Propp4C:\WINDOWS\Desktop\Teaching\491\Lectures\Sept 02.docJames Propp4C:\WINDOWS\Desktop\Teaching\491\Lectures\Sept 02.docJames Propp/C:\WINDOWS\TEMP\AutoRecovery save of Sept02.asdJames Propp3C:\WINDOWS\Desktop\Teaching\491\Lectures\Sept02.docJames Propp3C:\WINDOWS\Desktop\Teaching\491\Lectures\Sept02.docJames Propp3C:\WINDOWS\Desktop\Teaching\491\Lectures\Sept02.docF џџџџџџџџџўKН1 џџџџџџџџџvё>ѓ|hџџџџџџџџџЃ"YB џџџџџџџџџH\ џџџџџџџџџ§рl џџџџџџџџџлA n џџџџџџџџџX=x џџџџџџџџџhўЦhOJQJo(З№hўЦhOJQJo(З№а0§Цаo(()hўЦhOJQJo(и№hўЦho(()hўЦho(.hўЦhOJQJo(З№hўЦhOJQJo(З№лA nўKН1FX=xH\§рlvё>Ѓ"YBџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџ@m'm'рmdm'm'A)P@G:џTimes New Roman5Symbol3&:џArial;Wingdings"qаhё
y&@ yї"H$ЅРДД0Ц)Gџџ1Look at notes for first lectures in other coursesJames ProppJames Proppўџ
р
ђљOhЋ+'Гй0Ьиьј ,
HT
`lt|ф2Look at notes for first lectures in other coursesrookJames ProppameNormal.dotJames Propp7meMicrosoft Word 8.0i@Ј[щ@оЃ$qУ@ШdЁrУї"ўџ
еЭе.+,љЎDеЭе.+,љЎl(hpЄЌДМФ
Ь
фUW Math DepartmentHЦ)j2Look at notes for first lectures in other coursesTitle 6>
_PID_GUIDфAN{167473A0-9FC2-11D5-A227-A293FA092D7A}
!ўџџџ#$%&'()ўџџџ+,-./01ўџџџ3456789ўџџџ§џџџ<ўџџџўџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџRoot Entryџџџџџџџџ РF \%qУўlЁrУ>1Tableџџџџџџџџџџџџ"WordDocumentџџџџџџџџBSummaryInformation(џџџџ*DocumentSummaryInformation8џџџџџџџџџџџџ2CompObjџџџџjObjectPoolџџџџџџџџџџџџўlЁrУўlЁrУџџџџџџџџџџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџўџ
џџџџ РFMicrosoft Word Document
MSWordDocWord.Document.8є9Вq