MATH 172 Combinatorics (Spring 2004):

Instructor: Alexander Yong, 1035 Evans Hall, ayong@math.berkeley.edu

Lectures: Tuesdays and Thursdays 3:30-5:00PM, 7 Evans

Office hours: Tuesdays 2-3 PM and Thursdays 5-6 PM

Required Text: None, but we will draw from various sources (see the recommended list below).

Other recommended texts:

1. R.P. Stanley "Enumerative Combinatorics I"

2. R.P. Stanley "Enumerative Combinatorics II"

3. D. Stanton and D. White "Constructive combinatorics"

4. R. Brualdi, "Introductory Combinatorics"

Grading: homework (30%), special problem set (30%), final exam (40%)

Homework: Students will be expected to do several problem sets. Four of these will be "regular" problem sets, to be handed out. Also, there will be two "special" problems sets where you are expected to turn in 3 "SPECIAL PROBLEMS" (see below) each. Which special problems you do is up to you. The first special problem set will be due the week of March 4th. The second will be due the last week of class. Feel free to come to me to talk about the problems. I should also make a note about "EASY" vs. "MEDIUM" vs "HARD" in the accessment of the problem's difficulty. This is of course subjective, but here's a guideline: "EASY" means that given that you have two months to work on it, if you are in touch with the course material you should be able to solve it. "MEDIUM" is like easy, but you might have to try a bunch of different things and really get your hands dirty to solve the problem. I reserve "HARD" for problems that I really do think are hard. Special problem 5 below is an example. The only bijection I know that solves this is pretty involved. But maybe an easy bijection is out there to be found (by you). Of course I will also give "X-Y" problems where X and Y are each one of the above designations.

Homework 0: Send me an email about you and your (mathematical) background so I can get to better know you.

Exams: Take Home Final.

Prerequisites: No specific prerequisites, however exposure to courses such as abstract algebra (Math 113) will be helpful. This will be an advanced undergraduate course on combinatorics.

Syllabus: Combinatorial methods are applied widely throughout mathematics; this class will be an introduction to various aspects of combinatorial theory. Some sample topics include: generating series, graph theory, poset theory, combinatorics of trees (parking functions, Catalan numbers, matrix-tree theorem), tableaux and the symmetric group (permutation statistics, the Schensted correspondence, hook-length formula), partitions, symmetric functions (elementary, monomial, power-sum, Schur polynomials, Kostka coefficients, the Littlewood-Richardson rule).

Outline: This course will focus on combinatorial problems, tied around the concept of the "generating series". We will spend the ~5 weeks on introducing generating series, ordinary and exponential generating series, the basic lemmas that allow us to use generating series to solve enumerative combinatorial problems. Then we will spend ~4 weeks on some classical combinatorial results: e.g., the Prufer correspondence, Schensted correspondence, the hook length formula, the matrix tree theorem, permutation statistics. Finally we will study the theory of symmetric functions for ~4 weeks.


Part I: Preliminaries:

Lecture 1: We talked a little about the things that will come up in the course. This class will be about enumeration: counting combinatorial objects. Moreover, the main tool/theme will be using generating series (and bijections) to do this (we will talk more about formally in the classes to come). Typical problems include:

(1) Enumerating sequences from the alphabet {1,2,...,m} of length n with p descents.

(2) Enumerating families of nonintersecting lattice paths.

(3) Enumerating linear transformations of a vector space (over a finite field) to itself whose kernel contains some given subspace.

A major part of the course (closer to the end) will be the theory of symmetric polynomials, which are all polynomials invariant under the natural action of S_{n}, the symmetric group. There is a nice basis of Schur polynomials. We spoke about the Littlewood Richardson rule and its applications to other areas of mathematics (representation theory and algebraic geometry, but in very sketchy terms). At the end we were working towards describing the so called Schubert problem. In doing so the following problem came up:

SPECIAL PROBLEM 1: Prove that the Symmetric group S_n has a presentation given by generators s_1,s_2,...,s_{n-1} subject to the relations (s_i)^2=1 (1=the empty word, or the identity), s_i s_j = s_j s_i if |i-j|>1, and s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}.

Finally, here is the first day survey (PDF file) . I should emphasize that starting the next class, we will very much work from the beginning.

