╨╧рб▒с>■ ')■ & ье┴Y ┐Ф
bjbjєWєW С=С=Ф ]▓▓▓▓▓▓▓╞╞╞╞╞╥╞┼ЄЄЄЄЄЄЄЄЄКММММММ$╖ЇлЇ░▓ЄЄЄЄЄ░°▓▓ЄЄЄ°°°Є▓Є▓ЄК╞╞▓▓▓▓ЄК°&°·Їl▓▓КЄц@D~█┐Т├╞╞°`*Any questions about the homework or the material?
Homework: Assignment #10, problem 1 and assignment #11 are due on Tuesday; assignment #10, problem 2 is due on Thursday.
The take-home exam (which I will make available Tuesday) will be due the following Tuesday (Oct. 28). If youТre finding any of the material difficult, now is the time to see me and get help.
TODAY:
Graph theory: perfect matchings and spanning trees
Ballot sequences and Catalan numbers
Perfect matchings and spanning trees
A graph G is a collection V of vertices together with a collection E of edges, where an edge is an (unordered) pair of vertices.
E.g.: G = (V,E) where V = {a,b,c,d}, E = {{a,b}, {b,c}, {c,d}, {d,a}}. [Sketch it in three ways.] All three pictures are the same abstract graph.
How many of you have seen this before?
A perfect matching of a graph is a set EТ of edges such that each vertex belongs to exactly one edge in EТ.
The graph G shown above has Е two perfect matchings: {{a,b},{c,d}} and {{b,c},{d,a}}.
What about the 2-by-3 grid? Е The 2-by-4 grid? ...
Perfect matchings of the m-by-n grid graph are Уthe sameФ as domino tilings of the m-by-n rectangle.
A spanning tree of a graph is a set EТ of edges such that any two vertices of G are joined by a unique path in EТ.
The graph G shown above has Е four spanning trees (sketch).
What about the 2-by-3 grid? Е Fifteen.
(This will get you started on the second problem on the assignment, which IТve also postponed until next Thursday.)
Ballot sequences and Catalan numbers
HereТs an important application of the addition and multiplication principles:
Q: How many sequences of n +1Тs and n Ц1Тs are there, such that the partial sums are all non-negative 0?
A: C_n, the Уnth Catalan numberФ
C_0 = C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42, ...
The Catalan numbers come up as often as Fibonacci numbers.
Note rephrasings:
How many lattice paths from (0,0) to (2n,0), with steps (+1,+1) and (+1,-1), never go below the line y=0? (These are sometimes called Dyck paths.)
How many lattice paths from (0,0) to (n,n), with steps (0,1) and (1,0), never go below (or above) the line y=x?
How many sequences of n+1 +1Тs and n Ц1Тs are there, such
that the partial sums are all positive?
If candidate A got 1 more vote that candidate B, in how many orders can the ballots be read so that candidate A is always ahead? (We arenТt distinguishing among the A-ballots or among the B-ballots.)
╬єЎ√ 02BЄЛОЫ1 Y c ╫ ╪ ■ PMWФ
¤¤√¤√¤√√¤√√6Б>*23мlmtuи═╬єЇu 0ЬЄ%ЛМ ; b c ╫ ╪ ¤ ■ M
¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤23мlmtuи═╬єЇu 0ЬЄ%ЛМ ; b c ╫ ╪ ¤ ■ M
N
╣
┌
PbЎfв╩У
Ф
№∙єэ
)M
N
╣
┌
PbЎfв╩У
Ф
¤¤¤¤¤¤°єєяє¤Д╨
&F
&F░╨/ ░р=!░"░#Ра$Ра%░
[(@ё (NormalCJ mH ,@, Heading 3$@&0@0 Heading 4$@&6Б0@0 Heading 6$@&6Б<A@Є б<Default Paragraph Font*B@Є* Body Text6Б(U@в( Hyperlink>*B*8V@в8FollowedHyperlink>*B*Ф Ф
M
Ф
Ф
ЛФ╓▀АГРЧагзко▒╡╕╞╧╙╓┘▄хшыю-6ip╝┐=FU`щэadЦ James Propp)C:\WINDOWS\Desktop\491\Lectures\Oct14.docJames Propp)C:\WINDOWS\Desktop\491\Lectures\Oct14.docJames Propp)C:\WINDOWS\Desktop\491\Lectures\Oct14.docJames Propp.C:\WINDOWS\TEMP\AutoRecovery save of Oct14.asdJames Propp.C:\WINDOWS\TEMP\AutoRecovery save of Oct14.asdJames Propp)C:\WINDOWS\Desktop\491\Lectures\Oct14.docJames Propp)C:\WINDOWS\Desktop\491\Lectures\Oct16.docJames Propp)C:\WINDOWS\Desktop\491\Lectures\Oct16.docJames ProppC:\WINDOWS\Desktop\Oct16.ps.docJames ProppC:\WINDOWS\Desktop\Oct-16.docFЮ d}iТ╦╨[ ░K─#╚с"ъ c%╧pу ╠x`1кfЮх ■K╜1 ЗAШ94ь vё>є|h ╓╥?bы<А г"YB k'ёZр╛┴ H\ "0t_PфЕ ╝9╛cрc ╡wkт$ьХ ¤рl █Aаn X=x ДhДШ■╞hOJQJo(╖ЁДД`·╞o(ДД`·╞o(Д╨Д0¤╞╨o(()Д╨Д0¤╞╨o(()ДhДШ■╞hOJQJo(╖ЁДД`·╞o(Д╨Д0¤╞╨o(()Д╨Д0¤╞╨o(()ДhДШ■╞hOJQJo(╪ЁД╨Д0¤╞╨o(()ДhДШ■╞ho((),Д╨Д0¤╞╨o(Д8ДШ■╞8o(-Д╨Д0¤╞╨o(()ДhДШ■╞ho(.ДhДШ■╞hOJQJo(╖ЁДhДШ■╞hOJQJo(╖Ё╓╥?╡wk╠x`1█Aаn■K╜1FЮX=xH\¤рlvё>г"YB░K─#ЗAШ9d}ik'ёZc%╝9╛c"0t_ @АУ У └▌dУ У Ф А@GРЗ: Times New Roman5РАSymbol3&РЗ: Arial;РАWingdings"qИ╨hzuzFzuzFёyFbх$е└┤┤А0d▒ <C:\Program Files\Microsoft Office\Templates\sixteenpoint.dotFormal power seriesJames ProppJames Propp■
рЕЯЄ∙OhлС+'│┘0ИРШ┤└╘р№
8DP
\hpxАфFormal power seriesormJames Proppamesixteenpoint.dotesJames Propp2meMicrosoft Word 8.0@@1 )З├@─╗┬┐Т├@─╗┬┐Т├bх■
╒═╒Ь.УЧ+,∙оD╒═╒Ь.УЧ+,∙оPhpМФЬдм┤╝─
╠ьфUW Math Department▒ jFormal power seriesTitleШ 6>
_PID_GUIDфAN{D6192561-AA77-11D5-A227-C7476C1BAA7B}
■
■ ■ !"#$%■ ¤ (■ ■ ■ Root Entry └F└ ;█┐Т├
П█┐Т├*А1Table ЯWordDocument SummaryInformation( DocumentSummaryInformation8 CompObj jObjectPool
П█┐Т├
П█┐Т├ ■ ■
└FMicrosoft Word Document
MSWordDocWord.Document.8Ї9▓q