6.042J/18.062J Staff Notes
Week of Tues., Apr. 5 through Monday, Apr. 11

----------------------------------------------------------------------

Reading: 

----------------------------------------------------------------------

Lecture 16: Exponential generating functions

15    EGF's
	Definition
	Examples
	Manipulations, including binomial convolution

15    EGF's for permutations
	$(1+x)^n$ is EGF for <P(n,0), P(n,1), ..., P(n,n), 0, 0, ...>
	Theorem: product of EGF's for r-perms of union of sets
	Ex: EGF for r-perms of n-obj set is $(1+x)^n$

40    Examples
	Count: r-perms of {2\cdot a, 3\cdot b}
	Count: r-perms of {\infty\cdot 1,\infty\cdot 2,\ldots,\infty\cdot n}
	Count: r-perms of {\infty\cdot a,\infty\cdot b,\infty\cdot c}
	  where each of a,b,c appears at least once
	Count: r-perms of {\infty\cdot a,\infty\cdot b,\infty\cdot c}
	  where #a's is even
	Count: r-perms of {\infty\cdot a,\infty\cdot b,\infty\cdot c}
	  where # a's + b's is even
	Count: r-perms of {n_1\cdot 1,n_2\cdot 2,\ldots,n_k\cdot k}
	  Ans = to count r-perms, count perms of r-submultisets

----------------------------------------------------------------------