Lecture 2: We finished off discussing some motivations for studying combinatorics by describing the Schubert problem. Along the way we talked a lot about the symmetric group. Typically one learns about S_{n} in terms of "two line notation" or "cycle notation". There is another way to think about it, as generated by simple relfections s_{i}=(i i+1), that is the permutation that interchanges i and i+1. In fact this suggests the way to define the isomorphism that solves SPECIAL PROBLEM 1. We talked more about "words" for a permutation w (expressions for w as a product of s_{i}'s). Of course, using the "commutation relations" given in that problem, we can morph one word into another. There are then two sets of words for a permutation w we could be interested in: (1) the set of _minimal length_ words for w, and (2) the set of _reduced_ words for w, i.e., words that cannot be made any shorter by the relations.

SPECIAL PROBLEM 2: Fix a permutation w in S_n. Prove that the set of minimal length words for w is the same as the set of reduced words for w. Also prove Tits' lemma: any two reduced words can be derived from one another via the commutation moves.

We also defined divided difference operators. An exercise is to show that they satisfy the relations that the s_i do. In fact here's an:

OPEN PROBLEM: Find all possible "minimal" relations between the divided difference operators.

(NOT TOO HARD) SPECIAL PROBLEM 3: Prove that the _Schubert polynomial_ \S_{w} defined by the divided difference operators does not depend not change when you view w in S_n or S_{n+1} under the natural embedding. (For this one you should just absorb the definitions from class and work out some examples.)

We asserted that these polynomials form an integeral linear basis of the ring of all polynomials (in Z[x_1,x_2,...]). So \S_u*\S_v = sum_{w} C_{u,v}^{w} \S_{w} for some integer coefficients C_{u,v}^{w}. In fact, it is known these are nonnegative:

FAMOUS OPEN ("SCHUBERT") PROBLEM: Give a combinatorial proof of the nonnegativity of C_{u,v}^{w}. Also, give a combinatorial counting formula for what they count.

Having discussed some uses and problems in enumerative combinaotrics, we then moved on to the formal part of the course. We defined the "enumerative problem" c(n) defined by the pair (S,w) where S is a combinatorial object and w is a weight function. This gives rise to an _ordinary generating series_ [(S,w)]_{o} such that the coefficient [x^n] [(S,w)]_{o}=c(n) -- hence our interest. We described some basic properties of the ring of formal power series to which these generating series belong.

(EASY) SPECIAL PROBLEM 4 When does a generating series have an inverse? What is that inverse?

Our goal will to explain how to decompose a given combinatorial set (S,w) to another set (S',w') which is easier to enumerate.

Lecture 3: We talked more about bijections. The basic point being that if two sets A and B have the same (finite) cardinality, then there must exist a bijection, a one-to-one and onto map that explains this. Basic combinatorial question: find that bijection!

Perhaps you are not a purist: i.e., you demand such a bijection to verify an equality of cardinalities. In that case, bijections will be mainly applied in this course to decompose a hard combinatorial problem into easier chunks that can be managed. Or perhaps to "rephrase" a problem into a different language where a question is easier. Ask for examples of this as we go through the course, i.e., ask yourself/me "what advantage does this bijection provide for the combinatorial problem that we are dealing with?"

We also introduced "elementary counting lemmas". The analogy with calculus' sum, product, chain rules is not bad: if you want to differentiate some complicated function, first decompose it into a sum/product/composition of functions which you can differentiate, then apply the rules. What we will do is similar: if you cannot find a generating series for a combinatorial set, decompose it into disjoint unions or cartesian products of things you can do, then apply the sum/product lemmas (you may ask if there is an analogue of the chain rule--just wait!).

We also gave examples of applying these lemmas, to plane planted trees and to partitions.

(HARD) SPECIAL PROBLEM 5 Give an explicit bijection that proves that the number of standard Young tableaux of shape (n,n-1,n-2,...,3,2,1), i.e., a staircase shape, equals the number of "balanced" tableaux of the same shape. (Reference: Problem 7.21 in Stanley EC II).

(MEDIUM) SPECIAL PROBLEM 6 (EC I, pg 46 Q 16) Let S(n,k) denote a Stirling number of the second kind. The generating function \sum_{n} S(n,k)x^n= x^{k}/(1-x)(1-2x)...(1-kx) implies the identity S(n,k)=\sum 1^{a_1 - 1} 2^{a_2 - 1}...k^{a_k - 1}, the sum being over all compositions a_1+a_2+...+a_k = n (i.e., all nonnegative integer solutions to this linear equation). Give a bijective proof of this fact. That is, associate with each partition P of [n]={1,2,..,n} into k blocks a composition a_1+...+a_k = n such that exactly 1^{a_1 - 1} 2^{a_2 - 1}...k^{a_k - 1} paritions P are associated with the partition.

(EASY) SPECIAL PROBLEM 7 (EC I, pg 49 Q16) A permutation a_1...a_n of [n] is _indecomposible_ if n is the least positive integer j for which {a_1,...,a_j}={1,2,...,j}. Let f(n) be the number of indecomposible permutations of [n], and set F(x)=\sum_{n>=0} n! x^{n}. Show that \sum_{n>=1} f(n)x^{n} = 1 - F(x)^{-1}.

Lecture 4: Talked about partitions and Ferrers shapes and proved some generating series identities of Euler-Gauss via combinatorial arguments (i.e., decompositions of Ferrers shapes). Here is Assignment 1 which is not due until February 18th, 2004.

SPECIAL PROBLEM 8 Give an explicit bijection between R_{2,3,5} and R_{2,3,6,9,10 mod 12}.

SPECIAL PROBLEM 9 (EASY) Generalize the algebraic argument in class that proves R_{2,3,5} and R_{2,3,6,9,10 mod 12} have the same generating series as far as you can.

Lecture 5 Continued talking about the proofs of some classical Euler-Gauss identities. The idea for all of them is the same. Take a Ferrers diagram for a partition of a certain type that is "obviously" enumerated by one side of the identity, and start manipulating it until you get a Ferrers shape (or a _collection_ of Ferrers shapes) that is "obviously" enumerated by the right hand side of the identity. OK "obviously" is sometimes a bit of a stretch in the sense that we sometimes have identities where we've eliminated the middle man to make an identity of the form "Weird thing I"====via bijection==== "Well known thing"=====via another bijection====="Wierd thing II" into "Weird thing I" = "Weird thing II". But the point is that this is easy too, if you know what the "Well known thing" middle man is.

So continuing this philosohy, I showed you more examples of basic decompositions of Ferrers shapes. I also talked about compositions and their generating series (which might be helpful for the Special problems above).

I also mentioned a free book by Herb Wilf called Generatingfunctionology . This book contains a bunch of things we are/will be talking about.

Lecture 6 We mainly spent the lecture talking about the refinement principle which among other things allows us to prove some more classical Euler-Gauss identities. The basic example is this: thus far, given a partition we've looked only at one enumerative statistic, namely the size of the partition (i.e., the number of dots in the Ferrers' shape). However, a partition contains a lot more information, for example the number of (nonzero) parts it has (i.e., the number of rows in the Ferrers shape). Let's think about the generating series for partitions that records both statistics, where x will mark the number of dots (partition size) and z will mark the number of rows (number of parts). Ok then the generating series for all partitions is $\prod_{k=1}^{\infty} (1-zx^{k})^{-1}$. Why is that? Well the product is equal to (1+zx+z^2 x^2 + z^3 x^3+...)(1+zx^2 + z^2 x^4 + z^3 x^6+...)(1+zx^3 + z^2 x^6 + z^3 x^9+...).... Let me rewrite it as (1+zx^1 + z^2 x^{1+1} + z^3 x^{1+1+1}+...)(1+zx^2 + z^2 x^{2+2} + z^3 x^{2+2+2}+...) (1+zx^3 + z^2 x^{3+3} + z^3 x^{3+3+3}+...) by "remembering" what the exponent means (a bunch of 1's, 2's 3's etc). Now expand a few terms. What you are doing is precisely "building" a partition. For example, multiplying the 2nd, 3rd and 2nd terms of the above product you get (zx^1)*(z^2 x^{2+2})*(z x^{3}) which is z^4(x^{1+2+2+3}) which marks the existence of the partition 1+2+2+3 of 8. What's that z^4? It marks the fact that the partition had 4 parts. Can you see why this works in general?

