MAT344H1Y– Problem Set 7 Introduction to Combinatorics

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MAT344H1Y– Problem Set 7

Introduction to Combinatorics

Due: July 12, 11PM

Complete the following exercises from the textbook in §8 but do not submit them for credit: .  1-27. Think about 28.

Complete the following problems for credit.  You must link to the problems on Gradescope. Answer all questions with full and complete explanations.  The textbook is a good guide for what standard we are expecting of your explanations. Some questions may not be graded closely so that others may be focused on more closely in grading.

1.  Create a combinatorial problem that is solved via ordinary generating functions, similar to example.  8.5, exercise 8, or exercise 8, 10, 12 or 13 from the textbook.  The setting can be different but it should contain between 4 and 6 restrictions on the distribution of objects. Write down the generating function that solves the combinatorial problem, and explain how you arrived at the generating function from the restrictions.

2. We will denote by R[x] the set of polynomial with coefficients in R, and R[[x]] the set of formal power series with coefficients in R (note:  both are infinite dimensional R vectors spaces, and R[x] ⊂ R[[x]]). Symbolically:

These both have some interesting algebraic properties that make them analogous to Z.  For example, we can add, subtract, and multiply polynomials and power series together.   As it turns out, just like with Z, it is not always possible to divide.  For example, if p(x) ∈ R[x], p(x)−1  is only a polynomial if p(x) is a non-zero constant polynomial (the rational functions, denoted by R(x), is what you get when you allow for inverting polynomials). Things are much more interesting when you consider power series.

(a)  Suppose that p(x) = x2 + x − 6. Find the power series so that f(x) = p(x)−1 .

(b)  Suppose that p(x) is a polynomial with a non-zero constant term.  Explain how you can

find a power series f(x) so that f(x)p(x) = 1.  Find the first 5 coefficients for this power series when p(x) = x2 + x + 1.

(c) Explain how why the result of the previous part can be extended to show that if g(x) is any power series with non-zero constant term, then there is another power series f(x) so that f(x)g(x) = 1.

(d)  Suppose that p(x) = x+x2 . Show that there is a power series f(x) so that p(f(x)) = x (this is called the functional inverse. Such a functional inverse exists (and is unique) whenever p(x) is a power series with zero constant term and non-zero linear term).

3. By a labelled graph with n vertices we mean a graph G = ([n],E), where E ⊂ P([n]).  Two labelled graphs can be isomorphic  as graphs but distinct  as labelled graphs  (for example, ([3], {{1, 2}}) and ([3], {{2, 3}}) are isomorphic as graphs, but are considered distinct labelled graphs).

(a) Let

be the exponential generating function for the number of labelled graphs.   Show that an  = 2n(n−1)/2

(b) Let

be the exponential generating function for connected labelled graphs. At the moment we do not have any idea what the coefficients bn  are, simply that they are the number of labelled graphs with exactly n vertices that are connected (for example b3  = 4 is pretty easy to calculate, and you could probably work out b4  = 38, and you could go to https: //oeis.org/A001187 to see bn  up to n = 17 if you want but an exact formula may be difficult to come up with until part c). Show that F(x) = eH(x) − 1.

Hint :  First of all plug in the right hand side into the power series for ez .  Figure out a way to interpret H(x)k  as the exponential generating series for graphs with exactly k components.

(c) Now for some of the real power of generating functions. The power series for log(x + 1) is:

Use this to find an expression for bn . It might not be the prettiest but it works and if you’re curious about how many connected graphs with exactly 18 vertices there are a computer can tell you with this formula (you don’t actually need to submit that, but you should work through it for your own edification how this gives you the result for b3  and b4 ).


2023-07-11