> DFCY +bjbjWW R=='],,,,,8L,k 0222222$!VVBBBBn0,,0BHBr
T0@OV ,,B"TODAY:
Short recurrence for counting lattice paths by q-weight
Number partitions
Short recurrence for counting lattice paths by q-weight
Warm-up: combinatorial interpretation of
(a choose b) b = a (a-1 choose b-1)
Consequence: (a choose b) = (a/b) (a-1 choose b-1)
Put a=m+n, b=m
(motivation: counting lattice paths from (0,0) to (m,n))
Let P(m,n;1) = the polynomial P(m,n) from the homework due
today, evaluated at q=1; i.e. P(m,n;1) = the number of lattice
paths from (0,0) to (m,n).
P(m,n;1) = (m+n)/(m) P(m-1,n;1)
This is a special case of a q-version you proved in HW #10:
P(m,n) = ((1-q^(m+n))/(1-q^m)) P(m-1,n)
= ((1+q+...+q^(m+n-1))/(1+q+...+q^(m-1))) P(m-1,n)
(just send q ( 1)
Definition: [n] = 1+q+...+q^(n-1). We call this the q-analogue
of n. (Some authors prefer to define [n] as 1-q^n.)
[1], [2], [3], ... are the q-integers.
(Compare with an earlier definition of [n] as {1,...,n}. Ill continue
to use both, but it should always be clear which one I have in
mind.)
Digress for a moment: We defined P(m,n) as a sum of weights of
lattice paths, where the weight of a lattice path was defined
as q to the power of the sum of the heights of the horizontal
edges. (Give example: compute P(2,2).) Is there another
way to think about the weight? ...: q to the power of the area
under the path.
Lets find a direct proof of
(1+q+...+ q^(m-1)) P(m,n) = (1+q+...+q^(m+n-1)) P(m-1,n): Motivation: non-q version: m P(m,n) = (m+n-1) P(m-1,n)
LHS: Counts lattice paths from (0,0) to (m,n) with a marked
horizontal edge, where the area associated with such a
marked path is defined as its ordinary area plus the
x-coordinate of the left endpoint of the marked edge.
RHS: Counts lattice paths from (0,0) to (m-1,n) with a marked
vertex, where the area associated with such a marked path is
defined as its ordinary area plus the x-coordinate of the
vertex plus the y-coordinate of the vertex.
Weight-preserving bijection from LHS-objects to RHS-objects:
... Replace each marked dot by a marked horizontal edge,
shifting everything after it to the right.
Do example with (m-1,n) = (1,1), (m,n) = (2,1).
Discuss why its a bijection.
Analysis: Consider a lattice-path from (0,0) to (m,n) with weight
x^A. When you mark a vertex (i,j) on a lattice-path from
(0,0) to (m-1,n), you get a vertex-marked path of weight
x^(A+i+j). On the other hand, if you replace the marked
vertex by a marked horizontal edge, you get an edge-marked
path of weight x^(A+i+j).
Upshot: P(m,n) = ([n+m]/[m]) P(m-1,n).
Consequence: P(m,n)
= ([n+m]/[m]) ([n+m-1]/[m-1]) ([n+1]/[1]) P(0,n)
= [n+1][n+2]...[n+m]/[1][2]...[m].
P(m,n) is a reciprocal polynomial, i.e., one whose coefficients read
the same forwards as backwards. Why? ... Rotating a lattice
path by 180 degrees turns a path of area k into one of area
mn-k.
Why do we have P(m,n) = P(n,m) ? ... flip over diagonal joining
(m,0) and (0,n).
If we define [k]! = [1][2]...[k], we can write
P(m,n) = [m+n]!/[m]![n]!.
Fun problems to study (due a week from today):
How many lattice paths in the m,n rectangle remain the same when
you flip them across the diagonal joining (n,0) and (0,n)?
What is the sum of their q-weights?
One thing thats nice about guessing formulas for products of
q-integers is that there are more clues to what the relevant
factorization: 12 can be factored as 2 times 6 or 3 times 4
or even 2 time 2 times 3, but [2][6], [3][4], and [2][2][3]
are distinct polynomials. (Check:
[2] [2] = (1+q)(1+q) \not\eq 1+q+q^2+q^3 = [4].)
One tricky thing, though is that [m] often factors; e.g.,
[4] = (1+q)(1+q^2) = [2](1+q^2)
[6] = [2][3](1-q+q^2)
When youre doing the homework problem thats due next
Thursday, you will find it helpful to rewrite 1+q^2 as [4]/[2],
1-q+q^2 as [6]/[2][3], etc.
Number Partitions
A partition of the positive integer n is a way of writing n as a sum
of one or more positive summands, where order doesnt
matter.
Thus, the number 4 has 5 partitions:
1+1+1+1
1+1+2=1+2+1=2+1+1
1+3=3+1
2+2
4
The summands are called parts, and its usually convenient to
write them either in weakly ascending OR weakly
descending order. (Discuss what I mean by weakly.)
By convention, we say that the number 0 has one partition, the
empty partition.
We let p(n) be the number of partitions of n. Thus
p(0) = 1, p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7,
p(6) = 11, [...] p(7) = 15, ...
Theres no simple exact formula for p(n), though there is an
awesomely complicated one due to Hardy and Ramanujan,
and there is a beautiful and simple form for the generating
function of this sequence.
We can represent a partition by a diagram of dots, called a Ferrers
diagram, or by a diagram of boxes, called a Young diagram:
____________
o o o o o |__|__|__|__|__|
5+3+2 (5,3,2) o o o |__|__|__|
o o |__|__|
(This is the English style; the French flip their Ferrers and Young
diagrams into the first quadrant.)
Put origin at lowest left vertex.
If a partition has B parts, and the largest part is A, then the Young
diagram has a boundary that consist of three parts: a straight
path from (0,0) to (0,B), a straight path from (0,B) to (A,B),
and a NE, SE, lattice path from (0,0) to (A,B) that begins
with an E-step and ends with an N-step.
If we drop the constraint that the lattice path has to begin with an
E-step and end with an N-step, we get all the partitions with at most B parts, and with each part of size at most A.
Show how the partition (2,1) fits inside this diagram.
These are precisely the partitions whose Young diagram fits inside
an A-by-B rectangle.
The number of such partitions equals the number of lattice paths
from (0,0) to (A,B), namely (A+B)!/A!B!.
What if we want to q-count the partitions?
But wait: we already have!
(Discuss; point out that were complementing, but that it doesnt
matter, because of the symmetry.)
Theorem (already proved): The number of partitions of n with at
most B parts, each of size at most A, is equal to the
coefficient of q^n in the polynomial [A+B]!/[A]![B]!
These polynomials are called the Gaussian polynomials, or the
q-binomial coefficients.
What happens when A or B goes to infinity, or both of them do?
Write [A+B]!/[A]![B]! = ([A+1]/[1])([A+2]/[2])...([A+B]/[B])
= ((1-q^{A+1})/(1-q)) ((1-q^{A+2})/(1-q^2)) ...
((1-q^{A+B})/(1-q^B))
If B goes to infinity, this goes to 1/(1-q)(1-q^2)...(1-q^A).
Consequence: The number of partitions of n into parts of size at
most A is equal to the coefficient of x^n in the formal power
series 1/(1-q)(1-q^2)...(1-q^A).
Note direct proof.
More generally: if S is any subset of the positive integers, the
number of partitions of n into parts belonging to S equals the
coefficient of x^n in the (finite or infinite) product
prod_{k in S} 1/(1-q^k).
E.g., if a_n is the number of partitions of n into 2s, 3s, and 5s,
then sum_{n ( 0} a_n x^n = 1/(1-q^2)(1-q^3)(1-q^5).
This is a rational function, so you should remember what youve
learned about rational generating functions.
What can you say about an exact formula for a_n = the number of
partitions of n into 2s, 3s and 5s? ...
It is a ``quasi-polynomial function (discuss) of n, of the form
f(n) = C_n n^2 + D_n n + E_n
where C_n, D_n, and E_n are periodic mod (2)(3)(5).
Equivalently, f(n) = p_n (n) where p_1, p_2, ... is a periodic
sequence of degree-2 polynomials with period 30.
The g.f. 1/(1-q)(1-q^2)...(1-q^m) also counts partitions with at
most m parts.
Partitions with exactly m parts:
1/(1-q)...(1-q^m) 1/(1-q)...(1-q^{m-1}
= q^m/(1-q)...(1-q^m).
Mention bijective proof, too.
Partitions with largest part m: also q^m/(1-q)...(1-q^m).
Mention bijective proof.
Take A,B both to infinity: The generating function for partitions
with no constraints is 1/(1-q)(1-q^2)(1-q^3)...
Discuss why this makes sense.
The generating function for partitions into distinct parts is
(1+q)(1+q^2)(1+q^3)...
Discuss.
The generating function for partitions into distinct parts with
exactly m parts is
q^{1+2+...+m} / (1-q)(1-q^2)...(1-q^m).
Discuss.
Theorem (Euler): The number of partitions of n into distinct parts
equals the number of partitions of into odd parts.
Algebraic proof: (1+x)(1+x^2)(1+x^3)(1+x^4)...
1-x^2 1-x^4 1-x^6 1-x^8
= --------- --------- -------- --------- ...
1-x 1-x^2 1-x^3 1-x^4
= 1/(1-x)(1-x^3)(1-x^5)(1-x^7)...
Bijective proofs are also known.
Good challenge: find one!
The coefficient of x^n in (1+x^2)/(1x^3) is the number of
partitions of n into parts of size 2 and 3, where the part
of size 2 cannot be repeated. Call it a_n.
The coefficient of x^n in (1-x^3)/(1+x^2) is the sum of the weights
of all the partitions of n into parts of size 2 and 3, where
the part of size 3 cannot be repeated, where the weight of a
partition is -1 to the power of the number of parts. Call the
coefficient b_n.
Claim: For n > 0, sum_{k=0}^n a_k b_{n-k} = 0.
Algebraic proof: Same as in last problem of midterm.
Good challenge: Find a bijective proof.
The long recurrence relation for p(n):
p(n) = p(n-1) + p(n-2) p(n-5) p(n-7) + p(n-12) + p(n-15)
p(n-22) p(26) + p(n-35) + p(n-40) + + ...
Equivalently:
Eulers pentagonal number theorem:
(1-x)(1-x^2)(1-x^3)...
= sum_{n in Z} (-1)^n q^{3n(n+1)/2}.
Explain why its equivalent.
Franklins bijective proof:
Assign a partition with distinct part weight (-1)^k, where k is
the number of parts, so that the coefficient of x^n in the
LHS is the sum of the weights of the partitions of n into
distinct parts.
Say a partition with distinct parts is pentagonal if the parts are
m+1,m+2,...,m+n with n=m or m+1.
Claim: For all n, the sum of the weights of all the non-pentagonal
partitions of n into distinct parts equals 0.
Very tricky exercise: Find a sign-reversing involution. (The details
are in just about any treatment of partitions you could find.)
Give details, if time permits and the students desire.
RUU *wbw+<=DOq}~.7< E !!)"B"""#-#6###&%@%V'~'((\**+
jCJ 6CJ CJ j6>*5D?QRUHp.U$c$1$$1$?QRUHp.U$c 0 1 O 5
k
[*Zy0
j
3V]n)fC0G6ox<rb 0 1 O 5
k
[*Zy0
j
$1$$1$3V]n)fC0G$1$$1$6ox<r6W $h1$1$$1$r6W $h[~'gY.o3rs7y.n<| X w !!`!n!!!!!)"B"C""""#-#6#v######2$a$$$$%&%@%A%}%%a[~'gY.o1$1$1$1$$1$$1$$1$1$1$3rs7y.n<| X w !!1$1$1$1$!`!n!!!!!)"B"C""""#-#6#v######2$a$$$$%&%1$1$1$1$&%@%A%}%%%(&e&&&&!'V'~''''($(G(_(((((9)t)
&F1$1$1$1$%%(&e&&&&!'V'~''''($(G(_(((((9)t))))-*\***+ t))))-*\***+/ =!"#$%
[$@$NormalmH HH Heading 1$<@&5CJKHOJQJFF Heading 2$<@&56CJOJQJ0@0 Heading 3$@&CJ 4@4 Heading 4$@&5CJ 4@4 Heading 6$@&6CJ <A@<Default Paragraph Font.B@. Body Text6CJ .P@.Body Text 2CJ 'R+!&%t)+ !#$%&(r%+"'_Hlt55846731Q'Q'OR[`ux@BJMX[ad&)dgwzLOmv3 8
C
F
X
[
.17:
?D`gHO`chkvy|z}14}adknsv~"%;>#&1:HK!!U!X!!!!!""##m#v#$$+$$$.%1%:%=%%%%%%%'James Propp(C:\WINDOWS\Desktop\192\Lecture 11-01.docJames Propp(C:\WINDOWS\Desktop\192\Lecture 11-01.docJames Propp(C:\WINDOWS\Desktop\192\Lecture 11-01.docJames Propp(C:\WINDOWS\Desktop\192\Lecture 11-01.docJames Propp)C:\WINDOWS\Desktop\491\Lectures\Nov13.docJames Propp)C:\WINDOWS\Desktop\491\Lectures\Nov13.docJames Propp+C:\WINDOWS\Desktop\491\Lectures\Stephen.docJames Propp0C:\WINDOWS\TEMP\AutoRecovery save of Stephen.asdJames Propp0C:\WINDOWS\TEMP\AutoRecovery save of Stephen.asdJames Propp"C:\WINDOWS\Desktop\491\Stephen.docHfPFaa
O!'c&E|}~6y0o(()88o( VzVo(.o( HfE|}O!'caa@$'p@GzTimes New Roman5Symbol3&zArial"qhv0{tX{F"> DY0d'"Catalan numbers and triangulationsJames ProppJames Propp
Oh+'0|
8D
P\dlt#Catalan numbers and triangulationssataJames ProppameNormal.dotJames Propp3meMicrosoft Word 8.0 @L@42@h%N >
՜.+,D՜.+,`hp
UW Math DepartmentD'j#Catalan numbers and triangulationsTitle 6>
_PID_GUIDAN{CDF78C40-C409-11D5-A227-FC66FBA8D947}
!"#$%&'()+,-./012456789:<=>?@ABERoot Entry Fp@FhV G1Table*WordDocumentRSummaryInformation(3DocumentSummaryInformation8;CompObjjObjectPool@FhV @FhV
FMicrosoft Word Document
MSWordDocWord.Document.89q