Lecture 7 We went over the first part of the proof of the Jacobi triple product identity. Next class we'll verify that the mapping that we gave is reversible.

SPECIAL PROBLEM 10 (MEDIUM-EASY) From the Jacobi Triple Product identity prove that \prod_{i\geq 1} (1-q^{i})^{3} = \sum_{k\geq 0} (-1)^{k}(2k+1)q^{k(k+1)/2}. Here are hints to the steps you can use: (a) Deduce from the Jacobi triple product identity that \prod_{m\geq 1} (1-q^{2m+1}y)(1-q^{2m-1}y^{-1})(1-q^{2m})=(1-qy)^{-1}\sum_{i=-\infty}^{+\infty} (-y)^{i}q^{i^{2}}. (b) This series is a formal power series in q with coefficients in Q[y,y^{-1}]. Therefore expand the RHS in the form 1+\sum_{m\geq 1} c_{m}(y)q^{m} where c_{m}(y) is in Q[y, y^{-1}]. (c) Set y=q^{-1}, justify this substitution and simplify carefully. (d) Observe that, with this substitution, the lefthand side is \prod_{i\geq 1}(1-q^{2i})^{3}. (Incidently, if all this "LaTex" notation is unfamiliar to you, please come and ask. As a side note, it wouldn't be a bad time to learn LaTex.....)

Lecture 8: Finished the bijective proof of the Jacobi Triple Product identity. During which we digressed to talk about how to approach and write up combinatorial problems. Emphasis was put on **finding the right statement** of what you want to prove, and organizing your argument so that the lemmas and thus your theorem almost "proves itself". We illustrated this point when discussing the proof of the weight preserving properties of the bijection. We formulated the Euler pentagonal number theorem and began to give a proof, using the Jacobi Triple product identity. The big question in class was why it was justifiable to make those change of variables in the generating series?

Lecture 9: Finished the proof of the Euler Pentagonal number theorem. We also proved an amusing identity about the function \sigma(n)="sum of the positive divisors of n that are greater than or equal to 1". We then moved onto the next part of the course: labelled structures and exponential generating series. We gave examples of labelled structures. We worked towards the basic yoga of exponential generating series: a fancier version of the product lemma: the "star"-product lemma. In particular, this lemma explains why we do that weird thing of having to extract the coefficient of [x^{n}/n!] from an exponential generating series to get the desired enumerative number, rather than just extracting [x^n], which is what we have done in our work with ordinary generating series.

Lecture 10: Went more formally into the ideas surrounding exponential generating series. Examples of problems related to exponential generating series: counting the number of labelled trees (satisfying some conditions), counting the number of dearrangements, counting the number of mxn matrices with all entries from {0,1} such that no row or column contains only 0's. We also talked about counting "alternating sign matrices". We slowly moved up to the definition of the "star"-product and the "star"-product lemma. Here is Assignment 2 which is not due until March 18th, 2004. It also contains two SPECIAL PROBLEMS (11 and 12). I don't think that we have covered all the material in class to solve all the problems, but I think it's worthwhile having something to chew on while we talk about exponential generating series in class.

Lecture 11: We went over exponential generating series in closer detail, and proved the product lemma.

Lecture 12: Now that we're done talking about what _multiplying_ exponential generating series means, let us move onto _composing_ generating series. The main way in which this algebraic operation makes sense in what we do concerns the situation when we view some labelled object A as an ordered "O" (or unordered "U") collection of some "smaller" labelled objects "B". Then [(A,w_a)]_{e}=[(O,w_o)]_{e} composed with [(B,w_b)]_{e} (in the ordered case) and [(A,w_a)]_{e}=[(U,w_o)]_{e} composed with [(B,w_b)]_{e} (in the unordered case). The point is that [(O,w_o)]_{e} = 1/(1-x) while [(U,w_o)]_{e}=e^{x}. We did some examples: for many involutions are there in the set of permutations on n letters? How many surjections are there from {1...n} to {1...m}? Armed with the ideals from this class, you should be able to begin attacking all the problems in assignment 2.

Lecture 13: Talked more about the compositional lemma. It's a bit of a confusing topic. The point is that we need to carefullt define the combinatorial object A (.) B which is counted with the generating series [A(.)B,t]=[A,s]([B,t]) <-- composition of generating series. Here A and B are labelled combinatorial objects having s and t subobjects respectively. The object A(.)B has each s-object of A replaced by an element of B. Thus the subobjects of A(.)B are t. Furthermore, we assume that this operation of replacement is done bijectively, in all possible ways, with all possible (disjoint) labellings of the t-subobjects of B and in fact A(.)B.

The point then is that if one can "canonically" decompose a labelled combinatorial object into the form A(.)B where A and B are "easy to enumerate", we then have an easy enumeration of the original object.

Further discussion may be found in Stanley's ECII text (first few pages). We gave more examples of its use, including the computation of the number of surjections from $N_n$ to $N_m$. Vedran also explained how the same result can be derived via inclusion-exclusion.

(EASY) SPECIAL PROBLEM 13: Finish the proof of the compositional lemma from class, by interpreting the expansion of the generating series (or otherwise). Include complete hypotheses and conclusions, and explain in detail where the hypotheses get used. Take this problem as an opportunity to "teach me" about the lemma. Include carefully explained examples of its use (even if they are from class). I'm hoping that doing this problem will make clear the discussion in class, which admittedly is of a confusing topic.

Lecture 14: We went through more examples of using the compositional lemma. The main fact we proved is that the exponential generating series F for the number of rooted labelled trees on n vertices satisfies F=x*exp(F). This functional equation is solved via the Lagrange inversion theorem. To state this theorem we needed to go through the definition of compositional inverse. After a weird proof of the Lagrange inversion theorem, we found that the number of rooted labelled trees on n vertcies is n^{n-1}. Since the number of labelled trees (without root) on n vertices is (1/n)*[number of rooted lablled trees], that number is n^{n-2}.

Lecture 15: Talked more about trees and stated some problems for Assignment #3 (upcoming): such as proving the Prufer correspondence is a bijection, various things counted by Catalan numbers (don't forget the talk on Catalan numbers by Alexander Woo in 1015 Evans at 1:10 this Wednesday), factorizations of the long cycle. Another combinatorial story that we started on was thinking of functions in terms of their functional digraph (another application of the compositional lemma). We worked on an enumerative problem related to this.

Lecture 16: Another combinatorial story that we started on was thinking of functions in terms of their functional digraph (another application of the compositional lemma). We worked on an enumerative problem related to this: what is the expected number of cycles in the functional digraph of a function from N_n -> N_n. Uri Andrews noticed a very easy solution that avoids the generating series stuff that I wanted to use.

Lecture 17: Assignment 1 was handed back, and we talked about the solutions. I also described the following amusing

(FUN) SPECIAL PROBLEM 14: Here's a card trick done by two people, you and your assistant. Your assistant draws 5 cards from a deck and shows them to the audience (and himself), but not to you, of course. He then shows you the seven of spades, then the queen of hearts, then the eight of clubs and finally, the three of diamonds. You then have to tell people what what remaining card is. Indeed you do, and tell them correctly that it's the king of spades! There are no cheap tricks, slight of hand, mirrors or whatever here, but a clever mathematical algorithm. What is it (with proof that it works)?

Lecture 18: Here is Assignment 3 which is not due until April 18th, 2004. It also contains two SPECIAL PROBLEMS (15 and 16). We'll talk more about assignment 2. We'll also talk about the meaning of taking a derivative of an exponential generating series and give a nice example of enumerating "alternating permutations" such as w=13254 (up down up down..... pattern permutations).

SPECIAL PROBLEM 17: Give a combinatorial proof that the exponential generating series for alternating permutations is tan(x)+sec(x) (i.e., biject alternating permutations os size n with a combinatorial set that "obviously" has the cardinality of the coefficient of [x^n/n!] in tax(x)+sec(x).

Lecture 19: We started talking about the theory of symmetric functions (polynomials)--and following chapter 7 of Stanley's ECII. The symmetric group S_{n} acts on the ring of polynomials Q[x_1,x_2,...,x_n] by permuting the variables. A polynomial is _symmetric_ if w(f)=f for all w in S_n. It is not hard to see that the set of all symmetric polynomials in Q[x_1,...,x_n] forms a ring. Indeed it also forms a vector space over Q. Our first main task is to describe various bases for this vector space. We talked about the monomial symmetric functions.

Lecture 20: We talked about the elementary symmetric functions and their relation to the elementary symmetric functions. We also stated the following

(EASY-MEDIUM) SPECIAL PROBLEM 18: Expand \prod_{i\geq 1} (1+x_i +(x_i)^2 into elementary symmetric functions (the infinite product of (1+x_i +(x_i)^2) for i=1,2,3,... is obviously symmetric, so it should be writable as a linear combination of elementary symmetric polynomials. Find that linear combination)

Another simple but ubiquitous concept is that of "u-positivity". Let \{u_{\alpha}\} be a Q-basis (or Z-basis) for the ring of symmetric polynomials. Then any symmetric polynomial f=\sum C_{\alpha} u_{\alpha} is a linear combination of the u-basis elements. Then f is _u-positive_ if all the coefficients C_{\alpha} are nonnegative (integers). When this happens, these coefficients often have combinatorial significance.

We proved the "Fundamental theorem of symmetric functions" (which for us just covers the beginning steps), that the elementary symmetric functions form a linear basis for the ring of symmetric polynomials. We also talked more about partial orders (posets) on partitions. One concept is that of a "linear extension" of a poset. That is, a total order on the set P that has a given partial order < such that the total order is compatible with the partial order. Here's an open problem:

(OPEN) SPECIAL PROBLEM [S. Fomin]: Given a poset P of size $n$, consider all linear extensions. Fix any one of them as a reference. All others can be thought of as permutations of the first one. Each permutation is either even or odd. You might expect that the difference in the number of even and odd permutations (the _sign imbalance_) is small, but in fact it can be big in some cases. For each n>0, describe a (unique up to isomorphism??) poset M(n) whose sign imbalance is largest among all posets with n elements.

Lecture 21: Tony Chiang will guest lecture today.

Lecture 22: Talked about homogeneous symmetric functions and then power sum symmetric functions. I guess the main "trick" or "mentality" that I wanted to get across is how to look at things like \prod_{i} (1-x_it)=\sum e_n(X) t^n and see what it means! We also introduced the involution "omega" on the ring of symmetric functions (the one that is omega(e_n)=h_n). We used this to prove that the homogeneous symmetric functions form a basis.

Lecture 23: We'll do more on power sum symmetric functions, and in particular show that they too form a linear basis of the ring of symmetric functions. We studied the action of "omega" on these symmetric functions. (Upcoming: a scalar product on the ring of symmetric functions, then the answer to the question of an orthonormal basis **with integer coefficients**: the Schur functions!).

Lecture 24: We started working towards defining a scalar product < , > on the ring of symmetric functions. Well, basically the definition is that the m-basis and the h-basis are dual. In fact, all of these identities Product (1-x_i y_j)^{-1} = sum of products of symmetric functions are a statement about various bases being dual. Hence we proved a similar result for power sum symmetric functions, and examined the action of omega on these functions.

SPECIAL PROBLEM 19 (easy): Let z_{\lambda}=1^{m_{1}}m_{1}!.2^{m_{2}}m_{2}!.3^{m_{3}}m_{3}!... be the integer defined for a partition having m_{i} i's (i=1,2,...). If \lambda is a partition of n, prove that z_{\lambda} is the number of permutations (in S_n) that commute with a given fixed permutation of cycle type \lambda.

Lecture 25: We defined the scalar product on the ring of symmetric functions. This is the one that makes the m-basis and h-basis dual. We proved that whenever a u-basis and v-basis satisfy the same relation that the m-basis and h-basis do (see Lecture 24) the u and v-bases are dual. Hence it follows that the power sums are almost self dual. Started on the Schur polynomials. Here is Assignment 4 which is due May 11, 2004. It also contains a SPECIAL PROBLEM.

Lecture 26: Guest lecturer Tony Chiang.

Lecture 27: Proved the symmetry of the Schur polynomials directly from the combinatorial definition. We introduced and discussed the amazing Schensted correspondence.

Lecture 28: The amazing Gessel-Viennot involution trick to prove the Jacobi-Trudi identity for Schur polynomials. We will see this trick again soon in the proof of the Littlewood-Richardson rule.

Lecture 29: We proved that the Schur polynomials do from an integral basis of the ring of symmetric functions. We began towards our final goal: the proof of the Littlewood-Richardson rule. The idea is to use the Jacobi-Trudi identity and iterate the multiplication of a Schur polynomial with elementary (or homogeneous if you prefer) symmetric functions. Our first task was to prove a "Pieri" formula, which expands positively the product of a Schur with an elementary/homogeneous. We did this from the ratio of alternants description of the Schur polynomial. The basic idea to remember is that multiplying a Schur by an elementary e_k is like adding a vertical strip of size k (and with a homogeneous, it is adding a horizontal strip of size k).

Lecture 30: We continued our proof of the Littlewood-Richardson rule. Let me emphasize that the proof is a slick -- but retrospective one --. Such cancellation proofs are in general hard to find unless you know what the "good guys" are, i.e., the terms that are left uncancelled. By definition "easy problems" are those where it is easy to detect what these "good guys" are. This was not the case for the Littlewood-Richardson rule, and in fact there is a lot of combinatorics that was historically associated to the proof of the rule (jeu de taquin is one) that we avoid. However, the idea of wanting positive combinatorial formulas is a standard motif today in combinatorics. Feel free to come to my office to ask about this!