15-344/Homework Assignment 9: Difference between revisions

From Drorbn
Jump to navigationJump to search
No edit summary
No edit summary
 
(4 intermediate revisions by one other user not shown)
Line 26: Line 26:
Homework Assignment 9 Solution
Homework Assignment 9 Solution


'''2)''' Build a generating function for <math>a_{r}</math>, the number of integer solutions to the following equations.
'''2) Build a generating function for <math>a_{r}</math>, the number of integer solutions to the following equations.'''


c) <math>e_{1}+e_{2}+e_{3}+e_{4} = r, 2\leq e_{i} \leq 7, e_{1}</math> even <math> e_{2} </math> odd.
c) <math>e_{1}+e_{2}+e_{3}+e_{4} = r, 2\leq e_{i} \leq 7, e_{1}</math> even <math> e_{2} </math> odd.
Line 32: Line 32:
'''A)''' For <math>e_{3}</math> and <math>e_{4}</math> together, we have <math>g_{1}(x) = (x^2+x^3+x^4+x^5+x^6+x^7)^2 </math>
'''A)''' For <math>e_{3}</math> and <math>e_{4}</math> together, we have <math>g_{1}(x) = (x^2+x^3+x^4+x^5+x^6+x^7)^2 </math>
For <math>e_{1}</math>, we have <math>g_{2}(x) = (x^2+x^4+x^6) </math>
For <math>e_{1}</math>, we have <math>g_{2}(x) = (x^2+x^4+x^6) </math>


For <math>e_{2}</math>, we have <math>g_{3}(x) = (x^3+x^5+x^7) </math>
For <math>e_{2}</math>, we have <math>g_{3}(x) = (x^3+x^5+x^7) </math>


In total, we have <math>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 </math>
In total, we have <math>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 </math>


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


'''A)''' <math>e_{1}+e_{2}+e_{3} = r</math> with <math>0\leq e_{1} \leq 5</math>
'''A)''' <math>e_{1}+e_{2}+e_{3} = r</math> with <math>0\leq e_{1} \leq 5</math>
Line 49: Line 49:


so, in total we have: <math> g(x) = (1+x+x^2+x^3+x^4+x^5)(\frac{1}{1-x})^2 </math>
so, in total we have: <math> g(x) = (1+x+x^2+x^3+x^4+x^5)(\frac{1}{1-x})^2 </math>


'''16) Find a generating function for the number of integers between 0 and 999,999 whose sum of digits is <math> r </math>.'''

'''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:

<math> e_{1}+e_{2}+e_{3}+e_{4}+e_{5}+e_{6} = r , 0 \leq e_{i} \leq 9 , 1 \leq i \leq 6 </math>

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 </math>


'''Section 6.1 2) Find the coefficient of <math> x^r </math> in <math> (x^5 + x^6 + x^7 +...)^8</math>'''

'''A)'''

<math>(x^5 + x^6 + x^7 +...)^8 = (x^5(1+ x + x^2 ...))^8 = x^{40} \frac{1}{(1-x)^8} </math>

The coefficient of <math> x^r </math> in this will be of <math> x^{r-40} </math> in <math> (1-x)^{-8} </math>, which is

<math>\binom{(r-40) + 8 - 1}{r-40} </math>

== Scanned Solution to Homework9 P11e,32,43 in Secton6.2 ==
<gallery>
15-344-HW9.1-Yunheng Chen.jpg|Page 1
HW9.2-Yunheng Chen.jpg|Page 2
</gallery>

Latest revision as of 01:58, 16 December 2015

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 , let be the 'th Catalan number, defined as the number of words made of 's and 's in which in every initial segment there are at least as many 's as 's. Prove that for , .

Hint. If is such a word, let be the smallest such that if you cut after letters, then the number of 's before the cut is equal to the number of 's before the cut. What can you say about the part of before the cut, and the part of after the cut?

Part 2. For , let be the number of different ways of computing the product of matrices. Prove that for , .

Hint. In the last matrix multiplication to be carried out, you'd be multiplying the product of of the matrices with the product of of the matrices.

Part 3. Let and for let be the number of triangulations of a convex -gon using non-crossing diagonals. Prove that for , .

Hint. Choose one edge of the -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 , .

Dror's notes above / Students' notes below

Homework Assignment 9 Solution

2) Build a generating function for , the number of integer solutions to the following equations.

c) even odd.

A) For and together, we have

For , we have

For , we have

In total, we have

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

A) with

For , we have

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

so, in total we have:


16) Find a generating function for the number of integers between 0 and 999,999 whose sum of digits is .

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:

So, we have


Section 6.1 2) Find the coefficient of in

A)

The coefficient of in this will be of in , which is

Scanned Solution to Homework9 P11e,32,43 in Secton6.2