15-344/Homework Assignment 9

DBN: Classes: 2015-16: 15-344 / Navigation Welcome to Math 344! Edits to the Math 344 web sites no longer count for the purpose of good deed points. # Week of... Notes and Links 1 Sep 14 About This Class, Day One Handout, Tuesday, Hour 3 Handout, Thursday, Tutorial 1 Handout 2 Sep 21 Tuesday, Tutorial 2 Page 1, Tutorial 2 Page 2, Thursday, HW1 3 Sep 28 Tuesday, Class Photo, Tutorial 3 Page 1, Tutorial 3 Page 2, Thursday, HW2 4 Oct 5 Tuesday, Drawing Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} -cubes, Thursday, HW3 5 Oct 12 Tuesday, Tutorial Handout, Thursday, HW4 6 Oct 19 Tuesday, Tutorial Handout, Thursday 7 Oct 26 Term Test on Tuesday, Dijkstra Handout,Thursday,HW5 8 Nov 2 Tuesday, Tutorial Handout, Thursday, HW6, Sunday November 8 is the last day to drop this class 9 Nov 9 Monday-Tuesday is UofT Fall Break, Thursday, HW7 10 Nov 16 Tuesday, Thursday, HW8 11 Nov 23 Tuesday, Thursday, HW9 12 Nov 30 Tuesday, Thursday, HW10 13 Dec 7 Tuesday, FibonacciFormula.pdf, semester ends on Wednesday - no class Thursday F Dec 11-22 The Final Exam Register of Good Deeds Add your name / see who's in!

This assignment is due at the tutorials on Thursday December 3. Here and everywhere, neatness counts!! You may be brilliant and you may mean just the right things, but if the teaching assistants will be having hard time deciphering your work they will give up and assume it is wrong.

Reread sections 6.1-6.2 of our textbook, and your notes for November 26 and December 1. Remember that reading math isn't like reading a novel! If you read a novel and miss a few details most likely you'll still understand the novel. But if you miss a few details in a math text, often you'll miss everything that follows. So reading math takes reading and rereading and rerereading and a lot of thought about what you've read. Also, preread chapter 7, just to get a feel for the future.

Solve problems 2abde, 2c, 4abc, 4d, 12, 16, 20, and 25 in section 6.1 and problems 1, 2, 11abcd, 11e, 30, 32, and 43 in section 6.2, but submit only your solutions of the underlined problems.

In addition, solve the following problem. There is no need to submit your solution.

Part 1. For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\geq 0} , let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_n} be the $n$'th Catalan number, defined as the number of words made of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} 's and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} 's in which in every initial segment there are at least as many Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} 's as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} 's. Prove that for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\geq 1} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_n=C_0C_{n-1}+C_1C_{n-2}+C_2C_{n-3}+\ldots+C_{n-1}C_0} .

Hint. If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} is such a word, let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k\geq 1} be the smallest such that if you cut Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} after Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2k} letters, then the number of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} 's before the cut is equal to the number of $b$'s before the cut. What can you say about the part of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} before the cut, and the part of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} after the cut?

Part 2. For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\geq 1} , let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_n} be the number of different ways of computing the product Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1A_2\cdots A_n} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} matrices. Prove that for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\geq 2} , $D_{n}=D_{1}D_{n-1}+D_{2}D_{n-2}+D_{3}D_{n-3}+\ldots +D_{n-1}D_{1}$.

Hint. In the last matrix multiplication to be carried out, you'd be multiplying the product of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} of the matrices with the product of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-k} of the matrices.

Part 3. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_2=1} and for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\geq 3} let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_n} be the number of triangulations of a convex Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} -gon using non-crossing diagonals. Prove that for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\geq 3} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_n=E_2E_{n-1}+E_3E_{n-2}+E_4E_{n-3}+\ldots+E_{n-1}E_2} .

Hint. Choose one edge of the $n$-gon, and consider the triangle on top of it, what's to its left, and what's to its right.

Part 4. Use the above three assertions to prove that for any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\geq 0} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_n=D_{n+1}=E_{n+2}} .

Dror's notes above / Students' notes below

Homework Assignment 9 Solution

2) Build a generating function for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{r}} , the number of integer solutions to the following equations.

c) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_{1}+e_{2}+e_{3}+e_{4} = r, 2\leq e_{i} \leq 7, e_{1}} even Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_{2} } odd.

A) For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_{3}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_{4}} together, we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_{1}(x) = (x^2+x^3+x^4+x^5+x^6+x^7)^2 }

        For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_{1}}
, we have $g_{2}(x)=(x^{2}+x^{4}+x^{6})$

        For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_{2}}
, we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_{3}(x) = (x^3+x^5+x^7) }

In total, we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x) = (x^2+x^4+x^6)(x^3+x^5+x^7)(x^2+x^3+x^4+x^5+x^6+x^7)^2 }

4 d) Three different boxes with at most five objects in the first box

A) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_{1}+e_{2}+e_{3} = r} with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0\leq e_{1} \leq 5}

For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_{1}} , we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1+x+x^2+x^3+x^4+x^5) }

Note that for the other two, we don't have a limit, so:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=0}^{\infty}x^{k} = \frac{1}{1-x} }

so, in total we have: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x) = (1+x+x^2+x^3+x^4+x^5)(\frac{1}{1-x})^2 }

16) Find a generating function for the number of integers between 0 and 999,999 whose sum of digits is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r } .

A) For each integer in the range, we can express them as a six digit number, including 0's in the front (5 will be 000005). So this amounts to finding:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_{1}+e_{2}+e_{3}+e_{4}+e_{5}+e_{6} = r , 0 \leq e_{i} \leq 9 , 1 \leq i \leq 6 }

So, we have <math> g(x) = (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9)^6